You need to find the length of the longest contiguous subarray with a sum at most K in an array of positive integers. Which technique is most appropriate?
ABinary search on the answer, because the subarray length can be searched directly
BSliding window, because positive integers create a monotonic relationship between window size and sum
CConverging two pointers, because you need to sort the array first
DBrute force O(n²), because subarrays have no exploitable structure
Sliding window works here because positive integers give monotonicity: expanding the window (moving right pointer right) can only increase the sum; contracting it (moving left pointer right) can only decrease it. This one-directional relationship means each pointer decision permanently eliminates states, making O(n) possible. Without this monotonic structure — for example, if the array contained negative numbers — the sliding window would not apply and brute force or prefix sums would be needed.
Question 2 Multiple Choice
In a sliding window, both the left and right pointers visit each element, so each element is processed twice. Why does this give O(n) rather than O(n²) time complexity?
AIt is actually O(n log n) — the O(n) claim is an approximation
BElements processed by the left pointer are cheaper, so the average cost is O(1) per element
CBoth pointers only move forward, so across the entire run each traverses the array at most once — 2n total steps
DThe window size is bounded by a constant, so the inner loop cost is O(1)
The critical invariant: neither pointer ever moves backward. The right pointer advances from index 0 to n−1 (n steps total). The left pointer advances from index 0 to at most n−1 (n steps total). No matter how many expand-contract cycles occur, the total work is at most 2n steps, giving O(n). In a naive nested loop the inner index can restart from any position — allowing O(n²) work. The monotonic forward movement is what prevents revisiting past states.
Question 3 True / False
The two-pointer technique can be applied to find a pair of elements that sum to a target in any array of integers, regardless of whether the array is sorted.
TTrue
FFalse
Answer: False
False. The converging two-pointer technique requires a sorted array (or a monotonic structure). When you move the left pointer right, you need to know this increases the sum — ruling out smaller left values. In an unsorted array, moving left forward might increase or decrease the sum unpredictably, so you cannot safely eliminate states. Without monotonicity the technique degenerates to brute force. Sorting first then applying two pointers is valid, but the sorted order is what makes the technique work.
Question 4 True / False
In the sliding window pattern, the left pointer may need to move backward in some cases to restore a violated invariant.
TTrue
FFalse
Answer: False
False. The left pointer only ever moves forward — this is non-negotiable. Moving it backward would reintroduce previously removed elements and break the O(n) guarantee by potentially creating an infinite loop. When the window's invariant is violated, you advance the left pointer (shrink the window) until the invariant is restored. This one-directional movement is precisely what ensures each element is visited at most twice, keeping the algorithm linear.
Question 5 Short Answer
What is the key structural property that makes two pointers or sliding window applicable to a problem, and why does this property allow you to avoid revisiting past states?
Think about your answer, then reveal below.
Model answer: The key property is monotonicity: moving a pointer in a given direction has a predictable, one-directional effect on the quantity being optimized or the condition being checked. Because each pointer decision unambiguously moves the quantity in one direction, any state 'behind' the pointer can be permanently ruled out — it cannot be part of an optimal answer that the current state does not already account for.
Without monotonicity, a pointer decision might need to be undone (moving backward), which eliminates the linear-time guarantee. With monotonicity, each step eliminates an entire region of the search space. In a sorted two-sum, moving the left pointer forward can only increase the sum — all pairs with the old left value are definitively handled. In a sliding window, expanding can only add to the aggregate. This structural guarantee transforms O(n²) into O(n).