Most Frequent Number Following Key In an Array solution and explanation
Google
9 more videos on this problem
2190. Most Frequent Number Following Key In an Array || Biweekly Contest 73 || Leetcode 2190Bro Coders · 4:49 · 3K views
Leetcode #2190 (Java Solution) - Most Frequent Number Following Key In an ArrayNatorAlgoVids · 9:01 · 1K views
2190. Most Frequent Number Following Key In an Array easycode kebab · 10:50 · 628 views
Leetcode Biweekly Contest 73 | PROBLEM 2190 , 2191 , 2192 | GRAPH PROBLEM | LOGICcode Explainer · 16:46 · 619 views
2190. Most Frequent Number Following Key In an Array (Leetcode Easy)Programming Live with Larry · 2:58 · 438 views
Most Frequent Number Following Key In an Array - LeetCode 2190 - Javaalgobest - Computer Science · 4:33 · 428 views
Most Frequent Number Following Key In an Array #LeetCode #java #coding #intervewQuestionsCodeVia · 3:23 · 203 views
Leetcode 2190 Most Frequent Number Following Key In an ArrayMath Geeks · 1:32 · 191 views
Leetcode 2190 - Most Frequent Number Following Key In an ArrayShafik Quoraishee · 15:35 · 160 views
LeetCode 2190 | Most Frequent Number Following Key In an Array | JavaSleepy Cracker · 4:53 · 100 views
The problem
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] == keyand,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] <= 1000- The test cases will be generated such that the answer is unique.
Approach overview
Problem 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 1: Using a HashMap or Dictionary
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.
def most_frequent(nums, key):
from collections import defaultdict
count = defaultdict(int)
for i in range(len(nums) - 1):
if nums[i] == key:
count[nums[i + 1]] += 1
return max(count, key=count.get)
nums = [2, 2, 2, 2, 3]
key = 2
print(most_frequent(nums, key))import java.util.HashMap;
public class Solution {
public int mostFrequent(int[] nums, int key) {
HashMap<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == key) {
count.put(nums[i + 1], count.getOrDefault(nums[i + 1], 0) + 1);
}
}
int maxCount = 0;
int result = -1;
for (int k : count.keySet()) {
if (count.get(k) > maxCount) {
maxCount = count.get(k);
result = k;
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 2, 2, 2, 3};
int key = 2;
System.out.println(sol.mostFrequent(nums, key));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
int mostFrequent(std::vector<int>& nums, int key) {
std::unordered_map<int, int> count;
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] == key) {
count[nums[i + 1]]++;
}
}
int maxCount = 0;
int result = -1;
for (auto& pair : count) {
if (pair.second > maxCount) {
maxCount = pair.second;
result = pair.first;
}
}
return result;
}
int main() {
std::vector<int> nums = {2, 2, 2, 2, 3};
int key = 2;
std::cout << mostFrequent(nums, key) << std::endl;
return 0;
}function mostFrequent(nums, key) {
const count = {};
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === key) {
count[nums[i + 1]] = (count[nums[i + 1]] || 0) + 1;
}
}
let maxCount = 0;
let result = -1;
for (let num in count) {
if (count[num] > maxCount) {
maxCount = count[num];
result = parseInt(num);
}
}
return result;
}
const nums = [2, 2, 2, 2, 3];
const key = 2;
console.log(mostFrequent(nums, key));#include <stdio.h>
#include <stdlib.h>
int mostFrequent(int* nums, int numsSize, int key) {
int count[1001] = {0}; // Because 1 <= nums[i] <= 1000
for (int i = 0; i < numsSize - 1; i++) {
if (nums[i] == key) {
count[nums[i + 1]]++;
}
}
int maxCount = 0;
int result = -1;
for (int i = 1; i <= 1000; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
result = i;
}
}
return result;
}
int main() {
int nums[] = {2, 2, 2, 2, 3};
int key = 2;
printf("%d\n", mostFrequent(nums, 5, key));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MostFrequent(int[] nums, int key) {
var count = new Dictionary<int, int>();
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] == key) {
if (!count.ContainsKey(nums[i + 1])) count[nums[i + 1]] = 0;
count[nums[i + 1]]++;
}
}
int maxCount = 0;
int result = -1;
foreach (var kvp in count) {
if (kvp.Value > maxCount) {
maxCount = kvp.Value;
result = kvp.Key;
}
}
return result;
}
public static void Main() {
var solution = new Solution();
int[] nums = {2, 2, 2, 2, 3};
int key = 2;
Console.WriteLine(solution.MostFrequent(nums, key));
}
}Using a defaultdict from the collections module, we count the occurrence of each number following the key. Then we find and return the number with the maximum occurrence using the max function.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 2: Using Array Indexing Technique
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.
def most_frequent(nums, key):
count = [0] * 1001
for i in range(len(nums) - 1):
if nums[i] == key:
count[nums[i + 1]] += 1
return max(range(len(count)), key=lambda x: count[x])
nums = [2, 2, 2, 2, 3]
key = 2
print(most_frequent(nums, key))public class Solution {
public int mostFrequent(int[] nums, int key) {
int[] count = new int[1001];
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == key) {
count[nums[i + 1]]++;
}
}
int maxCount = 0;
int result = -1;
for (int i = 1; i <= 1000; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
result = i;
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 2, 2, 2, 3};
int key = 2;
System.out.println(sol.mostFrequent(nums, key));
}
}#include <iostream>
#include <vector>
int mostFrequent(std::vector<int>& nums, int key) {
int count[1001] = {0};
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] == key) {
count[nums[i + 1]]++;
}
}
int maxCount = 0;
int result = -1;
for (int i = 1; i <= 1000; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
result = i;
}
}
return result;
}
int main() {
std::vector<int> nums = {2, 2, 2, 2, 3};
int key = 2;
std::cout << mostFrequent(nums, key) << std::endl;
return 0;
}function mostFrequent(nums, key) {
const count = Array(1001).fill(0);
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === key) {
count[nums[i + 1]]++;
}
}
let maxCount = 0;
let result = -1;
for (let i = 1; i <= 1000; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
result = i;
}
}
return result;
}
const nums = [2, 2, 2, 2, 3];
const key = 2;
console.log(mostFrequent(nums, key));#include <stdio.h>
int mostFrequent(int* nums, int numsSize, int key) {
int count[1001] = {0};
for (int i = 0; i < numsSize - 1; i++) {
if (nums[i] == key) {
count[nums[i + 1]]++;
}
}
int maxCount = 0;
int result = -1;
for (int i = 1; i <= 1000; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
result = i;
}
}
return result;
}
int main() {
int nums[] = {2, 2, 2, 2, 3};
int key = 2;
printf("%d\n", mostFrequent(nums, 5, key));
return 0;
}using System;
public class Solution {
public int MostFrequent(int[] nums, int key) {
int[] count = new int[1001];
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] == key) {
count[nums[i + 1]]++;
}
}
int maxCount = 0;
int result = -1;
for (int i = 1; i <= 1000; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
result = i;
}
}
return result;
}
public static void Main() {
var solution = new Solution();
int[] nums = {2, 2, 2, 2, 3};
int key = 2;
Console.WriteLine(solution.MostFrequent(nums, key));
}
}With a simple list to track counts, this approach efficiently computes and retrieves the target with the maximum frequency directly by accessing list indices, bypassing any additional structure or overhead.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Traversal and Counting
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.
function mostFrequent(nums: number[], key: number): number {
const cnt: number[] = Array(Math.max(...nums) + 1).fill(0);
let [ans, mx] = [0, 0];
for (let i = 0; i < nums.length - 1; ++i) {
if (nums[i] === key) {
if (mx < ++cnt[nums[i + 1]]) {
mx = cnt[nums[i + 1]];
ans = nums[i + 1];
}
}
}
return ans;
}func mostFrequent(nums []int, key int) (ans int) {
cnt := [1001]int{}
mx := 0
for i, x := range nums[1:] {
if nums[i] == key {
cnt[x]++
if mx < cnt[x] {
mx = cnt[x]
ans = x
}
}
}
return
}class Solution {
function mostFrequent($nums, $key) {
$cnt = array_fill(0, max($nums) + 1, 0);
$ans = 0;
$mx = 0;
for ($i = 0; $i < count($nums) - 1; ++$i) {
if ($nums[$i] === $key) {
$cnt[$nums[$i + 1]]++;
if ($mx < $cnt[$nums[$i + 1]]) {
$mx = $cnt[$nums[$i + 1]];
$ans = $nums[$i + 1];
}
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a HashMap or Dictionary | Time Complexity: O(n). |
| Using Array Indexing Technique | Time Complexity: O(n). |
| Traversal and Counting | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Most Frequent Number Following Key In an Array easy or hard?
Most Frequent Number Following Key In an Array is classified as an Easy problem. The main idea is recognizing that you only need to count numbers that appear immediately after the key, which can be solved with a single pass and a simple frequency map.
Most Frequent Number Following Key In an Array Python/Java solution
In Python, use a dictionary or collections.Counter to track frequencies while scanning the array. In Java, use a HashMap<Integer, Integer> and update the count whenever nums[i] equals the key. Both implementations achieve O(n) time complexity with straightforward frequency counting.
How to solve Most Frequent Number Following Key In an Array in O(n)?
Traverse the array from index 0 to n−2. Whenever nums[i] equals the key, increment the count for nums[i+1] in a hash map or counting array. Track the value with the highest frequency while iterating. Since each element is processed once, the algorithm runs in O(n) time.
What is the best approach for Most Frequent Number Following Key In an Array?
The best approach is using a hash map (dictionary) to count how many times each number appears immediately after the key. Iterate through the array and whenever nums[i] equals the key, increment the frequency of nums[i+1]. This solution runs in O(n) time with O(n) space and works for any value range.
Is Most Frequent Number Following Key In an Array asked at Google/Amazon/Meta?
This exact problem appears on LeetCode and represents a typical array frequency counting pattern. Variations of counting adjacent relationships and tracking most frequent elements are commonly asked in interviews at companies like Amazon and Google.
What data structure is used in Most Frequent Number Following Key In an Array?
The most common data structure used is a hash table (HashMap or dictionary) to store frequencies of numbers that appear after the key. If constraints allow, a simple counting array can also be used to track frequencies more efficiently.
What is the time complexity of Most Frequent Number Following Key In an Array?
The optimal solution runs in O(n) time because the array is scanned once. Each update to the hash map or counting array takes O(1) average time. Space complexity is O(n) for a hash map or O(k) if using a fixed counting array based on value range.