Count Covered Buildings

Medium
1830.

Count Covered Buildings

Count Covered Buildings is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

A city is an n x n grid. You are given the positions of its buildings as buildings[i] = [x, y]; no two buildings share a position.

A building is covered if there is at least one other building in each of the four directions from it:

  • left and right: a building with the same x and a smaller / larger y;
  • above and below: a building with the same y and a smaller / larger x.

Return the number of covered buildings.

Example 1

Input
n = 4, buildings = [[2,2],[1,2],[4,2],[2,1],[2,4],[3,3]]
Output
1
Explanation
`[2,2]` has `[2,1]` and `[2,4]` beside it and `[1,2]` and `[4,2]` above and below it. No other building has neighbours on all four sides.

Example 2

Input
n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
Output
0
Explanation
Every building sits on the edge of the block.

Example 3

Input
n = 4, buildings = [[1,2],[1,3],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,2],[4,3]]
Output
4
Explanation
The four inner buildings `[2,2]`, `[2,3]`, `[3,2]`, `[3,3]` are covered.

Constraints

  • 2 <= n <= 10^5
  • 1 <= buildings.length <= 10^5
  • buildings[i] = [x, y] with 1 <= x, y <= n
  • All positions in buildings are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} buildings
 * @return {number}
 */
var countCoveredBuildings = function(n, buildings) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Covered Buildings — Solution in Python, Java & C++

Count Covered Buildings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Covered Buildings is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Sorting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A city is an n x n grid. You are given the positions of its buildings as buildings[i] = [x, y]; no two buildings share a position.

A building is covered if there is at least one other building in each of the four directions from it:

  • left and right: a building with the same x and a smaller / larger y;
  • above and below: a building with the same y and a smaller / larger x.

Return the number of covered buildings.

Example 1

Input: n = 4, buildings = [[2,2],[1,2],[4,2],[2,1],[2,4],[3,3]]
Output: 1
Explanation: `[2,2]` has `[2,1]` and `[2,4]` beside it and `[1,2]` and `[4,2]` above and below it. No other building has neighbours on all four sides.

Example 2

Input: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
Output: 0
Explanation: Every building sits on the edge of the block.

Example 3

Input: n = 4, buildings = [[1,2],[1,3],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,2],[4,3]]
Output: 4
Explanation: The four inner buildings `[2,2]`, `[2,3]`, `[3,2]`, `[3,3]` are covered.

Constraints

  • 2 <= n <= 10^5
  • 1 <= buildings.length <= 10^5
  • buildings[i] = [x, y] with 1 <= x, y <= n
  • All positions in buildings are unique

Hints for Count Covered Buildings

  1. Hint 1

    A building has something to its left and to its right exactly when its y is neither the smallest nor the largest y among buildings with the same x.

  2. Hint 2

    Likewise for above and below, using the smallest and largest x among buildings with the same y.

  3. Hint 3

    One pass records, for every x, the min and max y, and for every y, the min and max x. A second pass tests each building strictly between both pairs.

How to solve Count Covered Buildings

Only the extremes of each row and column matter: a building has a neighbour on both sides of its line exactly when it is strictly inside that line's range of occupied positions.

Approach

  1. For each x, track minY[x] and maxY[x] over buildings with that x.
  2. For each y, track minX[y] and maxX[y] over buildings with that y.
  3. Count the buildings with minY[x] < y < maxY[x] and minX[y] < x < maxX[y].

Why it works

A building with the same x and a smaller y exists iff the smallest y for that x is below this one, and similarly for the other three directions. The four strict inequalities are exactly the four directions of the definition.

Complexity

  • Time — O(n + m) where m is the number of buildings
  • Space — O(n)

Pitfalls

  • Checking all four directions by scanning every other building is O(m^2) — too slow at 10^5 buildings.
  • The comparisons are strict: a building is not its own neighbour.

Reference solution

Python

from typing import List

def countCoveredBuildings(n: int, buildings: List[List[int]]) -> int:
    big = n + 1
    min_y = [big] * (n + 1)
    max_y = [0] * (n + 1)
    min_x = [big] * (n + 1)
    max_x = [0] * (n + 1)
    for x, y in buildings:
        min_y[x] = min(min_y[x], y)
        max_y[x] = max(max_y[x], y)
        min_x[y] = min(min_x[y], x)
        max_x[y] = max(max_x[y], x)
    return sum(1 for x, y in buildings
               if min_y[x] < y < max_y[x] and min_x[y] < x < max_x[y])

Java

public static int countCoveredBuildings(int n, int[][] buildings) {
    int[] minY = new int[n + 1], maxY = new int[n + 1], minX = new int[n + 1], maxX = new int[n + 1];
    Arrays.fill(minY, n + 1);
    Arrays.fill(minX, n + 1);
    for (int[] b : buildings) {
        int x = b[0], y = b[1];
        minY[x] = Math.min(minY[x], y);
        maxY[x] = Math.max(maxY[x], y);
        minX[y] = Math.min(minX[y], x);
        maxX[y] = Math.max(maxX[y], x);
    }
    int count = 0;
    for (int[] b : buildings) {
        int x = b[0], y = b[1];
        if (minY[x] < y && y < maxY[x] && minX[y] < x && x < maxX[y]) count++;
    }
    return count;
}

C++

int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
    vector<int> minY(n + 1, n + 1), maxY(n + 1, 0), minX(n + 1, n + 1), maxX(n + 1, 0);
    for (auto& b : buildings) {
        int x = b[0], y = b[1];
        minY[x] = min(minY[x], y);
        maxY[x] = max(maxY[x], y);
        minX[y] = min(minX[y], x);
        maxX[y] = max(maxX[y], x);
    }
    int count = 0;
    for (auto& b : buildings) {
        int x = b[0], y = b[1];
        if (minY[x] < y && y < maxY[x] && minX[y] < x && x < maxX[y]) count++;
    }
    return count;
}

JavaScript

var countCoveredBuildings = function(n, buildings) {
    var minY = new Array(n + 1).fill(n + 1), maxY = new Array(n + 1).fill(0);
    var minX = new Array(n + 1).fill(n + 1), maxX = new Array(n + 1).fill(0);
    for (var i = 0; i < buildings.length; i++) {
        var x = buildings[i][0], y = buildings[i][1];
        if (y < minY[x]) minY[x] = y;
        if (y > maxY[x]) maxY[x] = y;
        if (x < minX[y]) minX[y] = x;
        if (x > maxX[y]) maxX[y] = x;
    }
    var count = 0;
    for (var j = 0; j < buildings.length; j++) {
        var a = buildings[j][0], b = buildings[j][1];
        if (minY[a] < b && b < maxY[a] && minX[b] < a && a < maxX[b]) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets