Arrays & Hashing
Use hash maps and hash sets to trade space for time. Convert O(n²) lookups into O(n) by storing values you have seen. The foundation of almost every interview.
Time
O(n)
Space
O(n)
Recognize it when
- "Two Sum" style: find pairs/groups with a property
- Detect duplicates or count frequencies
- Group items by a computed key (anagrams, frequency)
- "Find the element missing / extra" in O(n) time
Questions — ordered by difficulty
Two Sum
Given an array of integers nums and an integer target, return the indices [i, j] of the two numbers that add up to target. Exactly one solution always exists; you may not use the same element twice. Example: nums=[2,7,11,15], target=9 → [0,1] because nums[0]+nums[1]=9.
Contains Duplicate
Given an integer array nums, return true if any value appears at least twice, or false if every element is distinct. Example: [1,2,3,1] → true (1 appears twice). [1,2,3,4] → false.
Valid Anagram
Given two strings s and t, return true if t is an anagram of s — meaning they contain the exact same characters with the same frequencies (order doesn't matter). Example: s="anagram", t="nagaram" → true. s="rat", t="car" → false.
Group Anagrams
Given an array of strings, group the strings that are anagrams of each other and return all groups. Example: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]] — order of groups and within each group doesn't matter.
Product of Array Except Self
Given integer array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i]. You must solve it in O(n) without using division. Example: [1,2,3,4] → [24,12,8,6] because answer[0]=2×3×4=24, answer[1]=1×3×4=12, etc.
Longest Consecutive Sequence
Given an unsorted integer array, return the length of the longest sequence of consecutive integers (e.g. 4,5,6,7). Must run in O(n) — sorting is O(n log n) and won't count. Example: [100,4,200,1,3,2] → 4 because [1,2,3,4] is the longest consecutive run.
Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the rules.
Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
Majority Element
Given an array nums of size n, return the majority element (appears more than ⌊n / 2⌋ times). Must solve in O(n) time and O(1) space.
Insert Delete GetRandom O(1)
Implement the RandomizedSet class with O(1) average time complexity for insert, remove, and getRandom.