Coding: Greedy, Interval, Counting, And Grid Patterns

What's being tested

Candidates must recognize and implement common greedy choices, manipulate intervals efficiently, use counting/hashmap patterns, and traverse grids reliably. Interviewers probe pattern recognition, correctness proofs for greedy steps, coordinate compression for large ranges, and robust BFS/DFS/grid bookkeeping under time/space constraints.

Patterns & templates

• Interval scheduling — sort intervals by end time, pick non-overlapping greedily; O(n log n) for sort, O(1) per pick; justify by exchange argument.

• Sweep-line / event sorting — convert intervals to start/end events, sort, then accumulate active count using heapq or Counter; good for max-overlap and k-coverage.

• Prefix-sum / difference array — apply +1/−1 at endpoints then prefix-sum; O(n + U) where U is compressed coordinate size; use coordinate compression for large domains.

• Counting with hashmap — defaultdict(int) / Counter for frequency, complements, grouping; O(n) expected time, watch memory if keys are high-cardinality.

• Grid BFS/DFS — use deque for BFS, mark visited in-place or with boolean grid, iterate 4/8 directions via direction array; avoid recursion for large grids.

• Greedy correctness mindset — state invariant, identify local optimal substructure, show exchange or counterexample for alternatives; highlight matroid-like constraints when present.

Common pitfalls

Pitfall: Confusing inclusive/exclusive interval endpoints — always clarify whether intervals are [start,end), [start,end], or points-based.

Pitfall: Allocating a difference array with raw coordinates — forget coordinate compression and blow memory for sparse large ranges.

Pitfall: Using recursive DFS on a ~10^5 cell grid — recursion depth will likely overflow; prefer iterative stack/BFS with deque.