2Brute2Best
🔥0

Arrays & Hashing Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Use a hash map or set to remember what you have already seen, so you never search the array twice.

4 sub-patterns · 12 questions

Remember this · Arrays & Hashing
Trigger
"Have I seen X before?", pairs that add up to a target, grouping things that look alike, counting occurrences.
Think
Instead of scanning again for each element, can I remember earlier elements in a map?
Key question
What exactly do I store as the key, and what as the value?
A

What is this pattern?

Arrays & Hashing means remembering what you've already seen in a hash map or hash set, so you never have to scan the array again to find it.

A hash map answers "is X here, and what did I store for it?" in O(1) on average. That one ability turns many O(N²) "for each element, search the rest" solutions into a single O(N) pass.

Every problem in this pattern comes down to one decision: what is the key, and what is the value?

  • Key = the value you'll look for later (the partner in Two Sum), value = its index.
  • Key = a signature that's the same for things that belong together (sorted letters for anagrams), value = the group.
  • Key = the element itself, no value (a set) — just "have I seen it?"
  • Key = what you'll be asked for, value = where it lives in another structure (LRU cache: key → position in a list).

A party host with a guest list. When someone says "I'm here to meet Priya", the host doesn't walk around the room asking everyone — they check the list and point. Writing names down as people arrive costs a little memory, but every later question is answered instantly.

B

See it move

Two Sum with target 9. Each number asks the map for target − number, then adds itself.

Look up the partner before remembering yourselfnums = [8, 3, 11, 5, 7, 2], target = 9step 1/7
nums
0
1
2
3
4
5
8
3
11
5
7
2
value → index
{ }
State
target
9
Map is empty

We walk left to right once. The map remembers every number we've passed and where it was.

Group anagrams. Each word's sorted letters are its key; green cells are already in the same group.

Same key, same groupwords = ["eat", "tea", "tan", "ate", "nat", "bat"]step 1/8
words
0
1
2
3
4
5
eat
tea
tan
ate
nat
bat
key → group
{ }
No groups yet

Anagrams use the same letters, so sorting the letters gives every member of a group the same key.

C

How do I recognise it?

  • "Have I seen this before?" — duplicates, repeats, first unique.

  • "Find two elements that add up / match a target" on an unsorted array, often returning indices.

  • "Group items that are the same in some way" — anagrams, same pattern, same count.

  • "Count how many times each thing appears", or compare two counts.

  • "Design a structure where every operation is O(1)" — caches, randomized sets.

Looks like Arrays & Hashing, but isn't

Two Sum on a **sorted** array
→ Two Pointers

The order already tells you which way to move. Two pointers gives O(1) extra space; a hash map would waste memory.

Count subarrays with sum exactly K
→ Prefix Sum + hash map

It still uses a hash map, but the key is a running total, not an element. The range between two totals is what you count.

Longest substring without repeating characters
→ Sliding Window (with a set or map inside)

The answer is a contiguous range that grows and shrinks. The map only tracks what's inside the window.

Top K most frequent elements
→ Hash map + heap or bucket sort

Counting is hashing, but picking the K largest counts is a separate step that needs a heap or buckets.

D

How would I discover it from scratch?

Don't memorise “use arrays & hashing”. Ask these questions in order — the pattern falls out.

For each element, scan the rest of the array for the thing you need — a partner, a duplicate, an anagram. Two nested loops, O(N²).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Complement lookup

3 questions

For each element, work out the partner it needs and check whether that partner was already seen. Then record the current element for the ones that come later.

02

Grouping by a canonical key

3 questions

Turn each item into a canonical key — a form that's identical for everything in the same group — and bucket by that key.

03

Set membership tricks

3 questions

Put everything into a set first; then each "is X present?" question is O(1). The trick is choosing where to start so nothing is walked twice.

04

Design with hash maps

3 questions

Build a class where every operation is O(1). A hash map alone can find things, but can't keep an order or pick a random element — so pair it with a list or array that can.

F

Don't mix these up

Hash set vs Hash map

Only need "have I seen it?" → set. Need to know where or how many → map (value = index or count).

Two Sum (hash map) vs Two Sum II (two pointers)

Unsorted and you need original indices → hash map. Already sorted → two pointers with O(1) space.

Contains Duplicate vs Contains Duplicate II

Any repeat anywhere → a set. Repeat within distance k → map of value → latest index (or a set of the last k).

LRU cache vs LFU cache

LRU evicts by recency only: one list. LFU evicts by frequency, then recency: one list per frequency plus a minFreq pointer.

G

Code templates (C++)

Complement lookup

Look up before inserting, so an element never pairs with itself. Store whatever the answer needs (index, count, last position).

complement-template.cpp
// For each element, ask: "is the partner I need already seen?"
vector<int> findPair(vector<int>& nums, int target) {
    unordered_map<int, int> seen;          // value -> index where we saw it
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = seen.find(need);         // look up FIRST...
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;                 // ...then remember the current element
    }
    return {};
}

Group by a canonical key

Only the keyOf function changes between problems. Everything that belongs together must produce the same key.

grouping-template.cpp
// Group items that share a canonical key. Only keyOf() changes between problems.
string keyOf(const string& s) {
    int count[26] = {0};
    for (char c : s) count[c - 'a']++;
    string key;
    for (int x : count) key += to_string(x) + '#';  // '#' keeps "1,11" and "11,1" apart
    return key;
}

vector<vector<string>> groupByKey(vector<string>& items) {
    unordered_map<string, vector<string>> groups;
    for (auto& s : items) groups[keyOf(s)].push_back(s);
    vector<vector<string>> result;
    for (auto& [key, group] : groups) result.push_back(group);
    return result;
}

Set: start only at the beginning of a run

The if (!s.count(x - 1)) line is what makes it O(N): each run is walked once, from its first element.

set-run-template.cpp
// Longest run of consecutive values (any order in the array).
int longestRun(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;
    for (int x : s) {
        if (s.count(x - 1)) continue;   // not the start of a run: someone else will count it
        int length = 1;
        while (s.count(x + length)) length++;
        best = max(best, length);
    }
    return best;
}

Map + list (LRU-style design)

The map finds a key in O(1); the list reorders and evicts in O(1). Each covers the other's weakness.

design-template.cpp
// LRU-style cache: the map finds a key in O(1), the list keeps recency order.
class Cache {
    int capacity;
    list<pair<int, int>> order;                               // front = most recent
    unordered_map<int, list<pair<int, int>>::iterator> where; // key -> its node in the list

public:
    Cache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = where.find(key);
        if (it == where.end()) return -1;
        order.splice(order.begin(), order, it->second);  // move to front, O(1)
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = where.find(key);
        if (it != where.end()) {                          // existing key: update + move to front
            it->second->second = value;
            order.splice(order.begin(), order, it->second);
            return;
        }
        if ((int)order.size() == capacity) {              // full: evict the least recent
            where.erase(order.back().first);
            order.pop_back();
        }
        order.emplace_front(key, value);
        where[key] = order.begin();
    }
};
Next
Start with Complement lookup