2025-12-11 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 11

Description

Count Covered Buildings

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.

 

Example 1:

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

Output: 1

Explanation:

  • Only building [2,2] is covered as it has at least one building: 
    <ul>
	<li>above (<code>[1,2]</code>)</li>
	<li>below (<code>[3,2]</code>)</li>
	<li>left (<code>[2,1]</code>)</li>
	<li>right (<code>[2,3]</code>)</li>
</ul>
</li>
<li>Thus, the count of covered buildings is 1.</li>

Example 2:

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

Output: 0

Explanation:

  • No building has at least one building in all four directions.

Example 3:

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

Output: 1

Explanation:

  • Only building [3,3] is covered as it has at least one building: 
    <ul>
	<li>above (<code>[1,3]</code>)</li>
	<li>below (<code>[5,3]</code>)</li>
	<li>left (<code>[3,2]</code>)</li>
	<li>right (<code>[3,5]</code>)</li>
</ul>
</li>
<li>Thus, the count of covered buildings is 1.</li>

 

Constraints:

  • 2 <= n <= 105
  • 1 <= buildings.length <= 105
  • buildings[i] = [x, y]
  • 1 <= x, y <= n
  • All coordinates of buildings are unique.

Solution

class Solution {
public:
  int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
    vector<int> left(n + 1, n + 1);
    vector<int> right(n + 1, 0);
    vector<int> up(n + 1, 0);
    vector<int> down(n + 1, n + 1);
    
    for(const auto &b : buildings) {
      left[b[0]] = min(left[b[0]], b[1]);
      right[b[0]] = max(right[b[0]], b[1]);
      up[b[1]] = max(up[b[1]], b[0]);
      down[b[1]] = min(down[b[1]], b[0]);
    }

    int answer = 0;
    for(const auto &b : buildings) {
      int x = b[1];
      int y = b[0];
      answer += (y > down[x] && y < up[x] && x > left[y] && x < right[y]);
    }

    return answer;
  }
};

// Accepted
// 634/634 cases passed (24 ms)
// Your runtime beats 87.37 % of cpp submissions
// Your memory usage beats 87.89 % of cpp submissions (283.7 MB)
Algorithm