NeetCode 150 · Arrays & Hashing

Arrays & Hashing Problems

Hash maps for O(1) lookup, sets for uniqueness, counters for frequency — these primitives unlock a huge class of interview problems.

Problems: 9
Easy: 3
Medium: 6
Hard: 0
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Easy ArrayHash Set
Given integer array nums, return True if any value appears at least twice in the array.
Test Cases
containsDuplicate([1, 2, 3, 1]) → True containsDuplicate([1, 2, 3, 4]) → False containsDuplicate([1, 1, 1, 3]) → True
hash setone-pass O(n)O(n) space
Can you check membership in O(1) as you scan? What data structure does that?
Python Solution
def containsDuplicate(nums): seen = set() for n in nums: if n in seen: return True seen.add(n) return False
Key idea: A set gives O(1) average lookup. Walk the array once; if the current number is already in the set, we found a duplicate.
Time: O(n) — one pass.
Space: O(n) — set stores up to n elements.
02 Easy StringHash Map
Given two strings s and t, return True if t is an anagram of s.
Test Cases
isAnagram('anagram', 'nagaram') → True isAnagram('rat', 'car') → False isAnagram('a', 'ab') → False
Counterfrequency comparisonO(n)
Count character frequencies in both strings. What must be true about the counts if they are anagrams?
Python Solution
from collections import Counter def isAnagram(s, t): return Counter(s) == Counter(t)
Key idea: Two strings are anagrams iff they have exactly the same character frequencies. Counter builds a frequency dict in O(n); comparing two dicts is O(k) where k is the alphabet size.
Time: O(n).
Space: O(1) — at most 26 characters.
03 Easy ArrayHash Map
Given array nums and integer target, return indices of two numbers that add up to target. Assume exactly one solution exists.
Test Cases
twoSum([2, 7, 11, 15], 9) → [0, 1] twoSum([3, 2, 4], 6) → [1, 2] twoSum([3, 3], 6) → [0, 1]
hash mapcomplement lookupenumerate
For each number, what value would pair with it to reach the target? Have you seen that value before?
Python Solution
def twoSum(nums, target): seen = {} # value → index for i, n in enumerate(nums): complement = target - n if complement in seen: return [seen[complement], i] seen[n] = i
Key idea: For each element, compute complement = target - n. If the complement is already in the hash map, we found the pair. Store indices as we go.
Time: O(n).
Space: O(n).
04 Medium ArrayHash MapSorting
Given an array of strings strs, group the anagrams together. Return the groups in any order.
Test Cases
groupAnagrams(['eat','tea','tan','ate','nat','bat']) → [['eat','tea','ate'],['tan','nat'],['bat']] groupAnagrams(['']) → [['']] groupAnagrams(['a']) → [['a']]
defaultdictsorted as keyO(n·k log k)
Two strings are anagrams iff their sorted versions are identical. Use the sorted string as a dictionary key.
Python Solution
from collections import defaultdict def groupAnagrams(strs): groups = defaultdict(list) for s in strs: key = tuple(sorted(s)) groups[key].append(s) return list(groups.values())
Key idea: Sort each string — anagrams produce the same sorted tuple. Use that as a hash map key to bucket strings into groups.
Time: O(n·k log k) — n strings, each of length k sorted.
Space: O(n·k).
05 Medium ArrayHash MapHeap
Given integer array nums and integer k, return the k most frequent elements. Order does not matter.
Test Cases
topKFrequent([1,1,1,2,2,3], 2) → [1, 2] topKFrequent([1], 1) → [1]
Counterheapq.nlargestbucket sort
Count frequencies first. Then how do you efficiently pick the top-k by frequency?
Python Solution
from collections import Counter import heapq def topKFrequent(nums, k): count = Counter(nums) return heapq.nlargest(k, count.keys(), key=count.get)
Key idea: Build a frequency map with Counter, then use a heap to extract the k largest by frequency. heapq.nlargest handles this in one line.
Time: O(n log k).
Space: O(n).
06 Medium ArrayString
Design an algorithm to encode a list of strings to a single string, and decode it back. The encoded string is sent over the network and decoded on the other side.
Test Cases
codec = Codec() strs = ['hello', 'world'] decoded = codec.decode(codec.encode(strs)) # decoded == ['hello', 'world']
length prefixencode/decodeO(n)
Delimiters like commas won't work if strings contain them. What if you prefix each string with its length?
Python Solution
class Codec: def encode(self, strs): # Format: '{length}#{string}' for each string return ''.join(f'{len(s)}#{s}' for s in strs) def decode(self, s): result = [] i = 0 while i < len(s): j = s.index('#', i) # find delimiter length = int(s[i:j]) # extract length result.append(s[j+1:j+1+length]) i = j + 1 + length # advance past this string return result
Key idea: Prefix each string with its length and a # delimiter. During decode, read the length first, then slice exactly that many characters — no ambiguity even if strings contain special characters.
Time: O(n·k) for both encode and decode.
Space: O(n·k).
07 Medium ArrayPrefix Sum
Given integer array nums, return array output where output[i] is the product of all elements except nums[i]. Must run in O(n) without division.
Test Cases
productExceptSelf([1,2,3,4]) → [24,12,8,6] productExceptSelf([-1,1,0,-3,3]) → [0,0,9,0,0]
prefix productsuffix productin-place O(1) extra
For each index, you need (product of everything to the left) × (product of everything to the right). Can you compute both in two separate passes?
Python Solution
def productExceptSelf(nums): n = len(nums) output = [1] * n # Forward pass: output[i] = product of nums[0..i-1] prefix = 1 for i in range(n): output[i] = prefix prefix *= nums[i] # Backward pass: multiply in suffix products suffix = 1 for i in range(n - 1, -1, -1): output[i] *= suffix suffix *= nums[i] return output
Key idea: Two passes. Forward pass fills output[i] with the product of everything to the left. Backward pass multiplies in the product of everything to the right.
Time: O(n).
Space: O(1) extra (output array doesn't count).
08 Medium ArrayHash SetMatrix
Determine if a 9×9 Sudoku board is valid. Only filled cells need to be validated: each row, column, and 3×3 box must contain unique digits 1–9.
Test Cases
# board = 9x9 grid with '.' for empty cells isValidSudoku(board) → True or False
set per row/col/boxfloor division for box indexO(81)
Use 9 sets for rows, 9 for columns, and 9 for 3×3 boxes. How do you map (row, col) to a box index?
Python Solution
def isValidSudoku(board): rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] boxes = [set() for _ in range(9)] for r in range(9): for c in range(9): val = board[r][c] if val == '.': continue box_idx = (r // 3) * 3 + (c // 3) if (val in rows[r] or val in cols[c] or val in boxes[box_idx]): return False rows[r].add(val) cols[c].add(val) boxes[box_idx].add(val) return True
Key idea: Maintain 27 sets (9 rows + 9 cols + 9 boxes). Map (r, c) to box index via (r//3)*3 + c//3. If any digit appears twice in the same set, the board is invalid.
Time: O(81) = O(1) — fixed grid size.
Space: O(81) = O(1).
09 Medium ArrayHash Set
Given unsorted integer array nums, return the length of the longest consecutive elements sequence. Must run in O(n).
Test Cases
longestConsecutive([100,4,200,1,3,2]) → 4 # [1,2,3,4] longestConsecutive([0,3,7,2,5,8,4,6,0,1]) → 9
setchain start detectionO(n)
Put all numbers in a set. For each number, check if it's the START of a chain (i.e., n-1 is NOT in the set). Only then count forward.
Python Solution
def longestConsecutive(nums): num_set = set(nums) best = 0 for n in num_set: # Only start a chain from the smallest number in it if n - 1 not in num_set: length = 1 while n + length in num_set: length += 1 best = max(best, length) return best
Key idea: For each number that is the start of a chain (no predecessor in the set), count how long the chain extends. Each number is visited at most twice total, giving O(n).
Time: O(n).
Space: O(n).
Next Category →