Hash Maps for Frequency and Lookup

Hello! In our last lesson, we built a hash table from the ground up using separate chaining. This gave you a deep understanding of its internal mechanics, including the hashCode()/equals() contract and the importance of rehashing to maintain performance. You now know why HashMap lookups, insertions, and deletions have an impressive average time complexity of $O (1)$ .

Today, we put that knowledge into practice. This lesson is all about leveraging the power of HashMap to solve common problems that frequently appear in technical interviews. We will focus on two key patterns: frequency counting and fast lookups. Mastering these patterns is a significant step toward your goal of excelling in interviews at product-based companies.

Our learning outcome is to apply hash maps to solve frequency counting and lookup problems, specifically "Two Sum" and "Subarray Sum Equals K".

1. The Foundation: Frequency Counting

The most direct application of a HashMap is to count the occurrences of items in a collection. This is a fundamental building block for many more complex algorithms.

The logic is simple:

Initialize an empty HashMap.
Iterate through the elements of your array or string.
For each element, use it as the key in the map. The value will be its frequency count.
If the key is already in the map, increment its value. If not, add it with a value of 1.

A concise way to do this in Java is with the getOrDefault method.

Java HashMap Programs And Coding Examples

This article, 'Java HashMap Programs And Coding Examples' from javaconceptoftheday.com, provides a clear, practical example of frequency counting. We'll look at how to count the occurrences of each number in an array.

Please read section 11, titled 'Find the frequency of each element of an array using HashMap?'. Focus on the 'Element Frequency Program' and observe the loop where elementFrequencyMap.put(i, elementFrequencyMap.getOrDefault(i, 0) + 1); is used. This is a standard and efficient pattern.

This single line of code, map.put(key, map.getOrDefault(key, 0) + 1), is incredibly powerful. It retrieves the current count for a key, or 0 if the key doesn't exist yet, increments it by one, and then updates the map. Keep this pattern in mind as we move to more complex problems.

2. Classic Lookup Problem: "Two Sum"

The "Two Sum" problem is one of the most famous coding interview questions. Its simplicity hides a crucial test of your understanding of data structures and time complexity.

The problem is: Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

Let's explore how to solve this, from a naive approach to an optimal one.

LeetCode Exercise in Java Tutorial - Two Sum FAST Solution

The video 'LeetCode Exercise in Java Tutorial - Two Sum FAST Solution' by Coding with John provides an excellent walkthrough. We'll watch it in parts to understand the problem, the brute-force solution, and finally the optimal HashMap solution.

Watch from 00:51 to 07:29. This part introduces the problem and then implements the brute-force O(n²) solution using nested loops. Understanding this initial approach is key to appreciating the optimization that follows.

As the video explains, the brute-force approach of checking every possible pair has a time complexity of $O (n^{2})$ , which is too slow for large inputs. This is where your knowledge of hash maps becomes a game-changer.

The Optimal O(n) Solution

The key insight is this: for each number x in the array, we need to find if its "complement," target - x, also exists in the array. Instead of searching the array for the complement in a second loop, we can use a HashMap to perform this lookup in $O (1)$ time.

Here is the refined algorithm:

Create a HashMap<Integer, Integer> to store each number we've seen and its index (value -> index).
Iterate through the array nums just once.
For each element nums[i], calculate its complement: complement = target - nums[i].
Check if the complement exists as a key in your HashMap.
- If it does, you've found a solution! The indices are i (the current index) and map.get(complement) (the index of the complement you stored earlier).
- If it does not, add the current element nums[i] and its index i to the map. This makes it available for lookup in future iterations.

Now, let's see this optimal solution in action.

LeetCode Exercise in Java Tutorial - Two Sum FAST Solution

Let's continue with the same video. This next segment explains the logic and implementation of the highly efficient HashMap solution.

Watch from 10:05 to 21:58. Pay close attention to the logic of checking for the complement before adding the current element to the map. This avoids using the same element twice. The video clearly explains the algorithm, walks through the code, and demonstrates the massive performance gain.

Two Sum Problem: Efficient Approach Using HashMap — This image illustrates the HashMap approach. While iterating, we are at the element '4'. We calculate the complement `11 - 4 = 7`. We then perform a quick O(1) lookup in our HashMap to see if we have encountered '7' before. Since '7' is in the map, we have found our pair.

This solution reduces the time complexity to $O (n)$ because we only traverse the array once. The trade-off is an increase in space complexity to $O (n)$ for storing the elements in the HashMap. For most interview scenarios, this is an excellent trade-off.

3. Advanced Lookup: "Subarray Sum Equals K"

Let's tackle a more challenging problem that combines hash maps with another powerful technique: prefix sums.

Problem: Given an array of integers nums and an integer k, find the total number of continuous subarrays whose sum equals k.

A subarray is a contiguous part of an array. For example, in [1, 2, 3], [2, 3] is a subarray, but [1, 3] is not.

The Prefix Sum + HashMap Insight

The core idea revolves around prefix sums. A prefix sum at index i is the sum of all elements from 0 to i. The sum of any subarray from j+1 to i can be calculated as prefixSum[i] - prefixSum[j].

We want this subarray sum to equal k:
prefixSum[i] - prefixSum[j] = k

If we rearrange this equation, we get:
prefixSum[j] = prefixSum[i] - k

This gives us our algorithm:
As we iterate through the array and calculate the currentSum (our prefixSum[i]), we need to look for how many times we have previously seen a prefix sum equal to currentSum - k. Each time we find one, it signifies a new subarray ending at our current position with a sum of k. A HashMap is the perfect tool for this lookup.

The following video provides an outstanding explanation of this intuition.

Count Subarray sum Equals K | Brute - Better -Optimal

The video 'Count Subarray sum Equals K' from the 'take U forward' channel is excellent for building intuition. It moves from brute-force to the optimal solution.

Watch from 08:15 to 20:53. This segment explains the prefix sum concept and walks through a detailed dry run of the optimal algorithm. Focus on why we are looking for s - k in the map and why the map stores the frequency of prefix sums.

To solidify this concept, let's look at a textual explanation and a clean Java implementation. This resource also highlights common mistakes, which are crucial to avoid in an interview.

560. Subarray Sum Equals K - In-Depth Explanation

The AlgoMonster article '560. Subarray Sum Equals K - In-Depth Explanation' provides a structured breakdown of the same algorithm and points out common pitfalls.

Read the sections on 'Intuition', 'Solution Implementation', 'Solution Approach', and 'Common Pitfalls'. Pay special attention to two critical details: (1) why the HashMap is initialized with {0: 1}, and (2) the correct order of checking the map and then updating it.

Test your understanding!

You are solving the "Subarray Sum Equals K" problem with nums = [1, -1, 1, -1, 1] and k = 1. You are using the prefix sum + HashMap approach. What will be the final count of subarrays, and what will be the state of your prefixSumCount map just before returning the final count?

Show answer

Let's trace the algorithm:

Initial State: currentSum = 0, count = 0, map = {0: 1}.

num = 1:
- currentSum becomes 1.
- Check for 1 - k = 1 - 1 = 0 in map. map.get(0) is 1. count becomes 1. (Finds subarray [1])
- Update map: map.put(1, 1). State: {0: 1, 1: 1}.
num = -1:
- currentSum becomes 0.
- Check for 0 - k = 0 - 1 = -1 in map. Not found. count remains 1.
- Update map: map.put(0, 2). State: {0: 2, 1: 1}.
num = 1:
- currentSum becomes 1.
- Check for 1 - k = 0 in map. map.get(0) is 2. count becomes 1 + 2 = 3. (Finds subarrays [1, -1, 1] and [1])
- Update map: map.put(1, 2). State: {0: 2, 1: 2}.
num = -1:
- currentSum becomes 0.
- Check for 0 - k = -1 in map. Not found. count remains 3.
- Update map: map.put(0, 3). State: {0: 3, 1: 2}.
num = 1:
- currentSum becomes 1.
- Check for 1 - k = 0 in map. map.get(0) is 3. count becomes 3 + 3 = 6. (Finds subarrays [1, -1, 1, -1, 1], [1, -1, 1], and [1])
- Update map: map.put(1, 3). State: {0: 3, 1: 3}.

Final Count: 6
Final Map State: {0=3, 1=3}

Conclusion

In this lesson, you've seen how the theoretical efficiency of HashMap translates into practical, high-performance solutions for common coding challenges.

Key Takeaways:

HashMap is the go-to data structure for frequency counting problems. The map.getOrDefault(key, 0) + 1 pattern is your best friend.
For lookup problems like "Two Sum," HashMap can drastically reduce time complexity from $O (n^{2})$ to $O (n)$ by providing constant-time checks for complement values.
By combining HashMap with other techniques like prefix sums, you can solve more advanced problems like "Subarray Sum Equals K" efficiently. The key is often to find a mathematical relationship (prefixSum[j] = prefixSum[i] - k) that allows you to look up a required value from your past calculations.

Preview of the Next Lesson:
We will continue exploring the power of hashing. In the next lesson, we'll apply these concepts to solve another classic interview problem: finding the longest consecutive subsequence in an array. This will involve using a HashSet (which is internally implemented using a HashMap) to achieve an elegant and efficient solution.