Top K Frequent Elements

🎯

Top K Frequent Elements

mediumHASH_MAPFacebookAmazonGoogle

Imagine you are analyzing a large dataset of user actions and want to quickly find the most common actions performed.

💡 This problem is about counting how often each element appears and then efficiently retrieving the top K elements by frequency. Beginners often struggle because they try to sort the entire dataset or don't know how to efficiently track frequencies and retrieve top elements.

📋

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4k is in the range [1, the number of unique elements in the array]

💡

Example

Input"nums = [1,1,1,2,2,3], k = 2"

Output[1,2]

1 appears 3 times, 2 appears 2 times, 3 appears once. The top 2 frequent elements are 1 and 2.

• All elements are the same → return that element
• k equals number of unique elements → return all elements
• Array with negative and positive numbers → handle negative keys correctly
• k equals 1 and multiple elements have same frequency → return any one of the top frequent

⚠️

Common Mistakes

Sorting the entire nums array instead of unique elements

Leads to incorrect results and unnecessary overhead

✅ Sort only the unique elements based on frequency

Using max-heap instead of min-heap for top k elements

Heap size grows unnecessarily, increasing time complexity

✅ Use a min-heap of size k to keep only top k frequent elements

Not handling the case when multiple elements have the same frequency

Output may be inconsistent or incorrect

✅ Accept any order or clarify with interviewer; bucket sort naturally groups ties

Forgetting to check if k is valid or equals number of unique elements

May cause index errors or incomplete results

✅ Validate k and handle edge cases explicitly

Using inefficient sorting or heap operations on large inputs

Solution times out or is too slow

✅ Use bucket sort or min-heap approach for better performance

🧠

Brute Force (Frequency Counting + Sorting Entire Array)

💡 This approach exists to build intuition by directly counting frequencies and sorting all elements by frequency, which is straightforward but inefficient for large inputs.

Intuition

Count how many times each element appears, then sort all unique elements by their frequency in descending order, and pick the top k.

Algorithm

1. Count the frequency of each element using a hash map.
2. Extract the unique elements into a list.
3. Sort the list based on frequency in descending order.
4. Return the first k elements from the sorted list.

💡 Sorting all unique elements by frequency is easy to understand but can be slow if there are many unique elements.

</>

Code

from typing import List

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    unique = list(freq.keys())
    unique.sort(key=lambda x: freq[x], reverse=True)
    return unique[:k]

# Driver code
if __name__ == '__main__':
    print(topKFrequent([1,1,1,2,2,3], 2))  # Output: [1, 2]

Line Notes

freq = {}Initialize a dictionary to count frequencies of elements

for num in nums:Iterate over each number to build frequency map

freq[num] = freq.get(num, 0) + 1Increment frequency count for current number

unique = list(freq.keys())Extract unique elements to a list for sorting

unique.sort(key=lambda x: freq[x], reverse=True)Sort unique elements by their frequency in descending order

return unique[:k]Return the top k frequent elements

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        List<Integer> unique = new ArrayList<>(freq.keySet());
        unique.sort((a, b) -> freq.get(b) - freq.get(a));
        return unique.subList(0, k);
    }

    public static void main(String[] args) {
        System.out.println(topKFrequent(new int[]{1,1,1,2,2,3}, 2)); // Output: [1, 2]
    }
}

Line Notes

Map<Integer, Integer> freq = new HashMap<>();Create a map to store frequency counts

for (int num : nums)Iterate over input array to count frequencies

freq.put(num, freq.getOrDefault(num, 0) + 1);Update frequency count for each number

List<Integer> unique = new ArrayList<>(freq.keySet());Get list of unique elements

unique.sort((a, b) -> freq.get(b) - freq.get(a));Sort unique elements by frequency descending

return unique.subList(0, k);Return top k frequent elements

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    vector<int> unique;
    for (auto& p : freq) {
        unique.push_back(p.first);
    }
    sort(unique.begin(), unique.end(), [&](int a, int b) {
        return freq[a] > freq[b];
    });
    unique.resize(k);
    return unique;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Output: 1 2
    return 0;
}

Line Notes

unordered_map<int, int> freq;Use hash map to count frequencies efficiently

for (int num : nums)Iterate over input to build frequency map

freq[num]++;Increment frequency count for each element

vector<int> unique;Store unique elements for sorting

sort(unique.begin(), unique.end(), [&](int a, int b)Sort unique elements by frequency descending

unique.resize(k);Keep only top k elements after sorting

function topKFrequent(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    const unique = Array.from(freq.keys());
    unique.sort((a, b) => freq.get(b) - freq.get(a));
    return unique.slice(0, k);
}

// Test
console.log(topKFrequent([1,1,1,2,2,3], 2)); // Output: [1, 2]

Line Notes

const freq = new Map();Initialize a Map to count frequencies

for (const num of nums)Iterate over input array to build frequency map

freq.set(num, (freq.get(num) || 0) + 1);Increment frequency count for current number

const unique = Array.from(freq.keys());Extract unique elements for sorting

unique.sort((a, b) => freq.get(b) - freq.get(a));Sort unique elements by frequency descending

return unique.slice(0, k);Return the top k frequent elements

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Counting frequencies takes O(n). Sorting unique elements takes O(m log m), where m is number of unique elements, up to n. Overall O(n log n) in worst case.

💡 For n=100,000, sorting all unique elements can be very slow, so this approach is not efficient for large inputs.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large inputs, so we need better methods.

🧠

Better Approach (Frequency Map + Min-Heap)

💡 This approach improves efficiency by using a min-heap to keep track of the top k frequent elements without sorting all unique elements.

Intuition

Count frequencies, then maintain a min-heap of size k to store the top k elements by frequency. This avoids sorting all elements.

Algorithm

1. Count the frequency of each element using a hash map.
2. Create a min-heap to store elements by frequency.
3. Iterate over frequency map, push elements into the heap.
4. If heap size exceeds k, pop the smallest frequency element.
5. After processing all, extract elements from heap as result.

💡 Using a min-heap keeps only the top k frequent elements, reducing sorting overhead.

</>

Code

from typing import List
import heapq

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for count, num in heap]

# Driver code
if __name__ == '__main__':
    print(topKFrequent([1,1,1,2,2,3], 2))  # Output: [2, 1]

Line Notes

freq = {}Initialize frequency dictionary

for num in nums:Count frequency of each number

heap = []Initialize min-heap to track top k elements

heapq.heappush(heap, (count, num))Push current element with frequency into heap

if len(heap) > k:If heap exceeds size k, remove smallest frequency element

return [num for count, num in heap]Extract elements from heap as result

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
            Comparator.comparingInt(Map.Entry::getValue));
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            heap.offer(entry);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!heap.isEmpty()) {
            res.add(heap.poll().getKey());
        }
        Collections.reverse(res); // Reverse to match descending frequency order
        return res;
    }

    public static void main(String[] args) {
        System.out.println(topKFrequent(new int[]{1,1,1,2,2,3}, 2)); // Output: [1, 2]
    }
}

Line Notes

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

for (int num : nums)Count frequencies

PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(...)Min-heap based on frequency

heap.offer(entry);Add entry to heap

if (heap.size() > k)Maintain heap size at most k

while (!heap.isEmpty())Extract top k elements from heap

Collections.reverse(res);Reverse result to get descending frequency order

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    // Comparator for min-heap by frequency
    auto cmp = [&](pair<int,int>& a, pair<int,int>& b) { return a.first > b.first; };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> heap(cmp);
    for (auto& p : freq) {
        heap.push({p.second, p.first});
        if ((int)heap.size() > k) heap.pop();
    }
    vector<int> res;
    while (!heap.empty()) {
        res.push_back(heap.top().second);
        heap.pop();
    }
    reverse(res.begin(), res.end()); // Reverse to get descending frequency order
    return res;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Output: 1 2
    return 0;
}

Line Notes

unordered_map<int, int> freq;Count frequencies using hash map

auto cmp = [&](pair<int,int>& a, pair<int,int>& b)Comparator for min-heap by frequency

priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> heap(cmp);Min-heap to keep top k frequent elements

heap.push({p.second, p.first});Push frequency and element pair into heap

if ((int)heap.size() > k) heap.pop();Pop smallest frequency if heap size exceeds k

while (!heap.empty())Extract elements from heap for result

reverse(res.begin(), res.end());Reverse result to get descending frequency order

function topKFrequent(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    const heap = [];
    const pushHeap = (pair) => {
        heap.push(pair);
        heap.sort((a, b) => a[0] - b[0]);
        if (heap.length > k) heap.shift();
    };
    for (const [num, count] of freq.entries()) {
        pushHeap([count, num]);
    }
    return heap.map(pair => pair[1]);
}

// Test
console.log(topKFrequent([1,1,1,2,2,3], 2)); // Output: [2, 1]

Line Notes

const freq = new Map();Initialize frequency map

for (const num of nums)Count frequencies

const heap = [];Use array as min-heap substitute

heap.push(pair);Add frequency-element pair to heap

heap.sort((a, b) => a[0] - b[0]);Sort heap to maintain min-heap property

if (heap.length > k) heap.shift();Remove smallest frequency element if heap too big

return heap.map(pair => pair[1]);Extract elements from heap as result

⏱

Complexity

TimeO(n log k)

SpaceO(n)

Counting frequencies is O(n). Each insertion into heap is O(log k), done for m unique elements, so O(m log k). Since m ≤ n, total O(n log k).

💡 For n=100,000 and k=10, this is much faster than sorting all elements.

Interview Verdict: Accepted and efficient for large inputs

This approach balances speed and simplicity, suitable for most interview scenarios.

🧠

Optimal Approach (Bucket Sort)

💡 This approach uses bucket sort to achieve linear time complexity by grouping elements by frequency, avoiding sorting or heap operations.

Intuition

Since frequency ranges from 1 to n, create buckets where index represents frequency and each bucket holds elements with that frequency. Then iterate buckets from high to low frequency to collect top k elements.

Algorithm

1. Count frequency of each element using a hash map.
2. Create an array of buckets where index is frequency, each bucket holds elements with that frequency.
3. Place each element into its corresponding frequency bucket.
4. Iterate buckets from highest frequency to lowest, collecting elements until k are collected.
5. Return the collected elements.

💡 Bucket sort leverages the limited frequency range to avoid expensive sorting or heap operations.

</>

Code

from typing import List

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    max_freq = max(freq.values())
    buckets = [[] for _ in range(max_freq + 1)]
    for num, count in freq.items():
        buckets[count].append(num)
    res = []
    for i in range(max_freq, 0, -1):
        for num in buckets[i]:
            res.append(num)
            if len(res) == k:
                return res
    return res

# Driver code
if __name__ == '__main__':
    print(topKFrequent([1,1,1,2,2,3], 2))  # Output: [1, 2]

Line Notes

freq = {}Initialize frequency dictionary

for num in nums:Count frequency of each element

max_freq = max(freq.values())Find maximum frequency to size buckets

buckets = [[] for _ in range(max_freq + 1)]Create buckets indexed by frequency

buckets[count].append(num)Place element in bucket corresponding to its frequency

for i in range(max_freq, 0, -1)Iterate buckets from highest frequency down

if len(res) == k:Stop when k elements collected

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int maxFreq = Collections.max(freq.values());
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= maxFreq; i++) {
            buckets.add(new ArrayList<>());
        }
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            buckets.get(entry.getValue()).add(entry.getKey());
        }
        List<Integer> res = new ArrayList<>();
        for (int i = maxFreq; i >= 1 && res.size() < k; i--) {
            for (int num : buckets.get(i)) {
                res.add(num);
                if (res.size() == k) return res;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(topKFrequent(new int[]{1,1,1,2,2,3}, 2)); // Output: [1, 2]
    }
}

Line Notes

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

int maxFreq = Collections.max(freq.values());Find max frequency for bucket size

List<List<Integer>> buckets = new ArrayList<>();Create buckets indexed by frequency

buckets.get(entry.getValue()).add(entry.getKey());Add element to corresponding frequency bucket

for (int i = maxFreq; i >= 1 && res.size() < k; i--)Iterate buckets from high to low frequency

if (res.size() == k) return res;Return once k elements collected

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    int maxFreq = 0;
    for (auto& p : freq) {
        maxFreq = max(maxFreq, p.second);
    }
    vector<vector<int>> buckets(maxFreq + 1);
    for (auto& p : freq) {
        buckets[p.second].push_back(p.first);
    }
    vector<int> res;
    for (int i = maxFreq; i >= 1 && (int)res.size() < k; i--) {
        for (int num : buckets[i]) {
            res.push_back(num);
            if ((int)res.size() == k) return res;
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Output: 1 2
    return 0;
}

Line Notes

unordered_map<int, int> freq;Count frequencies

int maxFreq = 0;Track maximum frequency

vector<vector<int>> buckets(maxFreq + 1);Create buckets indexed by frequency

buckets[p.second].push_back(p.first);Add element to bucket for its frequency

for (int i = maxFreq; i >= 1 && (int)res.size() < k; i--)Iterate buckets from high to low frequency

if ((int)res.size() == k) return res;Return once k elements collected

function topKFrequent(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    const maxFreq = Math.max(...freq.values());
    const buckets = Array.from({length: maxFreq + 1}, () => []);
    for (const [num, count] of freq.entries()) {
        buckets[count].push(num);
    }
    const res = [];
    for (let i = maxFreq; i > 0 && res.length < k; i--) {
        for (const num of buckets[i]) {
            res.push(num);
            if (res.length === k) return res;
        }
    }
    return res;
}

// Test
console.log(topKFrequent([1,1,1,2,2,3], 2)); // Output: [1, 2]

Line Notes

const freq = new Map();Count frequencies

const maxFreq = Math.max(...freq.values());Find maximum frequency

const buckets = Array.from({length: maxFreq + 1}, () => []);Create buckets indexed by frequency

buckets[count].push(num);Add element to bucket for its frequency

for (let i = maxFreq; i > 0 && res.length < k; i--)Iterate buckets from high to low frequency

if (res.length === k) return res;Return once k elements collected

⏱

Complexity

TimeO(n)

SpaceO(n)

Counting frequencies is O(n). Creating buckets and iterating them is O(n) since total elements are n. No sorting or heap operations needed.

💡 For n=100,000, this approach is very fast and scalable.

Interview Verdict: Accepted and optimal

This is the best approach in terms of time complexity and is recommended if you can implement it correctly.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (min-heap) or 3 (bucket sort) is preferred for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n)	O(n)	No	N/A	Mention only - never code
2. Min-Heap	O(n log k)	O(n)	No	N/A	Good balance of efficiency and simplicity
3. Bucket Sort	O(n)	O(n)	No	N/A	Optimal approach if comfortable implementing

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice all approaches. Start with brute force to build intuition, then improve efficiency step-by-step.

How to Present

Clarify the problem and constraints with the interviewer.State the brute force approach: count frequencies and sort all elements.Discuss its inefficiency and propose using a min-heap to track top k.Finally, explain the bucket sort approach for optimal linear time.Code the chosen approach carefully and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to count frequencies, choose appropriate data structures (hash map, heap, buckets), and optimize time complexity.

Common Follow-ups

• What if k equals the number of unique elements? → Return all elements sorted by frequency.
• How to handle ties in frequency? → Any order is acceptable unless specified.

💡 Follow-ups often test your understanding of edge cases and output ordering requirements.

🔍

Pattern Recognition

When to Use

1) Need to find most frequent elements; 2) Frequency counting is possible; 3) Output top k elements; 4) Efficient retrieval of top frequencies required.

Signature Phrases

top k frequent elementsmost common elementsfrequency of elements

NOT This Pattern When

Problems asking for kth largest element without frequency or sorting entire array

Similar Problems

Top K Frequent Words - similar frequency counting with stringsSort Characters By Frequency - frequency sorting of characters

Practice

1. Consider the following Python function to detect duplicates. What is the value of the variable seen after processing the third element in the input [2, 4, 2, 5]?

easy

A. {4, 2}

B. {2, 4, 2}

C. {2, 4, 5}

D. {2, 4}

Solution

1. Step 1: Trace the loop iterations

   After first element (2), seen = {2}. After second element (4), seen = {2, 4}. After third element (2), since 2 is already in seen, the function returns True before adding anything new.

2. Step 2: Determine seen after third element

   Because the function returns immediately upon detecting duplicate, seen remains {2, 4} at that point.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Duplicate detected at third element, no new additions after second iteration [OK]

Hint: Function returns immediately on duplicate, so seen stops growing [OK]

Common Mistakes:

• Assuming duplicate is added again to set
• Confusing order of insertion
• Misreading when return occurs

2. You are given an integer array and a target integer k. You need to determine if there exists a continuous subarray of at least length 2 whose sum is a multiple of k (including zero). Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to extend subarrays until sum is divisible by k

B. Sorting the array and using two pointers to find subarrays summing to multiples of k

C. Dynamic programming that stores sums of all subarrays explicitly

D. Prefix sum combined with a hash map tracking remainders modulo k

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking sums of continuous subarrays for divisibility by k, which suggests prefix sums and modular arithmetic.

2. Step 2: Identify the approach that efficiently tracks prefix sums modulo k

   Using a hash map to store the earliest index of each remainder allows O(n) detection of subarrays with sums divisible by k.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + remainder hash map is the classic optimal approach [OK]

Hint: Prefix sums + remainder hash map solves this optimally [OK]

Common Mistakes:

• Thinking greedy can find all valid subarrays
• Trying to sort array breaks continuous subarray property
• Using DP to store all subarray sums causes O(n^2) time

3. Consider the following Python function to check if two strings are isomorphic:

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    s_to_t = {}
    t_to_s = {}
    for c1, c2 in zip(s, t):
        if c1 in s_to_t:
            if s_to_t[c1] != c2:
                return False
        else:
            s_to_t[c1] = c2
        if c2 in t_to_s:
            if t_to_s[c2] != c1:
                return False
        else:
            t_to_s[c2] = c1
    return True

print(isIsomorphic("egg", "add"))

What is the output of this code?

easy

A. True

B. None

C. Raises an exception

D. False

Solution

1. Step 1: Trace first iteration with c1='e', c2='a'

   Both maps are empty, so s_to_t['e'] = 'a' and t_to_s['a'] = 'e'.

2. Step 2: Trace second and third iterations

   Second iteration: c1='g', c2='d', maps updated similarly. Third iteration: c1='g' already maps to 'd', and c2='d' maps back to 'g', so no conflict.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mapping is consistent for all characters, so returns True [OK]

Hint: Check mapping consistency at each iteration [OK]

Common Mistakes:

• Confusing output with 'foo' and 'bar'
• Assuming length mismatch causes exception

4. What is the time complexity of the optimal prefix sum + hash map solution for counting subarrays summing to k in an array of length n?

medium

A. O(n log n) due to hash map lookups

B. O(n) because each element is processed once with O(1) average hash map operations

C. O(n²) because prefix sums require nested loops to check subarrays

D. O(n) for prefix sums plus O(n) for nested loops, total O(n²)

Solution

1. Step 1: Identify loops and operations

   The algorithm iterates over the array once (O(n)) and performs constant-time hash map operations on average.

2. Step 2: Analyze hash map operations

   Hash map lookups and inserts are O(1) average, so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with O(1) map ops -> O(n) time [OK]

Hint: Hash map average O(1) lookups keep complexity linear [OK]

Common Mistakes:

• Assuming hash map lookups are O(log n)
• Confusing prefix sums with nested loops
• Counting nested loops inside prefix sums

5. Suppose the problem is modified so that the array can contain negative numbers and k can be zero. Which modification to the prefix sum + hash map approach correctly handles this variant?

hard

A. Use prefix sums without modulo and store sums in a hash map to detect repeated sums for k=0

B. Normalize k to positive and use modulo as usual, ignoring zero k case

C. Skip modulo operations entirely and check if any subarray sum equals zero when k=0

D. Replace hash map with a balanced tree to handle negative sums and zero k

Solution

1. Step 1: Understand that modulo by zero is undefined

   When k=0, modulo operations cannot be used; must check sums equal zero directly.

2. Step 2: Use prefix sums and hash map of sums (not modulo) to detect repeated sums indicating zero-sum subarray

   This approach correctly handles negative numbers and zero k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Detect repeated prefix sums for zero k to find zero-sum subarrays [OK]

Hint: For k=0, detect repeated prefix sums without modulo [OK]

Common Mistakes:

• Applying modulo when k=0 causing errors
• Ignoring negative numbers in modulo computations
• Using data structures that don't support negative sums efficiently