</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Search the Answer

What is this?

None of these three problems hands you a sorted array with a target in it. What each does have is a quantity where the answer is a boundary: below some side length every square fits, above it none do; below some start position the window is improvable, above it it is not; below some cumulative sum the draw belongs to an earlier index.

Recognising the boundary is the work. The loop that finds it is the same five lines every time.

What flips exactly once: square side length verified with a 2-D prefix sum, window start position compared via arr[mid] and arr[mid+k], and cumulative sum found as the first prefix greater than the draw

Fun fact: Find K Closest Elements is usually attempted by finding the closest value and expanding outward with two pointers, which is O(log n + k) and perfectly fine. The sharper version binary-searches the window's starting index over the range [0, n − k], comparing x − arr[mid] against arr[mid + k] − x: if the element just past the window is closer than the one at its start, the window must shift right. It searches over positions rather than values, which is the idea worth taking away.

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


Core idea: find the quantity whose predicate flips once (a size, a position, a running total) and binary-search that. The thing being searched is rarely the thing you were handed.


1. Search a size, verify with a prefix sum

Build the 2-D prefix sum once, padded with a zero row and column, so P[i][j] is the sum of the first i rows and j columns:

P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]

def square_sum(i, j, side):                       # bottom-right at P[i][j]
    return P[i][j] - P[i-side][j] - P[i][j-side] + P[i-side][j-side]

The - P[i-1][j-1] in the build and the + P[i-side][j-side] in the query are the same inclusion-exclusion correction: the overlapping corner region is subtracted twice and must be added back once. Padding is what removes every boundary check. Without it, i-1 and j-1 need guarding in four places.

With square_sum costing O(1), feasibility for a given side is one sweep of the grid, and the side length is binary-searched over [0, min(m, n)]. Cells are non-negative, which is what makes feasibility flip only once. The lesson also covers a single-pass O(mn) version that keeps a growing target side while building the table, so the binary search is the clearer first answer and the single pass is the follow-up.

2. Search a position

lo, hi = 0, len(arr) - k                          # candidate window starts
while lo < hi:
    mid = (lo + hi) // 2
    if x - arr[mid] > arr[mid + k] - x:           # the far end is closer → shift right
        lo = mid + 1
    else:
        hi = mid
return arr[lo:lo + k]

The search is O(log(n - k + 1)), and slicing out the k answers adds O(k). That O(k) is the output itself, so extra space beyond the returned slice is O(1).

The comparison is between the element at the window's start and the element just past its end. If dropping the start and gaining the next element is an improvement, the window belongs further right. The > rather than >= is what implements the stated tie-break. On equal distance the smaller value wins, which means keeping the left window.

3. Search a distribution

prefix = list(itertools.accumulate(weights))      # built once, O(n)
target = random.randint(1, prefix[-1])            # inclusive [1, total]
return bisect.bisect_left(prefix, target)         # first cumulative sum >= target

Each index owns a slice of the line whose length is its weight, so a uniform draw lands in it in proportion. Weights are positive, so the prefix array is strictly increasing and the binary search is valid. The draw range and the bisect variant must be paired: integer targets in [1, total] go with bisect_left, while a real draw in [0, total) goes with bisect_right. Each pick costs O(log n) after the O(n) build. If weights change between picks, keep them in a Fenwick tree so both an update and a pick are O(log n).


4. A 30-second worked example (window start)

arr = [1, 2, 3, 4, 5], k = 4, x = 3. Candidate starts are 0 and 1.

Worked window-start trace for arr=[1,2,3,4,5], k=4, x=3: mid=0, both ends are distance 2, 2 > 2 is false so hi=0, giving window arr[0:4]=[1,2,3,4]

The tie is what makes this instructive: both ends are two away, and the specification prefers the smaller values, so the window stays left. Using >= here would shift it right and return [2,3,4,5]. That is the wrong answer, and one that passes every non-tied test.


5. Where you'll actually meet this

  • Image processing. Integral images (summed-area tables) make rectangle sums O(1), and largest-region-under-threshold is this search.
  • Load balancing. Weighted random backend selection is the cumulative-sum draw.
  • A/B allocation. A configured split such as 70/20/10 is three segments on a line.
  • Sorted logs and timelines. "The k entries nearest this timestamp" is the window-start search.

6. Problems in this chapter

Maximum Side Length of a Square with Sum ≤ Threshold

Largest square whose sum stays under a threshold. Binary-search the side length and check feasibility with a padded 2-D prefix sum; a single-pass version drops the log factor.
Pattern: search a size + O(1) region verification. Target: O(mn log(min(m,n))) time with binary search (O(mn) single pass), O(mn) space.

Find K Closest Elements

The k values closest to x, in ascending order. Binary-search the window's start over [0, n-k], comparing the element at the start against the one just past the end.
Pattern: search a position. Target: O(log(n-k+1) + k) time, O(k) output space and O(1) beyond it.

Random Pick with Weight

Draw an index with probability proportional to its weight. Build prefix sums once, then binary-search a uniform draw. Fenwick tree is the follow-up when weights change.
Pattern: search a distribution. Target: O(n) build, O(log n) per pick, O(n) space.


7. Common pitfalls

  • Getting the inclusion-exclusion sign wrong. The corner is subtracted twice and must be added back once, in both the build and the query.
  • Not padding the prefix table, which forces boundary checks in four places and invites off-by-one errors.
  • Using >= in the window comparison. The tie-break says prefer the smaller values, which means keeping the left window.
  • Searching over [0, n] for the window start. The range is [0, n − k], or the slice runs off the end.
  • Mixing up the draw range and the bisect variant in the weighted pick. Integer targets in [1, total] pair with bisect_left; a real draw in [0, total) pairs with bisect_right. The wrong pairing skews the distribution at segment edges.
  • Rebuilding the cumulative sums per draw. Build once in the constructor.
  • Drawing 0 with randint(0, total), which would give index 0 an extra value and skew the odds.

8. Key takeaways

  1. Binary search needs a predicate that flips once, not an array and not a target.
  2. Search sizes, positions and totals, not only values.
  3. A padded 2-D prefix sum makes any rectangle query O(1) and removes all the boundary cases.
  4. Compare the two ends of a candidate window to decide which way it must move.
  5. Cumulative sums turn a uniform draw into a weighted one, so binary search is used to generate rather than to find.
  6. Tie-breaks are part of the specification, and here one comparison operator implements the whole rule.
  7. Why interviewers like it: none of these announce themselves as binary search, so spotting the monotonic boundary is the entire signal.

Order: Maximum Side Length of a Square with Sum ≤ Threshold → Find K Closest Elements → Random Pick with Weight.

Find K Closest Elements

Core idea: The k closest elements in a sorted array always form one contiguous window of length k. So the problem reduces to one question: where does that window start? You binary-search the window's left edge by comparing the distances of the two elements just outside its ends.

Problem, rephrased

Your metrics store keeps sensor samples sorted by timestamp. When an alert fires, the on-call dashboard shows the readings taken nearest that moment. You're given a sorted (ascending) integer array arr of sample timestamps, an integer k (how many samples to show) and an integer x (the instant the alert fired, which may fall before the first sample or after the last).

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.