Smaller Values Downstream
HardArrays & Hashing
Problem
Water-quality stations along a river report pollution levels levels, listed from upstream to downstream. For each station, the analysts want to know how many stations downstream of it (to its right) report a strictly lower level.
Return the array counts where counts[i] is that number for station i.
Example 1
- Input:
- levels = [5, 2, 6, 1]
- Output:
- [2, 1, 1, 0]
Downstream of 5 are 2 and 1 (lower) and 6 (not).
Example 2
- Input:
- levels = [-1]
- Output:
- [0]
Example 3
- Input:
- levels = [-1, -1]
- Output:
- [0, 0]
Equal levels do not count.
Constraints
- 1 ≤ levels.length ≤ 10^5
- -10^4 ≤ levels[i] ≤ 10^4
Hint
Show the first hint
Comparing each station with all downstream ones is O(n²). Which algorithm naturally compares left elements with right elements in bulk?
Walkthrough
How to approach it
01Clarify before coding
- Strictly lower? Yes, equal levels do not count.
- Is the output per original position? Yes, counts[i] belongs to station i, so the sort must track original indices.
- Size? Up to 10^5, so O(n²) is about 5 · 10^9 comparisons: too slow.
02Brute force
For every i, scan j > i and count levels[j] < levels[i].
Cost: O(n²) time, O(1) extra space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.