Count Overlapping Rectangle Updates on a Grid

Question

The question asks the candidate to devise an algorithm to count overlapping rectangle updates on a grid, where each rectangle is defined by its coordinates.

Codemia · Accepted Answer

To tackle the problem of counting overlapping rectangle updates on a grid, we first need to clarify the input format. Each rectangle is defined by its bottom-left and top-right coordinates. Our goal is to determine how many rectangles overlap at each point in the grid.

We can use a 2D difference array approach to efficiently manage the updates of overlapping rectangles. This technique allows us to mark the start and end of rectangle updates without having to iterate through all cells for each rectangle.

1. Initialize a 2D grid of size (max_x + 1) x (max_y + 1) to zero.
2. For each rectangle defined by (x1, y1) and (x2, y2):
   - Increment grid[x1][y1] by 1 (start of rectangle).
   - Decrement grid[x2][y1] by 1 (end of rectangle horizontally).
   - Decrement grid[x1][y2] by 1 (end of rectangle vertically).
   - Increment grid[x2][y2] by 1 (correct the corner). 
3. Iterate through the grid to compute the prefix sum to get the count of overlaps at each point.

The time complexity of this approach is O(n + m), where n is the number of rectangles and m is the number of cells in the grid. The space complexity is O(max_x * max_y) due to the grid storage.

```python
def count_overlapping_rectangles(rectangles, max_x, max_y):
    grid = [[0] * (max_y + 1) for _ in range(max_x + 1)]
    
    for (x1, y1, x2, y2) in rectangles:
        grid[x1][y1] += 1
        grid[x2][y1] -= 1
        grid[x1][y2] -= 1
        grid[x2][y2] += 1
    
    # Compute the prefix sum
    for x in range(max_x + 1):
        for y in range(1, max_y + 1):
            grid[x][y] += grid[x][y - 1]
    
    for y in range(max_y + 1):
        for x in range(1, max_x + 1):
            grid[x][y] += grid[x - 1][y]
    
    return grid
```

Count Overlapping Rectangle Updates on a Grid

Google

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string