Array Tricks

What is this?

Each of these looks like it needs to try every possibility, and each is one pass with one or two counters. The recurring move is to ask what a single scan could accumulate that makes the answer obvious at every position — the number of flips needed if the boundary were here, the size of the gap ending here, how many people fall into a given age bucket.

💡 Fun fact: Friends of Appropriate Ages has up to 20,000 people and looks quadratic — but ages are bounded to 1–120. Bucketing by age turns "every pair of people" into "every pair of ages", which is at most 120 × 120 = 14,400 combinations regardless of population, with the counts supplying the multiplication. Whenever a problem bounds a value far below the number of items, that bound is an invitation to count by value instead of by item.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: find the quantity a single left-to-right pass can maintain so that the answer at every position is immediate — a running count, a gap length, or a tally by value rather than by item.

1. A running count that decides a boundary

A monotone string is some 0s followed by some 1s, so the answer is the best place to draw the boundary. At any position, the flips needed are (the 1s to the left, which must become 0s) plus (the 0s to the right, which must become 1s). One pass maintains both implicitly:

ones = flips = 0
for ch in s:
    if ch == '1':
        ones += 1              # a 1 here is free if the boundary is after it
    else:
        flips = min(flips + 1, ones)   # flip this 0, or flip every 1 seen so far
return flips

The min is the whole algorithm. Either you keep this 0 and pay to flip it, or you decide the boundary is behind you and pay to flip all the 1s instead — and you never need to know where the boundary actually is.

2. The gaps, and the edges

The best empty seat is in the middle of the largest interior gap — but the first and last runs behave differently, because a run of empty seats at either end is not surrounded on both sides:

Forgetting the edge runs is the standard failure, and both are needed: an array like [1,0,0,0] has its answer at the end, not in a middle gap.

3. Bucket by value when the range is small

count = [0] * 121                       # ages 1..120
for age in ages:
    count[age] += 1

total = 0
for a in range(1, 121):
    for b in range(1, 121):
        if request_allowed(a, b):        # the problem's three conditions
            total += count[a] * count[b] - (count[a] if a == b else 0)

The a == b correction removes self-requests: within one age bucket there are c × (c − 1) ordered pairs, not c × c.

4. A 30-second worked example (Flip String to Monotone Increasing)

s = "00110"

ch   ones   flips
0     0     min(0+1, 0) = 0        keep as 0, nothing to flip
0     0     min(0+1, 0) = 0
1     1     0                       a 1 after 0s is free
1     2     0
0     2     min(0+1, 2) = 1         flip this 0 → cheaper than flipping two 1s
                                          answer = 1

The final min chooses between flipping this single 0 (cost 1) and flipping the two 1s before it (cost 2). One flip gives "00111", which is monotone ✓.

5. Where you'll actually meet this

• Data cleaning. Minimum edits to make a sequence monotone appears in sensor smoothing and validation.
• Seating and allocation. Placing a new item to maximise distance from existing ones — table seating, base-station siting, load spreading.
• Demographic and matching analytics. Bucketed pairwise counting is how any large matching or eligibility calculation is actually done.
• Histogram statistics. Whenever a value range is far smaller than the item count, counting by value is the standard optimisation.
• Threshold detection. Running counters that decide a boundary in one pass, over streams.

6. Problems in this chapter

▶ Flip String to Monotone Increasing

Minimum flips to make a binary string monotone. Track the 1s seen and take min(flips + 1, ones) at each 0.
Pattern: running-count boundary decision. Target: O(n) time, O(1) space.

▶ Maximize Distance to Closest Person

Best seat given occupied seats. Largest interior gap gives (g + 1) // 2; leading and trailing runs give g.
Pattern: gap scan with edge cases. Target: O(n) time, O(1) space.

▶ Friends of Appropriate Ages

Count friend requests under three age conditions. Bucket by age and count pairs of buckets.
Pattern: bucket by a bounded value. Target: O(n + 120²) time, O(120) space.

7. Common pitfalls 🚫

• Trying every boundary position. O(n²) when a running min decides it in one pass.
• Missing the edge runs. Empty seats at the start or end give distance g, not (g+1)//2.
• Rounding the interior gap wrong. (g + 1) // 2 — check it against a gap of 3, where the answer is 2.
• Comparing every pair of people. The age bound is the hint; bucket instead.
• Counting self-requests. Within one age bucket the count is c × (c − 1).
• Assuming at least one occupied seat. The problem guarantees it, but say that you checked.
• Allocating 20,000 buckets instead of 121. Size the array by the value range, not the input length.

8. Key takeaways

1. Ask what one pass can maintain so the answer is immediate everywhere.
2. A min of two running costs replaces searching for a boundary.
3. Edges behave differently from the middle in every gap problem.
4. A small value range means bucket by value, and the pair count becomes bucket arithmetic.
5. Correct for self-pairs when both items come from the same bucket.
6. Read the constraints for the trick. "Ages are 1 to 120" is the whole hint.
7. Why interviewers like it: the quadratic solution is immediate, so the entire signal is whether you spot the accumulator or the bound that removes it.

Order: Flip String to Monotone Increasing → Maximize Distance to Closest Person → Friends of Appropriate Ages.