Skip to main content
Talentd

Most Frequent Number Following Key In an Array - Solution & Explanation

EasyArrayHash TableCounting17 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 1000
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the size of the input array.
Space Complexity: O(1) since the array size is constant (1001).

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptJavaScriptPHP

Python

Java

C++

Go

TypeScript

JavaScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a HashMap or Dictionary

Time Complexity: O(n) where n is the size of the input array.
Space Complexity: O(1) since the array size is constant (1001).

Using Array Indexing Technique

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.

Traversal and Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap / Dictionary CountingO(n)O(n)General case when numbers can have a large or unknown range
Array Indexing TechniqueO(n)O(k)When the numeric range is small and predictable, enabling direct indexing

Video Solution

2190. Most Frequent Number Following Key In an Array || Biweekly Contest 73 || Leetcode 2190 • Bro Coders • 3,306 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Most Frequent Number Following Key In an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort Array by Increasing Frequency