Problem Description

You have an n x n city grid and a list of buildings with their coordinates. Each building is represented as [x, y] where x and y are its coordinates on the grid.

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

• At least one building to its left (same row x, smaller column y)
• At least one building to its right (same row x, larger column y)
• At least one building above it (same column y, larger row x)
• At least one building below it (same column y, smaller row x)

Your task is to count how many buildings are covered according to this definition.

For example, if a building is at position [2, 3], it would be covered only if:

• There's at least one building at [2, y] where y < 3 (left)
• There's at least one building at [2, y] where y > 3 (right)
• There's at least one building at [x, 3] where x > 2 (above)
• There's at least one building at [x, 3] where x < 2 (below)

The solution groups buildings by their x-coordinates and y-coordinates using hash tables. For each building (x, y), it checks if there are buildings both before and after it in the same row (checking g1[x] for y-values) and buildings both before and after it in the same column (checking g2[y] for x-values). If both conditions are met, the building is covered.

Intuition

The key insight is that to check if a building is covered, we need to efficiently determine if there are buildings in all four directions from it. Instead of checking every possible pair of buildings (which would be inefficient), we can organize the data to make these checks fast.

Think about what it means for a building at (x, y) to have neighbors in all four directions:

• Buildings to the left and right share the same row x but have different y values
• Buildings above and below share the same column y but have different x values

This naturally leads us to group buildings by their shared coordinates. If we group all buildings that share the same x-coordinate together, we can quickly find all buildings in the same row. Similarly, grouping by y-coordinate gives us all buildings in the same column.

Once we have these groupings:

• For a building at (x, y), all buildings in row x are stored in g1[x] as a list of y-coordinates
• All buildings in column y are stored in g2[y] as a list of x-coordinates

By sorting these lists, we can use a simple comparison to check coverage:

• If the building's y value is between the minimum and maximum in g1[x], it has neighbors left and right
• If the building's x value is between the minimum and maximum in g2[y], it has neighbors above and below

The condition l2[0] < x < l2[-1] checks if x is strictly between the smallest and largest x-coordinates in column y, confirming vertical neighbors. Similarly, l1[0] < y < l1[-1] confirms horizontal neighbors. When both conditions are true, the building is covered.

Learn more about Sorting patterns.

Solution Approach

The implementation uses hash tables and sorting to efficiently determine covered buildings.

Step 1: Group buildings by coordinates

We create two hash tables using defaultdict(list):

• g1: Maps each x-coordinate to a list of y-coordinates of buildings in that row
• g2: Maps each y-coordinate to a list of x-coordinates of buildings in that column

g1 = defaultdict(list)
g2 = defaultdict(list)
for x, y in buildings:
    g1[x].append(y)
    g2[y].append(x)

For example, if we have buildings at [2,3], [2,5], and [4,3]:

• g1[2] would contain [3, 5] (all y-values for row 2)
• g2[3] would contain [2, 4] (all x-values for column 3)

Step 2: Sort the coordinate lists

We sort each list to easily identify the minimum and maximum values:

for x in g1:
    g1[x].sort()
for y in g2:
    g2[y].sort()

After sorting, the first element [0] is the minimum and the last element [-1] is the maximum.

Step 3: Check each building for coverage

For each building (x, y), we:

1. Get the sorted list of y-coordinates in row x: l1 = g1[x]
2. Get the sorted list of x-coordinates in column y: l2 = g2[y]
3. Check if the building is covered using the conditions:
   • l2[0] < x < l2[-1]: There are buildings both above (x > l2[0]) and below (x < l2[-1])
   • l1[0] < y < l1[-1]: There are buildings both to the left (y > l1[0]) and right (y < l1[-1])

ans = 0
for x, y in buildings:
    l1 = g1[x]
    l2 = g2[y]
    if l2[0] < x < l2[-1] and l1[0] < y < l1[-1]:
        ans += 1

The time complexity is O(n log n) where n is the number of buildings, due to the sorting operations. The space complexity is O(n) for storing the hash tables.

Example Walkthrough

Let's walk through a concrete example with buildings at coordinates: [[1,2], [2,1], [2,2], [2,3], [3,2]]

Visualizing on a grid (with 'B' marking buildings):

  0 1 2 3
3       B
2   B B B
1     B
0

Step 1: Group buildings by coordinates

We create two hash tables:

• g1 (group by x-coordinate/row):

  • g1[1] = [2] (row 1 has building at column 2)
  • g1[2] = [1, 2, 3] (row 2 has buildings at columns 1, 2, 3)
  • g1[3] = [2] (row 3 has building at column 2)

• g2 (group by y-coordinate/column):

  • g2[1] = [2] (column 1 has building at row 2)
  • g2[2] = [1, 2, 3] (column 2 has buildings at rows 1, 2, 3)
  • g2[3] = [2] (column 3 has building at row 2)

Step 2: Sort the coordinate lists

After sorting (already sorted in this case):

• g1[1] = [2], g1[2] = [1, 2, 3], g1[3] = [2]
• g2[1] = [2], g2[2] = [1, 2, 3], g2[3] = [2]

Step 3: Check each building for coverage

1. Building at [1,2]:

   • l1 = g1[1] = [2] (buildings in row 1)
   • l2 = g2[2] = [1, 2, 3] (buildings in column 2)
   • Check: 1 < 1 < 3? Yes. 2 < 2 < 2? No (need strict inequality)
   • Not covered ❌

2. Building at [2,1]:

   • l1 = g1[2] = [1, 2, 3] (buildings in row 2)
   • l2 = g2[1] = [2] (buildings in column 1)
   • Check: 2 < 2 < 2? No. 1 < 1 < 3? No
   • Not covered ❌

3. Building at [2,2]:

   • l1 = g1[2] = [1, 2, 3] (buildings in row 2)
   • l2 = g2[2] = [1, 2, 3] (buildings in column 2)
   • Check: 1 < 2 < 3? Yes. 1 < 2 < 3? Yes
   • Covered! ✓ (has buildings in all 4 directions)

4. Building at [2,3]:

   • l1 = g1[2] = [1, 2, 3] (buildings in row 2)
   • l2 = g2[3] = [2] (buildings in column 3)
   • Check: 2 < 2 < 2? No. 1 < 3 < 3? No
   • Not covered ❌

5. Building at [3,2]:

   • l1 = g1[3] = [2] (buildings in row 3)
   • l2 = g2[2] = [1, 2, 3] (buildings in column 2)
   • Check: 1 < 3 < 3? No. 2 < 2 < 2? No
   • Not covered ❌

Result: Only 1 building (at [2,2]) is covered.

The building at [2,2] is covered because:

• Left: building at [2,1] (same row, smaller y)
• Right: building at [2,3] (same row, larger y)
• Below: building at [1,2] (same column, smaller x)
• Above: building at [3,2] (same column, larger x)

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of buildings.

Breaking down the time complexity:

• Creating the dictionaries g1 and g2 by iterating through all buildings: O(n)
• Sorting all lists in g1: In the worst case, all buildings share the same x-coordinate, resulting in one list of length n to sort, which takes O(n log n). In the best case, each x-coordinate has only one building, resulting in n lists of length 1, which takes O(n) total. Overall, the sorting step is O(n log n) in the worst case.
• Sorting all lists in g2: Similarly, this takes O(n log n) in the worst case.
• Final loop through all buildings: O(n), with each iteration performing constant-time operations (accessing first and last elements of sorted lists and comparisons).

The dominant operation is the sorting step, giving us O(n log n) overall time complexity.

The space complexity is O(n), where n is the number of buildings.

Breaking down the space complexity:

• Dictionary g1 stores at most n building coordinates across all its lists: O(n)
• Dictionary g2 stores at most n building coordinates across all its lists: O(n)
• The total auxiliary space used is O(n) + O(n) = O(n)

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

Common Pitfalls

Pitfall 1: Confusion About Coordinate System Interpretation

The Problem: A major source of confusion in this problem is the inconsistent interpretation of the coordinate system between the problem description and the actual solution. The problem states:

• "above it (same column y, larger row x)"
• "below it (same column y, smaller row x)"

However, the solution code uses the opposite logic:

if l2[0] < x < l2[-1] and l1[0] < y < l1[-1]:

This checks if x is between the minimum and maximum x-values (treating smaller x as "below" and larger x as "above"), which contradicts the problem statement.

Why This Happens: Different coordinate systems can be used:

1. Mathematical convention: Origin at bottom-left, y increases upward
2. Computer graphics convention: Origin at top-left, y increases downward
3. Matrix indexing: Row index increases downward

The Solution: Always clarify the coordinate system before implementing. If the problem states "larger row x means above," ensure your code reflects this:

# Corrected version matching problem description
for x_coord, y_coord in buildings:
    y_coords_at_x = buildings_by_x[x_coord]
    x_coords_at_y = buildings_by_y[y_coord]
  
    # According to problem: larger x = above, smaller x = below
    has_below = any(x < x_coord for x in x_coords_at_y)  # smaller x
    has_above = any(x > x_coord for x in x_coords_at_y)  # larger x
    has_left = any(y < y_coord for y in y_coords_at_x)   # smaller y
    has_right = any(y > y_coord for y in y_coords_at_x)  # larger y
  
    if has_below and has_above and has_left and has_right:
        covered_count += 1

Pitfall 2: Edge Case with Single Building in Row or Column

The Problem: When there's only one building in a row or column, the sorted list will have length 1. Accessing list[0] and list[-1] will return the same value, making the condition list[0] < coordinate < list[-1] always false.

Example: If building at [3, 5] is the only building in row 3:

• buildings_by_x[3] = [5]
• The check 5 < 5 < 5 is always false

The Solution: Add an explicit check for minimum required buildings:

for x_coord, y_coord in buildings:
    y_coords_at_x = buildings_by_x[x_coord]
    x_coords_at_y = buildings_by_y[y_coord]
  
    # Need at least 3 buildings in each direction to have one covered
    if len(y_coords_at_x) < 3 or len(x_coords_at_y) < 3:
        continue
  
    if (x_coords_at_y[0] < x_coord < x_coords_at_y[-1] and 
        y_coords_at_x[0] < y_coord < y_coords_at_x[-1]):
        covered_count += 1

This optimization also improves performance by skipping unnecessary checks for buildings that cannot possibly be covered.