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
xand a smaller / largery; - above and below: a building with the same
yand a smaller / largerx.
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^51 <= buildings.length <= 10^5buildings[i] = [x, y] with 1 <= x, y <= nAll positions in buildings are unique
Hints for Count Covered Buildings
Hint 1
A building has something to its left and to its right exactly when its
yis neither the smallest nor the largestyamong buildings with the samex.Hint 2
Likewise for above and below, using the smallest and largest
xamong buildings with the samey.Hint 3
One pass records, for every
x, the min and maxy, and for everyy, the min and maxx. 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
- For each
x, trackminY[x]andmaxY[x]over buildings with thatx. - For each
y, trackminX[y]andmaxX[y]over buildings with thaty. - Count the buildings with
minY[x] < y < maxY[x]andminX[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 at10^5buildings. - 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