Array Hashing Examples

5 problems in this category

Hash Map Array Hash Set String Sorting Heap Prefix Sum

Two Sum

Given an array of integers and a target, return the indices of two numbers that add up to the target.

Easy LeetCode
Time:
O(n)?
Why O(n)?
Single pass through the array
We visit each element exactly once in the loop. For each element, hash lookup and insertion are O(1) operations.
Example: Array of 1000 elements = ~1000 operations
Space:
O(n)?
Why O(n)?
Hash map stores up to n elements
In the worst case, we might store almost every element in the hash map before finding the solution.
Example: Array [1,2,3,4] with target 7 stores 3 elements in hash
Example: nums = [2,7,11,15], target = 9 → [0,1]
Hash Map Array
View Solution →

Contains Duplicate

Returns true if the input array has any duplicates, false otherwise.

Easy LeetCode
Time: O(n)
Space: O(n)
Example: [1,2,3,1] → true
Hash Set Array
View Solution →

Group Anagrams

Groups words that are anagrams of each other.

Medium LeetCode
Time: O(n * k log k)
Space: O(n * k)
Example: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]
Hash Map String Sorting
View Solution →

Top K Frequent Elements

Returns the k most frequent elements in the array.

Medium LeetCode
Time: O(n log n)
Space: O(n)
Example: [1,1,1,2,2,3], k=2 → [1,2]
Hash Map Sorting Heap
View Solution →

Product of Array Except Self

Returns a new array such that each index has the product of all elements except itself.

Medium LeetCode
Time: O(n)
Space: O(1)
Example: [1,2,3,4] → [24,12,8,6]
Array Prefix Sum
View Solution →
← Back to All Categories