Hashing
Uses a hash map or set to store and retrieve values in average O(1) time.
The Approach
- Initialize a HashMap or HashSet to store data.
- Iterate through the input data.
- For each element, use the hash structure to check for existence, update frequency, or store a value.
- This avoids nested loops and provides fast lookups.
Types of Hashing
Frequency Counting
Use a HashMap to count occurrences of each element in a collection.
Original Array
10
20
10
30
20
10
Hash Map (Frequency Count)
Map is empty
Initialize an empty hash map.
Existence Checking
Use a HashSet to quickly check if an element has been seen before.
Original Array
10
20
10
30
20
10
Hash Map (Frequency Count)
Map is empty
Initialize an empty hash map.
Common Problems
Two Sum
Array + HashMap
Longest Substring Without Repeating Characters
Sliding Window
Subarray Sum Equals K
Prefix Sum + HashMap
Group Anagrams
Hashing + Sorting