Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 225 ยท Arrays and Lists

Classic Array Problems: Rain Water, Two-Array Median, Rotations

Master three classic array interview problems in Python: trapping rain water three ways, the median of two sorted arrays in O(log n) and rotated arrays.

Some array problems appear in interviews so often that they deserve their own lesson. Each one has a slow, obvious solution and a clever fast one, and each teaches a transferable technique: precomputing from both ends, binary searching on a partition instead of a value, and using reversal to rotate in place.

In this lesson you will solve trapping rain water (prefix and suffix maxima, then a two-pointer version with O(1) memory, then a stack), find the median of two sorted arrays in O(log(min(n, m))), and handle rotations: rotate an array in place, find the minimum of a rotated sorted array, and search in one. Every solution is checked against a brute force. You should know two pointers, prefix sums and binary search.

Trapping rain water

Bars of given heights stand side by side, each with width 1. After rain, how many units of water are held between them?

TEXT
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]   ->   6 units

The key observation: the water above bar i has height min(max_left, max_right) - height[i], where max_left and max_right are the tallest bars at or on each side of i. If that is negative, there is no water there.

flowchart LR
  A["For each bar i"] --> B["left = tallest bar from 0 to i"]
  A --> C["right = tallest bar from i to end"]
  B --> D["water at i = min(left, right) - height[i]"]
  C --> D

The lower of the two walls decides the water level.

Approach 1: brute force and prefix arrays

Recomputing the two maxima for every bar is O(n^2). Precompute them once with prefix and suffix maximum arrays: O(n) time and O(n) memory.

Python Trapping rain water: brute force vs prefix maxima

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Approach 2: two pointers in O(1) memory

We do not need both full arrays. Keep pointers lo and hi plus the running maxima left_max and right_max. Look at the smaller of h[lo] and h[hi]. If h[lo] < h[hi], the right wall is at least as tall as h[hi] > h[lo], so the water above lo depends only on left_max: settle lo and move it right. Otherwise settle hi the same way. Each step moves a pointer, so time is O(n) and extra space O(1).

Python Two-pointer rain water

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Approach 3: a monotonic stack

Another view fills water layer by layer. Keep a stack of indexes with decreasing heights. When a bar h[i] is taller than the bar on top of the stack, the top is a basin floor, bounded on the left by the new top and on the right by i. Its water is (min(h[left], h[i]) - h[floor]) * (i - left - 1). This is the idea from monotonic stacks, also O(n).

Python Stack version of rain water

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Median of two sorted arrays

Given two sorted arrays a and b, find the median of all elements together. Merging takes O(n + m). The classic challenge is O(log(min(n, m))).

The idea: the median splits the combined elements into a left half and a right half of equal size (the left one bigger by one if the total is odd), where every element on the left is <= every element on the right. We choose how many elements i of a go left; then j = (n + m + 1) // 2 - i of b go left. A split is valid when

TEXT
a[i-1] <= b[j]   and   b[j-1] <= a[i]

Binary search on i over the shorter array. If a[i-1] > b[j], we took too many from a: move left. If b[j-1] > a[i], we took too few: move right. Use -inf and +inf sentinels for out-of-range indexes.

Once found, the median is max(a[i-1], b[j-1]) for an odd total, or the average of that and min(a[i], b[j]) for an even total.

Python Median of two sorted arrays in O(log min(n, m))

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each step halves the search range over the shorter array, so the time is O(log(min(n, m))) and extra space is O(1). The related idea of binary searching on the answer is covered in binary search variants, and a similar partition trick powers quickselect and partitioning.

Rotations

A rotated sorted array is a sorted array whose front part was moved to the back: [4, 5, 6, 7, 0, 1, 2]. Three common tasks follow.

Rotate an array in place

Rotate right by k positions without extra memory using three reversals: reverse the whole array, then reverse the first k elements, then the remaining n - k. Each element is touched twice: O(n) time, O(1) space. Always reduce k modulo n first.

Python In-place rotation by reversal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Find the minimum in a rotated sorted array

Binary search compares arr[mid] with arr[hi]. If arr[mid] > arr[hi], the minimum is to the right of mid. Otherwise it is at mid or to its left. With distinct values the loop is O(log n).

Search a target in a rotated array

At each step at least one half [lo..mid] or [mid..hi] is sorted. Find which one, check if the target lies in its range, and discard the other half. Also O(log n) with distinct values. (With duplicates the worst case degrades to O(n), because arr[lo] == arr[mid] == arr[hi] hides which side is sorted.)

Python Minimum and search in a rotated array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four more array classics

These four problems appear often in exercise sets. Each one has an obvious O(nยฒ) or worse solution and a neat fix built from a tool you have already met.

Surpasser counts

A surpasser of arr[i] is an element to its right that is strictly larger. For [2, 7, 5, 3, 0, 8, 1] the surpasser counts are [4, 1, 1, 1, 2, 0, 0]. Counting directly is O(nยฒ). Compress the values to ranks, then sweep from the right with a Fenwick tree that counts how many values seen so far are larger. Each step is O(log n), so the total is O(n log n). (A modified merge sort works too.)

Maximum occurring point in ranges

You get ranges [l, r] (inclusive) and want the integer that lies in the most ranges. Add +1 at l and -1 at r + 1 in a difference array, then take a running sum: the prefix value at x is the number of ranges covering x. See prefix sums for the idea. With coordinates up to M the cost is O(n + M); for huge coordinates use a dictionary of events and sort its keys (a mini sweep line).

Counting triangles

How many triples of numbers can be the sides of a non-degenerate triangle? Three lengths a <= b <= c work if a + b > c. Sort the array, then fix the largest side c = arr[k] and use two pointers on the prefix arr[0..k-1]: if arr[i] + arr[j] > arr[k] then every index from i to j - 1 pairs with j, which adds j - i triangles at once. The total is O(nยฒ) instead of O(nยณ).

Maximum of sum(i * arr[i]) over rotations

Let R_k be the value of sum(i * arr[i]) after rotating the array k positions. Rotating by one more step moves the last element from index n - 1 to index 0, and every other element's index grows by 1:

R_(k+1) = R_k + total_sum - n * (the element that wrapped around)

So you compute R_0 in O(n), then every other rotation in O(1), for O(n) overall.

Python Surpassers, busiest point, triangles and rotation sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which technique when?

Problem Technique Time Space
Trapping rain water prefix and suffix maxima O(n) O(n)
Trapping rain water two pointers O(n) O(1)
Median of two sorted arrays binary search on the partition O(log min(n, m)) O(1)
Rotate array by k three reversals O(n) O(1)
Min or search in rotated array modified binary search O(log n) O(1)
Surpasser counts Fenwick tree over ranks O(n log n) O(n)
Most-covered point difference array O(n + M) O(M)
Counting triangles sort + two pointers O(nยฒ) O(1)
Max sum of i * arr[i] over rotations recurrence between rotations O(n) O(1)

Common mistakes: forgetting to reduce k modulo n, off-by-one errors in the partition index j = (n + m + 1) // 2 - i (it makes the left half the larger one for odd totals), running the partition search over the longer array (the index j can go negative), and trying the rotated-array searches on arrays with duplicates without checking the problem statement.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How much water sits above bar i in the rain-water problem?

    The shorter of the two surrounding walls sets the water level, and the bar itself takes up the bottom part.
  2. 2. In the two-pointer version, why can we settle the left bar when h[lo] < h[hi]?

    The right wall is at least h[hi], which exceeds h[lo]. Therefore the water level above lo is determined by left_max alone.
  3. 3. Why does the median-of-two-arrays binary search run on the shorter array?

    If a is the longer one, half - i can become negative or exceed the length of b, and the search takes more steps.
  4. 4. Which sequence of reversals rotates an array right by k?

    Reversing the whole array puts the last k elements first, but backwards; reversing the first k and the rest then restores their order.

Summary

  • Rain water above a bar is min(left max, right max) - height; solve it with prefix and suffix maxima, two pointers (O(1) space) or a monotonic stack, all O(n).
  • The median of two sorted arrays comes from binary searching a partition of the shorter array, in O(log min(n, m)).
  • Rotate in place with three reversals after reducing k modulo n.
  • Rotated sorted arrays admit O(log n) minimum and search by deciding which half is sorted (distinct values).
  • Check every clever solution against a brute force on random small inputs.

Next: Matrices