20 Must-Know HashMap Questions for DSA Interviews

BY: coding_error1

\ 1. Two Sum

Problem: Find indices of two numbers that add up to a target.

Python

python
CopyEdit
def twoSum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
if target - num in hashmap:
return [hashmap[target - num], i]
hashmap[num] = i

C++

cpp
CopyEdit
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if(map.count(complement)) return {map[complement], i};
map[nums[i]] = i;
}
return {};
}

Java

java
CopyEdit
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[0];
}

2. Check for Anagram

Problem: Check if two strings are anagrams.

BY: coding_error1
Python

python
CopyEdit
def isAnagram(s, t):
return sorted(s) == sorted(t)

C++

cpp
CopyEdit
bool isAnagram(string s, string t) {
if (s.length() != t.length()) return false;
int count[26] = {0};
for (char c : s) count[c - 'a']++;
for (char c : t) if (--count[c - 'a'] < 0) return false;
return true;
}

Java

java
CopyEdit
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
for (char c : t.toCharArray()) if (--count[c - 'a'] < 0) return false;
return true;
}

3. First Non-Repeating Character

Problem: Return index of first non-repeating character.

Python

python
CopyEdit
from collections import Counter
def firstUniqChar(s):
count = Counter(s)
for i, c in enumerate(s):
if count[c] == 1:
return i
return -1

C++

cpp
CopyEdit
int firstUniqChar(string s) {
unordered_map<char, int> count;
for (char c : s) count[c]++;
for (int i = 0; i < s.length(); i++)

BY: coding_error1
 if (count[s[i]] == 1) return i;
return -1;
}

Java

java
CopyEdit
public int firstUniqChar(String s) {
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) count.put(c, count.getOrDefault(c, 0) +
1);
for (int i = 0; i < s.length(); i++)
if (count.get(s.charAt(i)) == 1) return i;
return -1;
}

4. Majority Element

Problem: Find the element that appears more than ⌊n / 2⌋ times.

Python

python
CopyEdit
def majorityElement(nums):
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
if count[num] > len(nums) // 2:
return num

C++

cpp
CopyEdit
int majorityElement(vector<int>& nums) {
unordered_map<int, int> freq;
for (int num : nums) {
freq[num]++;
if (freq[num] > nums.size() / 2) return num;
}
return -1;
}

Java

java
CopyEdit
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (map.get(num) > nums.length / 2) return num;
}
return -1;
}

BY: coding_error1
 5. Group Anagrams

Problem: Group words that are anagrams.

Python

python
CopyEdit
from collections import defaultdict
def groupAnagrams(strs):
res = defaultdict(list)
for word in strs:
key = tuple(sorted(word))
res[key].append(word)
return list(res.values())

C++

cpp
CopyEdit
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (string s : strs) {
string key = s;
sort(key.begin(), key.end());
map[key].push_back(s);
}
vector<vector<string>> res;
for (auto& pair : map) res.push_back(pair.second);
return res;
}

Java

java
CopyEdit
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}

6. Longest Consecutive Sequence

Problem: Find the length of the longest consecutive elements sequence.

Python

BY: coding_error1
python
CopyEdit
def longestConsecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set:
current = num
streak = 1
while current + 1 in num_set:
current += 1
streak += 1
longest = max(longest, streak)
return longest

C++

cpp
CopyEdit
int longestConsecutive(vector<int>& nums) {
unordered_set<int> set(nums.begin(), nums.end());
int maxLen = 0;
for (int num : set) {
if (!set.count(num - 1)) {
int curr = num, len = 1;
while (set.count(curr + 1)) {
curr++;
len++;
}
maxLen = max(maxLen, len);
}
}
return maxLen;
}

Java

java
CopyEdit
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
int longest = 0;
for (int num : set) {
if (!set.contains(num - 1)) {
int current = num, streak = 1;
while (set.contains(current + 1)) {
current++;
streak++;
}
longest = Math.max(longest, streak);
}
}
return longest;
}

7. Isomorphic Strings

BY: coding_error1
 Problem: Determine if two strings follow the same pattern.

Python

python
CopyEdit
def isIsomorphic(s, t):
s_map, t_map = {}, {}
for a, b in zip(s, t):
if s_map.get(a, b) != b or t_map.get(b, a) != a:
return False
s_map[a], t_map[b] = b, a
return True

C++

cpp
CopyEdit
bool isIsomorphic(string s, string t) {
unordered_map<char, char> map1, map2;
for (int i = 0; i < s.size(); i++) {
if (map1.count(s[i]) && map1[s[i]] != t[i]) return false;
if (map2.count(t[i]) && map2[t[i]] != s[i]) return false;
map1[s[i]] = t[i];
map2[t[i]] = s[i];
}
return true;
}

Java

java
CopyEdit
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map1 = new HashMap<>();
Map<Character, Character> map2 = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c1 = s.charAt(i), c2 = t.charAt(i);
if (map1.containsKey(c1) && map1.get(c1) != c2) return false;
if (map2.containsKey(c2) && map2.get(c2) != c1) return false;
map1.put(c1, c2);
map2.put(c2, c1);
}
return true;
}

8. Find Duplicate Number

Problem: Return the duplicate number in an array.

Python

python
CopyEdit
def findDuplicate(nums):

BY: coding_error1
 seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)

C++

cpp
CopyEdit
int findDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int num : nums) {
if (seen.count(num)) return num;
seen.insert(num);
}
return -1;
}

Java

java
CopyEdit
public int findDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)) return num;
}
return -1;
}

9. Subarray Sum Equals K

Problem: Count subarrays with sum exactly K.

Python

python
CopyEdit
def subarraySum(nums, k):
count = 0
prefix_sum = 0
hashmap = {0: 1}
for num in nums:
prefix_sum += num
count += hashmap.get(prefix_sum - k, 0)
hashmap[prefix_sum] = hashmap.get(prefix_sum, 0) + 1
return count

C++

cpp
CopyEdit
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> map;
map[0] = 1;

BY: coding_error1
 int count = 0, sum = 0;
for (int num : nums) {
sum += num;
count += map[sum - k];
map[sum]++;
}
return count;
}

Java

java
CopyEdit
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int count = 0, sum = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}

10. Intersection of Two Arrays

Problem: Return intersection elements (unique).

Python

python
CopyEdit
def intersection(nums1, nums2):
return list(set(nums1) & set(nums2))

C++

cpp
CopyEdit
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end()), result;
for (int num : nums2)
if (set1.count(num)) result.insert(num);
return vector<int>(result.begin(), result.end());
}

Java

java
CopyEdit
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int num : nums1) set1.add(num);
Set<Integer> result = new HashSet<>();
for (int num : nums2)

BY: coding_error1
 if (set1.contains(num)) result.add(num);
return result.stream().mapToInt(Integer::intValue).toArray();
}

11. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

Python

python
CopyEdit
def lengthOfLongestSubstring(s):
seen = {}
left = max_len = 0
for right, char in enumerate(s):
if char in seen and seen[char] >= left:
left = seen[char] + 1
seen[char] = right
max_len = max(max_len, right - left + 1)
return max_len

C++

cpp
CopyEdit
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> seen;
int left = 0, maxLen = 0;
for (int right = 0; right < s.size(); ++right) {
if (seen.count(s[right]) && seen[s[right]] >= left)
left = seen[s[right]] + 1;
seen[s[right]] = right;
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}

Java

java
CopyEdit
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c) && map.get(c) >= left)
left = map.get(c) + 1;
map.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}

12. Count Distinct Elements in Every Window

BY: coding_error1
 Problem: Given an array and a window size K, count distinct elements in each window.

Python

python
CopyEdit
from collections import defaultdict
def countDistinct(arr, k):
freq = defaultdict(int)
res = []
for i in range(len(arr)):
freq[arr[i]] += 1
if i >= k:
freq[arr[i - k]] -= 1
if freq[arr[i - k]] == 0:
del freq[arr[i - k]]
if i >= k - 1:
res.append(len(freq))
return res

C++

cpp
CopyEdit
vector<int> countDistinct(int arr[], int n, int k) {
unordered_map<int, int> freq;
vector<int> res;
for (int i = 0; i < n; ++i) {
freq[arr[i]]++;
if (i >= k) {
freq[arr[i - k]]--;
if (freq[arr[i - k]] == 0)
freq.erase(arr[i - k]);
}
if (i >= k - 1)
res.push_back(freq.size());
}
return res;
}

Java

java
CopyEdit
public List<Integer> countDistinct(int[] arr, int k) {
Map<Integer, Integer> freq = new HashMap<>();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
if (i >= k) {
freq.put(arr[i - k], freq.get(arr[i - k]) - 1);
if (freq.get(arr[i - k]) == 0)
freq.remove(arr[i - k]);
}
if (i >= k - 1)
res.add(freq.size());
}
return res;
}

BY: coding_error1
 13. Word Pattern Matching

Problem: Check if a word pattern matches a string.

Python

python
CopyEdit
def wordPattern(pattern, s):
words = s.split()
if len(words) != len(pattern): return False
char_map, word_map = {}, {}
for c, w in zip(pattern, words):
if char_map.get(c, w) != w or word_map.get(w, c) != c:
return False
char_map[c] = w
word_map[w] = c
return True

C++

cpp
CopyEdit
bool wordPattern(string pattern, string s) {
istringstream iss(s);
vector<string> words;
string word;
while (iss >> word) words.push_back(word);
if (words.size() != pattern.size()) return false;

unordered_map<char, string> pmap;

unordered_map<string, char> smap;

for (int i = 0; i < pattern.size(); i++) {

if (pmap.count(pattern[i]) && pmap[pattern[i]] != words[i])
return false;
if (smap.count(words[i]) && smap[words[i]] != pattern[i])
return false;
pmap[pattern[i]] = words[i];
smap[words[i]] = pattern[i];
}
return true;
}

Java

java
CopyEdit
public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
if (pattern.length() != words.length) return false;

Map<Character, String> charMap = new HashMap<>();

Map<String, Character> wordMap = new HashMap<>();

BY: coding_error1
 for (int i = 0; i < pattern.length(); i++) {
char c = pattern.charAt(i);
String w = words[i];
if (charMap.containsKey(c) && !charMap.get(c).equals(w)) return
false;
if (wordMap.containsKey(w) && wordMap.get(w) != c) return false;
charMap.put(c, w);
wordMap.put(w, c);
}
return true;
}

14. Top K Frequent Elements

Problem: Return the k most frequent elements.

Python

python
CopyEdit
from collections import Counter
import heapq
def topKFrequent(nums, k):
count = Counter(nums)
return [item for item, freq in count.most_common(k)]

C++

cpp
CopyEdit
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;
priority_queue<pair<int, int>> pq;
for (auto& [num, count] : freq) pq.push({count, num});
vector<int> res;
while (k--) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}

Java

java
CopyEdit
public 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>> pq =
new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

pq.addAll(freq.entrySet());
List<Integer> result = new ArrayList<>();

BY: coding_error1
 while (k-- > 0) result.add(pq.poll().getKey());
return result;
}

15. Longest Palindrome by Character Count

Problem: Build the longest palindrome from character counts.

Python

python
CopyEdit
from collections import Counter
def longestPalindrome(s):
count = Counter(s)
length = 0
odd_found = False
for freq in count.values():
length += (freq // 2) * 2
if freq % 2: odd_found = True
return length + 1 if odd_found else length

C++

cpp
CopyEdit
int longestPalindrome(string s) {
unordered_map<char, int> count;
for (char c : s) count[c]++;
int length = 0;
bool odd = false;
for (auto& [ch, freq] : count) {
length += (freq / 2) * 2;
if (freq % 2) odd = true;
}
return length + odd;
}

Java

java
CopyEdit
public int longestPalindrome(String s) {
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) count.put(c, count.getOrDefault(c, 0) +
1);
int length = 0;
boolean odd = false;
for (int freq : count.values()) {
length += (freq / 2) * 2;
if (freq % 2 == 1) odd = true;
}
return length + (odd ? 1 : 0);
}

16. Minimum Window Substring

BY: coding_error1
 Problem: Find the minimum window in s which will contain all the characters in t.

Python

python
CopyEdit
from collections import Counter
def minWindow(s, t):
if not s or not t: return ""
t_count = Counter(t)
start = 0
min_len = float('inf')
min_start = 0
window = {}
have, need = 0, len(t_count)
l = 0
for r in range(len(s)):
c = s[r]
window[c] = window.get(c, 0) + 1
if c in t_count and window[c] == t_count[c]:
have += 1
while have == need:
if (r - l + 1) < min_len:
min_len = r - l + 1
min_start = l
window[s[l]] -= 1
if s[l] in t_count and window[s[l]] < t_count[s[l]]:
have -= 1
l += 1
return s[min_start:min_start+min_len] if min_len != float('inf') else
""

C++

cpp
CopyEdit
string minWindow(string s, string t) {
unordered_map<char, int> tmap, window;
for (char c : t) tmap[c]++;
int have = 0, need = tmap.size();
int l = 0, minLen = INT_MAX, start = 0;

for (int r = 0; r < s.size(); r++) {

window[s[r]]++;
if (tmap.count(s[r]) && window[s[r]] == tmap[s[r]])
have++;
while (have == need) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
start = l;
}
window[s[l]]--;
if (tmap.count(s[l]) && window[s[l]] < tmap[s[l]])
have--;
l++;
}
}
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

BY: coding_error1
Java

java
CopyEdit
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";

Map<Character, Integer> tmap = new HashMap<>();

for (char c : t.toCharArray()) tmap.put(c, tmap.getOrDefault(c, 0) +
1);

Map<Character, Integer> window = new HashMap<>();

int have = 0, need = tmap.size(), l = 0;
int minLen = Integer.MAX_VALUE, start = 0;

for (int r = 0; r < s.length(); r++) {

char c = s.charAt(r);
window.put(c, window.getOrDefault(c, 0) + 1);
if (tmap.containsKey(c) && window.get(c).equals(tmap.get(c)))
have++;

while (have == need) {

if (r - l + 1 < minLen) {
minLen = r - l + 1;
start = l;
}
char lc = s.charAt(l);
window.put(lc, window.get(lc) - 1);
if (tmap.containsKey(lc) && window.get(lc) < tmap.get(lc))
have--;
l++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start +
minLen);
}

17. Find All Anagrams in a String

Problem: Return all start indices of p's anagrams in s.

Python

python
CopyEdit
from collections import Counter
def findAnagrams(s, p):
res = []
p_count = Counter(p)
s_count = Counter()
for i in range(len(s)):
s_count[s[i]] += 1
if i >= len(p):
if s_count[s[i - len(p)]] == 1:
del s_count[s[i - len(p)]]
else:
s_count[s[i - len(p)]] -= 1

BY: coding_error1
 if s_count == p_count:
res.append(i - len(p) + 1)
return res

C++

cpp
CopyEdit
vector<int> findAnagrams(string s, string p) {
vector<int> res;
if (s.size() < p.size()) return res;
unordered_map<char, int> pmap, smap;
for (char c : p) pmap[c]++;
for (int i = 0; i < s.size(); i++) {
smap[s[i]]++;
if (i >= p.size()) {
smap[s[i - p.size()]]--;
if (smap[s[i - p.size()]] == 0)
smap.erase(s[i - p.size()]);
}
if (smap == pmap) res.push_back(i - p.size() + 1);
}
return res;
}

Java

java
CopyEdit
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s.length() < p.length()) return res;

Map<Character, Integer> pmap = new HashMap<>();

for (char c : p.toCharArray()) pmap.put(c, pmap.getOrDefault(c, 0) +
1);

Map<Character, Integer> smap = new HashMap<>();

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
smap.put(c, smap.getOrDefault(c, 0) + 1);

if (i >= p.length()) {
char toRemove = s.charAt(i - p.length());
if (smap.get(toRemove) == 1)
smap.remove(toRemove);
else
smap.put(toRemove, smap.get(toRemove) - 1);
}

if (smap.equals(pmap)) res.add(i - p.length() + 1);

}
return res;
}

18. Count Pairs with Given Sum

BY: coding_error1
 Problem: Count pairs in array with sum = K.

Python

python
CopyEdit
def countPairs(arr, k):
count = 0
freq = {}
for num in arr:
count += freq.get(k - num, 0)
freq[num] = freq.get(num, 0) + 1
return count

C++

cpp
CopyEdit
int countPairs(vector<int>& arr, int k) {
unordered_map<int, int> freq;
int count = 0;
for (int num : arr) {
count += freq[k - num];
freq[num]++;
}
return count;
}

Java

java
CopyEdit
public int countPairs(int[] arr, int k) {
Map<Integer, Integer> freq = new HashMap<>();
int count = 0;
for (int num : arr) {
count += freq.getOrDefault(k - num, 0);
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
return count;
}

19. Copy List with Random Pointer

Problem: Deep copy a linked list where each node has a random pointer.

Python

python
CopyEdit
def copyRandomList(head):
if not head: return None
old_to_new = {}
curr = head
while curr:

BY: coding_error1
 old_to_new[curr] = Node(curr.val)
curr = curr.next
curr = head
while curr:
old_to_new[curr].next = old_to_new.get(curr.next)
old_to_new[curr].random = old_to_new.get(curr.random)
curr = curr.next
return old_to_new[head]

C++

cpp
CopyEdit
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
unordered_map<Node*, Node*> map;
Node* curr = head;
while (curr) {
map[curr] = new Node(curr->val);
curr = curr->next;
}
curr = head;
while (curr) {
map[curr]->next = map[curr->next];
map[curr]->random = map[curr->random];
curr = curr->next;
}
return map[head];
}

Java

java
CopyEdit
public Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node, Node> map = new HashMap<>();
Node curr = head;
while (curr != null) {
map.put(curr, new Node(curr.val));
curr = curr.next;
}
curr = head;
while (curr != null) {
map.get(curr).next = map.get(curr.next);
map.get(curr).random = map.get(curr.random);
curr = curr.next;
}
return map.get(head);
}

20. Smallest Subarray with All Occurrences of Most Frequent Element

Problem: Return the smallest subarray that includes all occurrences of the most frequent
element.

BY: coding_error1
Python

python
CopyEdit
def minSubarray(nums):
freq = {}
left, right = {}, {}
max_freq = 0
for i, num in enumerate(nums):
freq[num] = freq.get(num, 0) + 1
if num not in left: left[num] = i
right[num] = i
max_freq = max(max_freq, freq[num])
min_len = len(nums)
for num in freq:
if freq[num] == max_freq:
min_len = min(min_len, right[num] - left[num] + 1)
return min_len

C++

cpp
CopyEdit
int minSubarray(vector<int>& nums) {
unordered_map<int, int> freq, left, right;
int maxFreq = 0, minLen = nums.size();
for (int i = 0; i < nums.size(); ++i) {
if (!left.count(nums[i])) left[nums[i]] = i;
right[nums[i]] = i;
maxFreq = max(maxFreq, ++freq[nums[i]]);
}
for (auto& [num, count] : freq) {
if (count == maxFreq)
minLen = min(minLen, right[num] - left[num] + 1);
}
return minLen;
}

Java

java
CopyEdit
public int minSubarray(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
Map<Integer, Integer> left = new HashMap<>();
Map<Integer, Integer> right = new HashMap<>();
int maxFreq = 0, minLen = nums.length;

for (int i = 0; i < nums.length; i++) {

freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
left.putIfAbsent(nums[i], i);
right.put(nums[i], i);
maxFreq = Math.max(maxFreq, freq.get(nums[i]));
}

for (int num : freq.keySet()) {

if (freq.get(num) == maxFreq) {
minLen = Math.min(minLen, right.get(num) - left.get(num) + 1);
}

BY: coding_error1
 }
return minLen;
}

BY: coding_error1