Arrays & Hashing
Two pointers, prefix sums, intervals, line sweep and Kadane.
11 notes · 59 min total
Questions0 of 90 done
Warm up with these before Phase 1.
Patterns
- 1Hash Map & Set Basics: Count, Look Up, GroupUse a set or dict to remember what you've seen: duplicates, complements, frequency counts, grouping keys and composite keys, each in one pass.5 min
- 2Two Pointers: Opposite Ends & kSumStart one pointer at each end of a sorted array and let one comparison per step decide which end moves; extend it to 3Sum and kSum.6 min
- 3Two Pointers: Read/Write & Cyclic SortModify an array in place with a read pointer that scans and a write pointer that marks where the next kept value goes, plus cyclic sort.5 min
- 4Two Pointers on Two SequencesWalk one pointer through each of two sequences to merge, intersect, or check a subsequence, and know which pointer to advance.4 min
- 5Prefix Sum + HashmapCount subarrays with a target sum, remainder or parity by keeping a running state and a hashmap of the states you've already seen.6 min
- 6Prefix/Suffix Aggregates & 2D Prefix SumPrecompute what lies left and right of each index for any associative operation, and answer rectangle sums in O(1) with 2D prefix sums.6 min
- 7Difference ArrayApply many range updates in O(1) each by marking only where each update starts and stops, then rebuild the array with one prefix sum.4 min
- 8Line SweepTurn intervals into sorted start and end events, sweep once with a running state, and pick the tie-break for touching intervals.6 min
- 9Intervals: Choose the Sort KeyMost interval problems come down to the sort key: start to merge, end to schedule, start then end descending to find covers.5 min
- 10Kadane & Running-State DPFind the best contiguous subarray by choosing to extend or restart at each index, then add states for min, coupon and alternating variants.7 min
- 11Classic Array TricksFour one-idea tricks: Boyer-Moore voting, the Dutch national flag, rotation by reversal, and O(1) delete by swapping with the last.5 min