Arrays, Intervals, Sliding Windows, And Prefix Sums

What's being tested

Meta interviewers are probing linear-time array reasoning: transforming arrays without extra passes, counting contiguous ranges with prefix sums, and maintaining interval/window invariants under edge cases. You need to state constraints, choose the right template quickly, and defend O(n) or O(n log n) tradeoffs.

Patterns & templates

• Prefix/suffix products for productExceptSelf — two passes, O(n) time, O(1) extra space excluding output; handle one or multiple zeros.

• Prefix sum + hashmap for target-sum subarrays — maintain count[prefix - k]; initialize {0: 1}; works with negatives unlike sliding window.

• Range-sum precomputation — build prefix[i + 1] = prefix[i] + nums[i]; answer sum(l,r) as prefix[r+1] - prefix[l] in O(1).

• Sliding window for longest transformable consecutive segment — expand right, track violation budget, shrink left until valid; usually O(n).

• Interval gap scan for missing ranges — track previous boundary, compare prev + 1 to curr - 1; guard empty input and integer limits.

• Order statistics for k-th largest — use min-heap size k for O(n log k) or Quickselect average O(n); clarify mutation.

Common pitfalls

Pitfall: Using sliding window for target-sum subarrays when numbers can be negative; use prefix-sum counts instead.

Pitfall: Forgetting boundary sentinels in missing ranges, especially empty arrays, lower, upper, and 32-bit overflow around INT_MIN / INT_MAX.

Pitfall: Claiming O(1) space for productExceptSelf while allocating separate left and right arrays; only the output array may be excluded.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.