DSA · Lesson 2 of 17

Arrays, Hashing & Prefix Sums

⏱ 15 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 9 practice problems

Hash maps and sets turn “search the whole array” into O(1) lookups. Prefix sums answer any range-sum question in O(1).

The idea

An array gives O(1) access by index but O(n) search by value. A hash map (Python dict, Java HashMap, C++ unordered_map, JS Map) stores key → value pairs with average O(1) insert and lookup. A hash set is the same without values.

Most “Easy/Medium array” interview problems become linear once you ask: what would I like to look up instantly?

When to reach for a hash map

“Have I seen this before?” → set (duplicates, cycles, visited states)
“Where did I see it?” → map value → index (Two Sum)
“How many times?” → map value → count (anagrams, top-k, majority)
“Group things that are equivalent” → map canonical key → list (group anagrams: key = sorted word)

Prefix sums

Store prefix[i] = a[0] + … + a[i−1]. Then the sum of a[i..j] is prefix[j+1] − prefix[i]: one subtraction instead of a loop.

Combine prefix sums with a hash map to count subarrays with a target sum: a subarray (i, j] sums to k exactly when prefix[j] − prefix[i] = k, so for each prefix you count how many earlier prefixes equal prefix − k. Unlike sliding window, this works with negative numbers.

Code template

from collections import defaultdict

# Hash map: value -> index (Two Sum pattern)
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

# Prefix sums + counting (subarray sum = k)
def count_subarrays(nums, k):
    count, prefix = 0, 0
    seen = defaultdict(int, {0: 1})
    for x in nums:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

// Hash map: value -> index (Two Sum pattern)
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[]{j, i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

// Prefix sums + counting (subarray sum = k)
int countSubarrays(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>(Map.of(0, 1));
    int count = 0, prefix = 0;
    for (int x : nums) {
        prefix += x;
        count += seen.getOrDefault(prefix - k, 0);
        seen.merge(prefix, 1, Integer::sum);
    }
    return count;
}

// Hash map: value -> index (Two Sum pattern)
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        auto it = seen.find(target - nums[i]);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

// Prefix sums + counting (subarray sum = k)
int countSubarrays(vector<int>& nums, int k) {
    unordered_map<int, int> seen{{0, 1}};
    int count = 0, prefix = 0;
    for (int x : nums) { prefix += x; count += seen[prefix - k]; seen[prefix]++; }
    return count;
}

// Hash map: value -> index (Two Sum pattern)
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (seen.has(target - nums[i])) return [seen.get(target - nums[i]), i];
    seen.set(nums[i], i);
  }
}

// Prefix sums + counting (subarray sum = k)
function countSubarrays(nums, k) {
  const seen = new Map([[0, 1]]);
  let count = 0, prefix = 0;
  for (const x of nums) {
    prefix += x;
    count += seen.get(prefix - k) || 0;
    seen.set(prefix, (seen.get(prefix) || 0) + 1);
  }
  return count;
}

Complexity

Operation	Array	Hash map / set
Access by index	O(1)	—
Search by value	O(n)	O(1) average
Insert / delete	O(n) (middle), O(1) (end)	O(1) average
Ordered iteration	yes	no (use a TreeMap / sorted structure)

Practise this pattern (9 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
1	Two Sum	Easy
2	Contains Duplicate	Easy
3	Valid Anagram	Easy
4	Majority Element	Easy
5	Group Anagrams	Medium
6	Top K Frequent Elements	Medium
7	Product of Array Except Self	Medium
8	Longest Consecutive Sequence	Medium
9	Subarray Sum Equals K	Medium

Common mistakes

Using a list for membership tests inside a loop (O(n²)). Use a set.
Mutable keys: in Python, use a tuple, not a list, as a dict key.
Forgetting seen[0] = 1 (the empty prefix) when counting subarray sums.
In Java, comparing Integer objects with == above 127. Use .equals, or unbox first.

Check yourself: why does sliding window fail for “subarray sum equals k” with negative numbers?

With negatives, extending the window can make the sum smaller, so you can no longer decide whether to grow or shrink. Prefix sums with a hash map do not depend on monotonicity.

Check yourself: what key groups “eat”, “tea” and “ate” together?

The sorted letters “aet”, or the 26-letter count vector.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar