Count Covered Buildings - Practice Coding Problems

Count Covered Buildings - Problem

You are given a positive integer n, representing an n x n city. You are also given a 2D grid buildings, where buildings[i] = [x, y] denotes a unique building located at coordinates [x, y].

A building is covered if there is at least one building in all four directions: left, right, above, and below.

Return the number of covered buildings.

Input & Output

Example 1 — Grid with One Covered Building

$ Input: n = 4, buildings = [[2,2],[1,2],[3,2],[2,1],[2,3]]

› Output: 1

💡 Note: Building at (2,2) is covered: left (2,1), right (2,3), above (1,2), below (3,2). All other buildings lack coverage in at least one direction.

Example 2 — No Covered Buildings

$ Input: n = 3, buildings = [[1,1],[1,2],[2,1]]

› Output: 0

💡 Note: No building has coverage in all four directions. Each building is missing at least one directional neighbor.

Example 3 — Multiple Covered Buildings

$ Input: n = 5, buildings = [[2,2],[2,3],[1,2],[3,2],[2,1],[2,4],[1,3],[3,3]]

› Output: 2

💡 Note: Buildings (2,2) and (2,3) are both covered, each having neighbors in all four cardinal directions.

Constraints

1 ≤ n ≤ 10³
1 ≤ buildings.length ≤ 5 × 10²
buildings[i] = [x_i, y_i]
1 ≤ x_i, y_i ≤ n
All buildings are at unique locations

Visualization

Tap to expand

Understanding the Visualization

Input

Grid size n and building coordinates

Process

Check each building for neighbors in all four cardinal directions

Output

Count of buildings with complete coverage

Key Takeaway

🎯 Key Insight: A building is covered only when it has at least one neighbor in each cardinal direction (left, right, above, below)

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is that a building is covered only when it has at least one neighbor in each of the four cardinal directions. The optimal approach uses hash sets for O(1) coordinate lookups, achieving O(m×n) time complexity where we check each building against potential positions in all directions. Time: O(m×n), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(m²)	O(m)	Use hash sets to store building coordinates for O(1) lookup when checking coverage
Brute Force	O(m²)	O(1)	For each building, scan all other buildings to check coverage in all four directions

Hash Set Optimization — Algorithm Steps

Store all building coordinates in a hash set
For each building, check each direction
Use hash set to quickly verify if buildings exist in each direction
Count buildings with complete coverage

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Set

Store all building coordinates in hash set

Check Directions

For each building, use hash set to quickly check if buildings exist in each direction

Count Covered

Increment counter for buildings with complete coverage

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_BUILDINGS 1000

int solution(int n, int buildings[][2], int m) {
    int coveredCount = 0;
    
    for (int i = 0; i < m; i++) {
        int x = buildings[i][0];
        int y = buildings[i][1];
        bool left = false, right = false, above = false, below = false;
        
        // Check left direction
        for (int cy = 1; cy < y; cy++) {
            for (int j = 0; j < m; j++) {
                if (buildings[j][0] == x && buildings[j][1] == cy) {
                    left = true;
                    break;
                }
            }
            if (left) break;
        }
        
        // Check right direction
        for (int cy = y + 1; cy <= n; cy++) {
            for (int j = 0; j < m; j++) {
                if (buildings[j][0] == x && buildings[j][1] == cy) {
                    right = true;
                    break;
                }
            }
            if (right) break;
        }
        
        // Check above direction
        for (int cx = 1; cx < x; cx++) {
            for (int j = 0; j < m; j++) {
                if (buildings[j][0] == cx && buildings[j][1] == y) {
                    above = true;
                    break;
                }
            }
            if (above) break;
        }
        
        // Check below direction
        for (int cx = x + 1; cx <= n; cx++) {
            for (int j = 0; j < m; j++) {
                if (buildings[j][0] == cx && buildings[j][1] == y) {
                    below = true;
                    break;
                }
            }
            if (below) break;
        }
        
        if (left && right && above && below) {
            coveredCount++;
        }
    }
    
    return coveredCount;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for format [[x1,y1],[x2,y2],...]
    int buildings[MAX_BUILDINGS][2];
    int m = 0;
    
    char* ptr = line + 1;  // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            buildings[m][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;  // Skip comma
            buildings[m][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;  // Skip closing ']'
            m++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(n, buildings, m);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²)

Still need to check each building against potential positions in all directions

✓ Linear Growth

Space Complexity

O(m)

Hash set stores all m building coordinates

✓ Linear Space

23.4K Views

Medium Frequency

~18 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler