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] <= 1000In #2190 Most Frequent Number Following Key In an Array, the goal is to determine which number appears most often immediately after a given key in the array. A straightforward and efficient approach is to iterate through the array while observing pairs of consecutive elements.
Whenever the current element equals the key, we look at the next element and record how often it appears after the key. A hash table (frequency map) is ideal for this task because it allows constant-time updates and lookups while counting occurrences of each candidate value.
As we scan the array once, we update the frequency of the element that follows the key. After processing the array, we simply determine which value has the highest recorded frequency in the map.
This approach works efficiently because it requires only a single pass through the array and uses additional space proportional to the number of distinct values that follow the key.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single pass with Hash Map counting | O(n) | O(k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Count the number of times each target value follows the key in the array.
Choose the target with the maximum count and return it.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem only requires examining pairs of consecutive elements where the first equals the key. By checking each index and looking at the next element, we gather all required frequency information in one traversal.
Problems like this appear in interviews at large tech companies because they test array traversal, hash map usage, and frequency counting. While the exact question may vary, the pattern is common in coding interviews.
A hash table (or hash map) is the best data structure because it allows constant-time updates and lookups while counting occurrences. Each time the key is found, the next element’s frequency can be quickly incremented in the map.
The optimal approach scans the array once and uses a hash map to count how often each number appears immediately after the given key. After the traversal, the number with the highest frequency is returned. This method runs in linear time and is efficient for typical interview constraints.