Arrays, Sliding Windows, DP And Stack Patterns

What's being tested

These problems test array invariants, monotonic stacks, sliding windows, and dynamic programming under tight time constraints. Interviewers are probing whether you can turn a brute-force scan over subarrays or future elements into an O(n) or near-O(n) solution with correct edge-case handling.

Patterns & templates

• Prefix invariant for permutations — track max_so_far; prefix 0..i forms 1..k iff max_so_far == i + 1, assuming valid permutation input.

• Monotonic stack for next smaller/equal element — maintain increasing stack of indices; pop while prices[top] >= prices[i]; O(n) time, O(n) space.

• Sliding window with frequencies — expand right, update pair count by freq[x]; contract left while condition still holds; count many subarrays at once.

• Identical-pair counting — adding value x creates freq[x] new pairs; removing it deletes freq[x] - 1; avoid recomputing combinations.

• At least k subarrays — when window [l..r] satisfies condition, all extensions to the right also satisfy it, contributing n - r.

• Dynamic programming for constrained jumps — define dp[i] as paths to position i; transition from allowed jump sizes; use modulo arithmetic consistently.

• Prime preprocessing — generate primes ending in 3 using Sieve of Eratosthenes up to max jump/position; avoid primality checks inside nested loops.

Common pitfalls

Pitfall: Using sum(freq[v] choose 2) after every pointer move turns an intended O(n) sliding window into O(n * distinct).

Pitfall: For final prices, using strictly smaller instead of smaller-or-equal changes correctness on duplicate prices.

Pitfall: In DP counting, forgetting mod = 1_000_000_007 during each addition can overflow in languages like Java or C++.

Practice these

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