Watch 10 video solutions for Most Frequent Number Following Key In an Array, a easy level problem involving Array, Hash Table, Counting. This walkthrough by Bro Coders has 3,226 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums. You are also given an integer key, which is present in nums.
For every unique integer target in nums, count the number of times target immediately follows an occurrence of key in nums. In other words, count the number of indices i such that:
0 <= i <= nums.length - 2,nums[i] == key and,nums[i + 1] == target.Return the target with the maximum count. The test cases will be generated such that the target with maximum count is unique.
Example 1:
Input: nums = [1,100,200,1,100], key = 1 Output: 100 Explanation: For target = 100, there are 2 occurrences at indices 1 and 4 which follow an occurrence of key. No other integers follow an occurrence of key, so we return 100.
Example 2:
Input: nums = [2,2,2,2,3], key = 2 Output: 2 Explanation: For target = 2, there are 3 occurrences at indices 1, 2, and 3 which follow an occurrence of key. For target = 3, there is only one occurrence at index 4 which follows an occurrence of key. target = 2 has the maximum number of occurrences following an occurrence of key, so we return 2.
Constraints:
2 <= nums.length <= 10001 <= nums[i] <= 1000Problem Overview: You are given an integer array nums and a value key. Every time key appears in the array, look at the element immediately after it. The goal is to find which number appears most frequently in that position.
Approach 1: HashMap / Dictionary Counting (O(n) time, O(n) space)
Scan the array once and record how often each number appears directly after key. When you encounter nums[i] == key, increment the count for nums[i + 1] inside a hash map. The hash map stores value → frequency. After the traversal, return the number with the highest recorded frequency.
This approach works because the problem only cares about the element immediately following each occurrence of the key. A hash map provides constant‑time insert and lookup, so each update is O(1). The full pass over the array results in O(n) time complexity with O(n) extra space in the worst case.
This method relies heavily on hash table counting patterns. Similar strategies appear frequently in problems involving frequency tracking and neighbor relationships in an array.
Approach 2: Array Indexing Technique (O(n) time, O(k) space)
If the value range of nums is known and reasonably small (as in this problem’s constraints), a fixed‑size counting array can replace the hash map. Traverse the array and whenever nums[i] == key, increment count[nums[i+1]]. Track the maximum frequency while updating counts to avoid a second pass.
Using array indexing eliminates hashing overhead and keeps operations extremely fast. Accessing a frequency bucket becomes a direct index lookup. The time complexity remains O(n), but the space complexity becomes O(k), where k is the numeric range of possible values.
This technique is common in problems involving counting when the domain of numbers is limited. It trades flexibility for raw speed and predictable memory usage.
Recommended for interviews: The HashMap counting approach is the most expected solution. It clearly demonstrates that you can detect the pattern ("track what follows the key") and apply frequency counting efficiently in one pass. The array indexing version is a nice optimization when constraints allow it, but the hash map solution communicates the idea cleanly and works for any value range.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap / Dictionary Counting | O(n) | O(n) | General case when numbers can have a large or unknown range |
| Array Indexing Technique | O(n) | O(k) | When the numeric range is small and predictable, enabling direct indexing |