LeetCode-in-Java

3531. Count Covered Buildings

Medium

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:
  • above ([1,2])
  • below ([3,2])
  • left ([2,1])
  • right ([2,3])
• Thus, the count of covered buildings is 1.

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:
  • above ([1,3])
  • below ([5,3])
  • left ([3,2])
  • right ([3,5])
• Thus, the count of covered buildings is 1.

Constraints:

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

Solution

import java.util.Arrays;

public class Solution {
    private int helper(int[][] buildings, int n) {
        int[] minRow = new int[n + 1];
        int[] maxRow = new int[n + 1];
        int[] minCol = new int[n + 1];
        int[] maxCol = new int[n + 1];
        Arrays.fill(minRow, n + 1);
        Arrays.fill(minCol, n + 1);
        for (int[] b : buildings) {
            int x = b[0];
            int y = b[1];
            minRow[x] = Math.min(minRow[x], y);
            maxRow[x] = Math.max(maxRow[x], y);
            minCol[y] = Math.min(minCol[y], x);
            maxCol[y] = Math.max(maxCol[y], x);
        }
        int ans = 0;
        for (int[] arr : buildings) {
            int x = arr[0];
            int y = arr[1];
            if (minRow[x] < y && maxRow[x] > y && minCol[y] < x && maxCol[y] > x) {
                ans++;
            }
        }
        return ans;
    }

    public int countCoveredBuildings(int n, int[][] buildings) {
        return helper(buildings, n);
    }
}

This site is open source. Improve this page.