Problem Description

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

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

Your task is to determine and return the number of covered buildings.

Intuition

To solve the problem of counting covered buildings, we employ a combination of data structures to efficiently manage and access building coordinates. The key idea is to categorize the buildings by their x and y coordinates using hash tables, then sort these coordinates to quickly check if a building is covered.

1. Hash Tables for Categorization: We use two hash tables, g1 and g2. g1[x] stores all the y-coordinates of buildings with the same x-coordinate x. Similarly, g2[y] keeps all the x-coordinates of buildings sharing the y-coordinate y. This sets the groundwork for categorizing and accessing buildings based on their respective axes.

2. Sorting for Efficient Checking: Once categorized, we sort the lists in both hash tables. Sorting helps easily determine if the current building (x, y) has neighbors in the required directions by checking the minimum and maximum values in the sorted lists.

3. Checking Coverage Condition: For a building (x, y) to be covered, it should have buildings both to its left and right (on the same y-coordinate), and buildings both above and below it (on the same x-coordinate). Mathematically, this translates to checking if:

   • l2[0] < x < l2[-1] where l2 is the sorted list of x-coordinates at y.
   • l1[0] < y < l1[-1] where l1 is the sorted list of y-coordinates at x.

By looping through each building and applying the above checks, we accumulate the count of covered buildings.

This method ensures an efficient traversal of potential candidate buildings, making it feasible to work within the constraints typically encountered in computational problems.

Learn more about Sorting patterns.

Solution Approach

The solution for counting covered buildings involves a strategic use of hash tables and sorting. Here's a step-by-step walkthrough of the implementation:

1. Data Structures Setup:

   • We initialize two hash tables, g1 and g2, using Python's defaultdict from the collections module. These will help in grouping buildings by their coordinates.
   • g1[x] will hold a list of all y-coordinates for buildings with x-coordinate x.
   • g2[y] will contain a list of all x-coordinates for buildings sharing the y-coordinate y.

2. Populating Hash Tables:

   • Iterate through each building's coordinates (x, y) in the given buildings list.
   • For each building, append the y-coordinate y to g1[x] and the x-coordinate x to g2[y].

3. Sorting for Quick Access:

   • After populating the hash tables, sort the lists in both g1 and g2. This enables quick determination of neighboring buildings along the same line of coordinate.

4. Counting Covered Buildings:

   • Initialize a counter ans to zero, which will store the number of covered buildings.
   • Loop over each building (x, y) again.
   • Retrieve the sorted list l1 from g1[x], which contains y-coordinates, and l2 from g2[y], which contains x-coordinates.
   • Check if the conditions for being covered are met:
     • l2[0] < x < l2[-1] ensures there are buildings both on the left and right.
     • l1[0] < y < l1[-1] ensures there are buildings both above and below.
   • If both conditions are satisfied, increment the ans counter.

5. Return the Result:

   • Once all buildings are processed, the final count stored in ans is returned as the result.

This approach efficiently determines which buildings are covered by leveraging the combined power of hash tables for fast categorization and sorting for concise condition checking.

Example Walkthrough

Consider a simple 3 x 3 grid with three buildings located at the following coordinates:

• Building 1: (1, 1)
• Building 2: (1, 2)
• Building 3: (2, 2)

The grid visualization will look like this:

    y
    |
    v
  3 . . .
  2 . B C
  1 . A .
    1   2  3
          x

Where A, B, and C represent buildings.

Step 1: Data Structures Setup

• Initialize two hash tables using defaultdict: g1 and g2.

Step 2: Populating Hash Tables

• For building (1, 1), g1[1] = [1] and g2[1] = [1].
• For building (1, 2), g1[1] = [1, 2] and g2[2] = [1].
• For building (2, 2), g1[2] = [2] and g2[2] = [1, 2].

Step 3: Sorting for Quick Access

• Sort the coordinates in g1 and g2:
  • g1[1] remains [1, 2].
  • g1[2] remains [2].
  • g2[1] remains [1].
  • g2[2] is sorted as [1, 2].

Step 4: Counting Covered Buildings

• Initialize counter ans = 0.

• Check building (1, 1):

  • l1 = [1, 2] from g1[1] and l2 = [1] from g2[1].
  • Condition l1[0] < y < l1[-1] fails as 1 < 1 < 2 is false.
  • Building (1, 1) is not covered.

• Check building (1, 2):

  • l1 = [1, 2] from g1[1] and l2 = [1, 2] from g2[2].
  • Condition l1[0] < y < l1[-1] fails as 1 < 2 < 2 is false.
  • Building (1, 2) is not covered.

• Check building (2, 2):

  • l1 = [2] from g1[2] and l2 = [1, 2] from g2[2].
  • Condition l2[0] < x < l2[-1] fails as 1 < 2 < 2 is false.
  • Building (2, 2) is not covered.

Step 5: Return the Result

• The final count of covered buildings is ans = 0.

Thus, none of the buildings are covered in this particular setup.

Solution Implementation

Time and Space Complexity

The given code iterates through the buildings list to populate two dictionaries g1 and g2, where each dictionary maintains a list of coordinates. The iteration is done using a for loop, which makes the time complexity for this operation $O(n)$, where n is the number of buildings.

Sorting each list in g1 and g2 individually takes $O(k \cdot \log k)$ time for each list, where k is the length of that list. In the worst case, each list can contain up to n elements, therefore, the total sorting operation contributes $O(n \cdot \log n)$ to the time complexity.

Finally, the code iterates over the buildings list once more to check the conditions for counting covered buildings, which is an $O(n)$ operation.

Therefore, the overall time complexity is $O(n \times \log n)$ due to the sorting step.

The space complexity of the code is $O(n)$. This is due to the dictionaries g1 and g2, which store up to n elements collectively where each building's coordinates are used to fill in these lists.

Learn more about how to find time and space complexity quickly.