Array And String Algorithms

What's being tested

These problems test linear array/string scanning, pointer discipline, and choosing the right optimization pattern instead of brute force. Expect to recognize monotonic stacks, sliding windows, interval sorting, bounded-range extrema, and in-place partitioning, then explain correctness and O(n) or O(n log n) complexity clearly.

Patterns & templates

• Monotonic stack for next-smaller-or-equal discounts — O(n) time, stack of candidate indices; watch equality semantics and rightward-only constraints.

• Sliding window for shortest constrained substring — expand right, update counts, contract left while valid; O(n) with a frequency map.

• Bounded max/min window using deque — maintain candidates in decreasing/increasing order; expire indices outside window before computing profit.

• Interval merge template — sort by start, track current [start,end], merge when next.start <= current.end; costs O(n log n).

• Dutch National Flag partitioning — three pointers low, mid, high; sort three categories in-place in O(n) time and O(1) space.

• Invariant-first coding — state what each pointer/stack/deque represents before writing loops; this prevents off-by-one and stale-index bugs.

• Complexity tradeoff — hash maps and stacks usually give O(n) extra space; interval sorting dominates unless input is already sorted.

Common pitfalls

Pitfall: Treating “smaller” as strictly smaller when the discount rule requires smaller-or-equal changes answers on duplicate prices.

Pitfall: Shrinking a sliding window only once per right pointer often misses the shortest valid substring; contract in a while loop.

Pitfall: In three-way partitioning, incrementing mid after swapping with high skips an unclassified element.

Practice these

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