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.
This approach involves a single traversal through the array to count occurrences of numbers following the key using a hash map or dictionary. After the traversal, you'll need to determine which number has the highest count.
The code uses an array to count the occurrences of each possible number (from 1 to 1000) that can follow the key. After iterating through the array, it checks for the number with the maximum count and returns it.
Time Complexity: O(n) where n is the size of the input array.
Space Complexity: O(1) since the array size is constant (1001).
This approach leverages a fixed-size array (1001 elements because numbers range from 1 to 1000) to efficiently count occurrences. Once the array is populated, determining the target with the maximum count is straightforward.
An array of 1001 integers is used to store counts of each possible number that can follow the key. This makes the count operation O(1), and we determine the result by checking for the max value in this array.
Time Complexity: O(n), n being the number of elements.
Space Complexity: O(1), since the array size is fixed irrespective of the input size.
We use a hash table or an array cnt to record the number of occurrences of each target, and use a variable mx to maintain the maximum number of occurrences of target. Initially, mx = 0.
Traverse the array nums. If nums[i] = key, increment the count of nums[i + 1] in cnt[nums[i + 1]]. If mx \lt cnt[nums[i + 1]], update mx = cnt[nums[i + 1]] and update the answer ans = nums[i + 1].
After the traversal, return the answer ans.
The time complexity is O(n), and the space complexity is O(M). Here, n and M are the length of the array nums and the maximum value of the elements in the array nums, respectively.
Python
Java
C++
Go
TypeScript
JavaScript
PHP
| Approach | Complexity |
|---|---|
| Using a HashMap or Dictionary | Time Complexity: O(n) where n is the size of the input array. |
| Using Array Indexing Technique | Time Complexity: O(n), n being the number of elements. |
| Traversal and Counting | — |
| 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 |
2190. Most Frequent Number Following Key In an Array || Biweekly Contest 73 || Leetcode 2190 • Bro Coders • 3,226 views views
Watch 9 more video solutions →Practice Most Frequent Number Following Key In an Array with our built-in code editor and test cases.
Practice on FleetCode