roadmap/Arrays & Hashing

Topic 1 / 16

Arrays & Hashing

BeginnerFoundation~5 days
Beginner friendly
progress0 / 15 solved

The backbone of every interview. Master frequency maps, prefix sums, and index tricks.

Concept

Arrays store elements in contiguous memory — O(1) random access, O(n) search. Hash maps (objects/Maps in JS) give O(1) average lookup, insert, and delete. Together they power the majority of Easy and Medium interview problems. The key insight: trading space for time by caching values you've already seen.

When to use this pattern
  • ◆Two-sum style problems: find a pair/triple with a target
  • ◆Counting frequency of elements
  • ◆Detecting duplicates or unique elements
  • ◆Building prefix sums for range queries
  • ◆Grouping elements by some property (anagram grouping)
Common patterns
Frequency map
Count occurrences; compare character/element counts.
Prefix sum
Pre-compute cumulative sums; answer range queries in O(1).
Two-sum complement lookup
Store seen values in a set; check for (target - current).
Index as implicit map
When values are bounded [0..n], use the array index itself as a hashmap.
Brute force → optimal thinking
Brute force
Try every pair with nested loops → O(n²) time, O(1) space.
Observation
For each element x, we only need to know if (target - x) exists. We've seen it or we haven't.
Optimization
Single pass: store each element in a HashMap. For each new element, check if its complement is already in the map.
Final complexity
O(n) time, O(n) space — the classic time-space tradeoff.
Quick Recall Check

What is the time complexity of a HashMap lookup?

Which technique solves Two Sum in a single pass?

What does a prefix sum array let you compute in O(1)?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

next
Two Pointers
→
Progress is saved on this device