Most Frequent Number Following Key In an Array — Solution
Most Frequent Number Following Key In an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Most Frequent Number Following Key In an Array is an easy coding problem on arrays, hash table and counting, asked in Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Counting
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and an integer key that occurs in nums.
For every distinct value target in nums, count the indices i with 0 <= i <= nums.length - 2, nums[i] == key and nums[i + 1] == target — that is, how often target comes immediately after an occurrence of key.
Return the target with the maximum count. The input guarantees that this target is unique.
Example 1
Input: nums = [3,8,3,8,3,5], key = 3
Output: 8
Explanation: The values right after a 3 are 8, 8 and 5, so 8 follows the key twice.
Example 2
Input: nums = [9,9,9,4], key = 9
Output: 9
Explanation: After the 9s come 9, 9 and 4: the key can follow itself.
Example 3
Input: nums = [6,1], key = 6
Output: 1
Constraints
2 <= nums.length <= 10001 <= nums[i] <= 1000key occurs in numsthe answer is unique
Hints for Most Frequent Number Following Key In an Array
Hint 1
Only the element right after each occurrence of
keymatters.Hint 2
Walk the array once and, whenever
nums[i] == key, countnums[i + 1].Hint 3
Return the value with the largest count — values are at most 1000, so an array of counters works.
How to solve Most Frequent Number Following Key In an Array
A single scan of adjacent pairs (nums[i], nums[i + 1]) collects exactly the values that follow key; the most counted one is the answer.
Approach
- Create counters for the values 1–1000.
- For
ifrom 0 ton - 2, ifnums[i] == key, incrementcount[nums[i + 1]]. - Return the value with the largest count.
Why it works
Each index i contributes to exactly one target — the element after it — and only when nums[i] is the key, which is precisely the definition of the count. Uniqueness of the maximum makes the answer well defined.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Stop at
n - 2: the last element has no successor. - Count what follows the key, not the key's own occurrences.
Reference solution
Python
from typing import List
def mostFrequent(nums: List[int], key: int) -> int:
cnt = [0] * 1001
for i in range(len(nums) - 1):
if nums[i] == key:
cnt[nums[i + 1]] += 1
return max(range(1001), key=lambda v: cnt[v])Java
public static int mostFrequent(int[] nums, int key) {
int[] cnt = new int[1001];
int best = 0;
for (int i = 0; i + 1 < nums.length; i++) {
if (nums[i] != key) continue;
int t = nums[i + 1];
cnt[t]++;
if (cnt[t] > cnt[best]) best = t;
}
return best;
}C++
int mostFrequent(vector<int>& nums, int key) {
vector<int> cnt(1001, 0);
int best = 0;
for (size_t i = 0; i + 1 < nums.size(); i++) {
if (nums[i] != key) continue;
int t = nums[i + 1];
if (++cnt[t] > cnt[best]) best = t;
}
return best;
}JavaScript
var mostFrequent = function(nums, key) {
var cnt = new Array(1001).fill(0);
var best = 0;
for (var i = 0; i + 1 < nums.length; i++) {
if (nums[i] !== key) continue;
var t = nums[i + 1];
cnt[t]++;
if (cnt[t] > cnt[best]) best = t;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets