Tide Aerial View

You are provided a series of aerial-view pictures of the same coastal region, taken a few minutes apart. Each picture consists of an n x n binary grid, where 0 represents land (above water) and 1 represents water (below water).

The tide appears from the left and rises toward the right, so in each row, all 1s will be before all 0s.
Once a region is under water, it stays under water.
All pictures are different.

Determine which picture shows the most even balance between land and water (i.e., where the number of 1s most closely equals the number of 0s). In the event of a tie, return the earliest picture.

Input: An array of n x n grids.

1def bestTidePicture(pictures: List[List[List[int]]]) -> int:
2    def countWater(grid):
3        total = 0
4        for row in grid:
5            # Each row is like [1, 1, 0, 0], finding transition
6            l, r = 0, len(row) - 1
7            idx = -1
8            while l <= r:
9                mid = (l + r) // 2
10                if row[mid] == 1:
11                    idx = mid
12                    l = mid + 1
13                else:
14                    r = mid - 1
15            total += (idx + 1)
16        return total
17
18    n = len(pictures[0])
19    target = (n * n) / 2
20    best_idx = 0
21    min_diff = float('inf')
22    
23    # Binary Search on Time (pictures array)
24    # Because tide rises, water count increases monotonically
25    l, r = 0, len(pictures) - 1
26    while l <= r:
27        mid = (l + r) // 2
28        water = countWater(pictures[mid])
29        diff = abs(water - target)
30        
31        if diff < min_diff:
32            min_diff = diff
33            best_idx = mid
34        elif diff == min_diff:
35            best_idx = min(best_idx, mid)
36            
37        if water < target:
38            l = mid + 1
39        else:
40            r = mid - 1
41            
42    return best_idx

Min Pages Per Day

Visualization for grid is not implemented for this step data.

pictures_count=5

target=4.5

Step 1 / 4

Step 1:

Pictures are sorted by time (water increases). Binary search for 50% water.

Focus: default

pictures_count=5target=4.5