Prefix Sum & Frequency Maps: The Two Most Important Interview Patterns

Jun 13, 2026 — Aakash Verma

If you ask candidates who have cracked interviews at companies like Amazon, Google, Atlassian, Uber, Microsoft, and Flipkart:

"Which patterns appear repeatedly in coding interviews?"

You'll hear answers like:

Sliding Window
Two Pointers
Binary Search
Dynamic Programming

But before all of those comes something even more fundamental:

Prefix Sum and Frequency Maps

These two techniques solve a surprisingly large number of interview problems.

Many students memorize solutions like:

Two Sum
Subarray Sum Equals K
Contiguous Array
Valid Anagram

without realizing that they all belong to just two core patterns.

This blog will teach you:

What Frequency Maps are
What Prefix Sums are
How to identify them in interviews
Common problem categories
Mistakes beginners make
Example problems
Implementations in Java, C++, Python, and JavaScript

Pattern Recognition > Memorization

Most students prepare like this:

Solved 300 LeetCode problems

Interviewers think:

Can this person identify patterns?

The goal is NOT:

Memorize 500 solutions

The goal is:

Recognize 20 important patterns

Today we will learn two of them.

Pattern #1: Frequency Maps

What is a Frequency Map?

A Frequency Map stores:

Element → Number of Occurrences

Example:

Array:

[1, 2, 1, 3, 2, 1]

Frequency Map:

1 -> 3
2 -> 2
3 -> 1

Why Frequency Maps?

Without a map:

Need nested loops

Example:

Count frequency of each number

Brute Force:

O(n²)

Using HashMap:

O(n)

Huge improvement.

Frequency Map Template

Java

Map<Integer, Integer> freq = new HashMap<>();

for(int num : nums){
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}

C++

unordered_map<int,int> freq;

for(int num : nums){
    freq[num]++;
}

Python

freq = {}

for num in nums:
    freq[num] = freq.get(num, 0) + 1

Javascript

const freq = new Map();

for(const num of nums){
    freq.set(num, (freq.get(num) || 0) + 1);
}

How To Identify Frequency Map Problems?

Whenever you see words like:

frequency
count
occurrence
duplicate
pair
anagram
complement

A HashMap should immediately come to mind.

Interview Clues

Clue 1

Find duplicate elements

Use:

HashSet / HashMap

Clue 2

Count occurrences

Use:

Frequency Map

Clue 3

Find pair with target sum

Think:

HashMap

Clue 4

Check whether two strings contain same characters

Think:

Frequency Map

Problem 1: Two Sum

Given:

nums = [2, 7, 11, 15]
target = 9

Return:

[0,1]

because:

2 + 7 = 9

Brute Force

Check every pair.

O(n²)

Visualization:

2 -> check for 7 in the entire array except itself.
7 -> check for 2 in the entire array except itself.
11 -> check for -2 in the entire array except itself.

Very inefficient.

Observation

While standing at index i:

Need
target - nums[i]

Example:

Current = 7
Need = 2

Can we know whether 2 was seen before?

Yes.

Using a HashMap.

Pattern Identification

Question asks:

Find another element

using information already seen.

That is often:

HashMap Lookup

Java Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];

            if(map.containsKey(diff)) {
                return new int[]{map.get(diff), i};
            }

            map.put(nums[i], i);
        }

        return new int[]{-1, -1};
    }
}

C++ Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;

        for(int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];

            if(mp.find(diff) != mp.end()) {
                return {mp[diff], i};
            }

            mp[nums[i]] = i;
        }

        return {-1, -1};
    }
};

Python Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mp = {}

        for i, num in enumerate(nums):
            diff = target - num

            if diff in mp:
                return [mp[diff], i]

            mp[num] = i

        return [-1, -1]

Javascript Code

var twoSum = function(nums, target) {
    const map = new Map();

    for(let i = 0; i < nums.length; i++) {
        let diff = target - nums[i];

        if(map.has(diff)) {
            return [map.get(diff), i];
        }

        map.set(nums[i], i);
    }

    return [-1, -1];
};

Problem 2: Valid Anagram

Problem

s = "anagram"t = "nagaram"

Output:

true

What Is An Anagram?

Both strings contain:

same characterssame frequencies

Order doesn't matter.

Visualization

anagrama -> 3n -> 1g -> 1r -> 1m -> 1

nagarama -> 3n -> 1g -> 1r -> 1m -> 1

Same frequencies.

Answer:

true

Pattern Identification

Question asks:

How many times does each character appear?

That is the biggest hint for:

Frequency Map

Java Code

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> freqMap = new HashMap<>();

        for(char ch : s.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        for(char ch : t.toCharArray()) {
            if(freqMap.containsKey(ch)) {
                freqMap.put(ch, freqMap.get(ch) - 1);

                if(freqMap.get(ch) == 0) {
                    freqMap.remove(ch);
                }
            } else {
                return false;
            }
        }

        return freqMap.size() == 0;
    }
}

C++ Code

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char,int> freq;

        for(char ch : s) {
            freq[ch]++;
        }

        for(char ch : t) {
            if(freq.find(ch) == freq.end()) {
                return false;
            }

            freq[ch]--;

            if(freq[ch] == 0) {
                freq.erase(ch);
            }
        }

        return freq.empty();
    }
};

Python Code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        freq = {}

        for ch in s:
            freq[ch] = freq.get(ch, 0) + 1

        for ch in t:
            if ch not in freq:
                return False

            freq[ch] -= 1

            if freq[ch] == 0:
                del freq[ch]

        return len(freq) == 0

Javascript Code

var isAnagram = function(s, t) {
    const freq = new Map();

    for(const ch of s) {
        freq.set(ch, (freq.get(ch) || 0) + 1);
    }

    for(const ch of t) {
        if(!freq.has(ch)) {
            return false;
        }

        freq.set(ch, freq.get(ch) - 1);

        if(freq.get(ch) === 0) {
            freq.delete(ch);
        }
    }

    return freq.size === 0;
};

Common Frequency Map Categories

Once you learn Frequency Maps, many problems become similar.

Problem Type	Example
Frequency Counting	Valid Anagram
Duplicate Detection	Contains Duplicate
Pair Finding	Two Sum
Grouping	Group Anagrams
Counting Elements	Top K Frequent Elements
Sliding Window Counting	Permutation in String

Pattern #2: Prefix Sum

While Frequency Maps help us answer questions about elements and their occurrences.

Prefix Sums help us answer questions about subarrays and range sums.

The Problem

Consider the array:

[2, 4, 1, 7, 3]

Suppose you're repeatedly asked:

What is the sum from index L to index R?

A brute-force approach would calculate the sum every time, resulting in O(n) per query.

The Idea

Instead of recalculating sums, we precompute a Prefix Sum Array, where:

prefix[i] = sum of all elements from index 0 to i

For the above array:

Array  : [2, 4, 1, 7, 3]
Prefix : [2, 6, 7, 14, 17]

Formula:

prefix[i] = prefix[i - 1] + nums[i]

Finding Range Sum

Once the prefix array is built, the sum of any subarray from L to R can be calculated in O(1):

RangeSum(L,R) = prefix[R] - prefix[L - 1]

Example:

Array: [2, 4, 1, 7, 3]

Sum from index 1 to 3:
4 + 1 + 7 = 12

Using Prefix Sum:
prefix[3] = 14
prefix[0] = 2

Answer = 14 - 2 = 12

How to Identify Prefix Sum Problems?

Think about Prefix Sum whenever you see:

Subarray Sum
Range Sum Query
Count Subarrays
Longest Subarray
Continuous / Contiguous Array
Sum Equals K
Sum Divisible by K

Interview Pattern

There are two common categories:

1. Prefix Sum Only

Range Sum Query
2D Prefix Sum
Immutable Range Sum
Can You Eat Your Favorite Candy on Your Favorite Day?
Corporate Flight Bookings
Points That Intersect With Cars

2. Prefix Sum + Frequency Map

Subarray Sum Equals K
Contiguous Array
Continuous Subarray Sum
Count of Range Sum

A good rule of thumb:

If the problem talks about subarrays and sums, think Prefix Sum.

If it asks to count, detect, or find previous sums, think Prefix Sum + HashMap.

Prefix Sum & Frequency Maps: The Two Most Important Interview Patterns