Notes

Arrays & Hashing

Pattern Cheat Sheet

If the problem mentions…	Think about…
duplicates / frequency counts	hashmap / Counter
“have we seen this before?”	hashmap / set
range sums	prefix sums (1D or 2D)
O(n²) brute force	hashing / prefix sums / sorting
grouping	hashmap with a key (often sorted / tuple)
“in place”	two pointers / swapping
max / min profit / score	greedy / running min or max
constant-time queries	preprocessing (prefix, hashmap)
subarray / window	sliding window + hashmap / set
“consecutive” values	set + O(1) lookups

---

How to Think About Array & Hashing Problems

Even when a problem looks complicated, many of them boil down to linear passes over an array plus some kind of auxiliary structure (hashmap, prefix sums, etc.).

You’ll see a lot of:

• Single-pass or two-pass solutions over a 1D list
• Smart use of hashmaps/sets to avoid nested loops
• Sorting to group or order elements
• Simple building blocks reused inside more complex problems

Sorting also shows up frequently, e.g.:

• Merge sort – e.g. “Sort an Array” (LC 912)
• In-place sorts – e.g. “Sort Colors” (LC 75)
• Bucket / counting style approaches – e.g. “Top K Frequent Elements” (LC 347)

---

Core Techniques to Master

These are the main tools you want to be very comfortable with for Arrays & Hashing:

1. Prefix and Suffix Techniques

   • Build prefix sums/products or suffix arrays to answer range queries or avoid recomputation.
   • Example: Product of Array Except Self (LC 238) uses prefix and suffix products instead of division, in O(n) time and O(1) extra space (ignoring output).

2. Hashmaps / Hashsets to Reduce Complexity Use them when you want to:

   • Track counts or frequencies
   • Check membership in O(1) average time
   • Avoid re-scanning the array multiple times

   Classic problems:

   • Contains Duplicate (LC 217) – use a set to detect repeats.
   • Valid Sudoku (LC 36) – hash sets per row/column/box.
   • Group Anagrams (LC 49) – hashmap from a signature (sorted string or letter count) to list of words.
   • Longest Consecutive Sequence (LC 128) – put everything in a set and only start counting from “sequence starts”.

3. Majority Element Patterns

   • Recognize when something appears “more than n/2 times” or “more than n/3 times”.
   • Basic: Majority Element (LC 169) – Boyer–Moore voting algorithm in O(n) time, O(1) space.
   • Variation patterns show up in more advanced problems too.

4. 2D Arrays / Matrices + Prefix Sums

   • Think of a matrix as a 2D extension of array tricks.
   • Precompute a 2D prefix sum to answer submatrix queries in O(1) after O(m·n) preprocessing.
   • Example: Range Sum Query 2D – Immutable (LC 304).

5. Consecutive Sequences

   • Any time the problem says “consecutive integers” or “streaks,” think set + neighbors.

   • Example: Longest Consecutive Sequence (LC 128):

     • Insert all numbers into a set
     • For each number, only expand when num - 1 is not in the set (i.e., it’s the start of a sequence).