LeetCode 2190 - Most Frequent Number Following Key In an Array

The problem asks us to find the integer that appears most frequently immediately after a given key value in the array. More specifically, we are given an integer array nums and an integer key, which is guaranteed to exist in the array.

leetcodeeasyarrayhash-tablecounting

LeetCode Problem 2190

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to find the integer that appears most frequently immediately after a given key value in the array.

More specifically, we are given an integer array nums and an integer key, which is guaranteed to exist in the array. We need to examine every occurrence of key in nums. Whenever we find key at index i, we look at the next element, nums[i + 1], because the problem defines a "target" as a number that directly follows key.

For every distinct number that follows key, we count how many times it appears in this position. At the end, we return the number with the highest count. The problem guarantees that the answer is unique, meaning there will never be a tie for the most frequent target.

For example, consider:

nums = [1,100,200,1,100]
key = 1

The number 1 appears at indices 0 and 3. Looking at the element immediately after each occurrence:

  • nums[1] = 100
  • nums[4] = 100

The number 100 appears twice after 1, making it the most frequent target.

The constraints are relatively small:

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

Since the maximum array size is only 1000, even a quadratic solution would technically work. However, this problem is naturally suited for a linear scan, allowing us to achieve an optimal solution efficiently.

An important detail is that we only inspect indices up to nums.length - 2, because we must always check nums[i + 1]. If key appears at the last index, there is no following number to count. The problem guarantees that the answer is unique, so we do not need to implement tie-breaking logic.

Important edge cases include repeated occurrences of key, consecutive keys, and arrays where the same target appears many times after key. For example, in [2,2,2,2,3] with key = 2, the target 2 repeatedly follows itself, which could expose indexing mistakes in a naive implementation.

Approaches

Brute Force Approach

A straightforward brute-force approach is to first identify every unique number in nums, then, for each possible target, scan the entire array to count how many times it immediately follows key.

For every distinct value target, we would iterate through the array and count indices i where:

nums[i] == key
nums[i + 1] == target

After computing counts for all possible targets, we return the one with the maximum frequency.

This approach is correct because it explicitly evaluates every valid target and counts occurrences exactly according to the problem definition. However, it is inefficient because we repeatedly scan the array for each candidate target.

If there are n elements and up to n unique targets, this leads to a worst-case time complexity of O(n²).

Optimal Approach, Single Pass with Hash Map

The key observation is that we do not need to evaluate every target separately.

Instead, we can process the array in a single pass. Every time we encounter key, we immediately look at the next element and increment its frequency count in a hash map.

While updating frequencies, we can also track the most frequent target seen so far. This avoids needing a second pass through the frequency map.

A hash map is ideal because it allows constant-time updates and lookups on average.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly scans the array for every target
Optimal O(n) O(n) Single pass with a hash map for counting

Algorithm Walkthrough

  1. Create an empty hash map called frequency_count.

This map stores how many times each target number appears immediately after key. 2. Initialize two variables:

  • most_frequent_target to store the current best answer
  • highest_frequency to store the largest count seen so far

These help us avoid scanning the map again after counting finishes. 3. Iterate through the array from index 0 to len(nums) - 2.

We stop at len(nums) - 2 because we always need to safely access nums[i + 1]. 4. At each index, check whether nums[i] == key.

If the current value is not equal to key, move on. 5. When nums[i] == key, inspect the next value:

target = nums[i + 1]

This value is a valid target because it immediately follows key. 6. Update the target's frequency in the hash map.

Increment its count by one. 7. Compare the updated count with highest_frequency.

If the new frequency is greater, update:

  • highest_frequency
  • most_frequent_target
  1. After the loop completes, return most_frequent_target.

Why it works

The algorithm works because every valid target occurrence is counted exactly once. Whenever key appears at index i, the algorithm immediately records nums[i + 1], which is precisely what the problem asks us to measure.

The hash map maintains an accurate frequency count for every target encountered. Since we continuously track the target with the highest frequency, the final stored answer must be the unique most frequent target guaranteed by the problem.

Python Solution

from typing import List

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        frequency_count = {}

        most_frequent_target = -1
        highest_frequency = 0

        for index in range(len(nums) - 1):
            if nums[index] == key:
                target = nums[index + 1]
                frequency_count[target] = (
                    frequency_count.get(target, 0) + 1
                )

                if frequency_count[target] > highest_frequency:
                    highest_frequency = frequency_count[target]
                    most_frequent_target = target

        return most_frequent_target

The implementation follows the exact algorithm described earlier.

We first create a dictionary called frequency_count to store how many times each target appears after key. Python dictionaries provide average O(1) insertion and lookup time, making them ideal for frequency counting.

We then initialize most_frequent_target and highest_frequency. These variables allow us to maintain the best answer dynamically as we process the array.

The loop iterates only up to len(nums) - 1, ensuring that nums[index + 1] is always valid. Whenever the current element equals key, we retrieve the following number and increment its frequency count.

After updating the count, we compare it with the current maximum frequency. If this target now has a larger count, it becomes the new answer.

Finally, we return the stored result after completing the scan.

Go Solution

func mostFrequent(nums []int, key int) int {
	frequencyCount := make(map[int]int)

	mostFrequentTarget := -1
	highestFrequency := 0

	for i := 0; i < len(nums)-1; i++ {
		if nums[i] == key {
			target := nums[i+1]
			frequencyCount[target]++

			if frequencyCount[target] > highestFrequency {
				highestFrequency = frequencyCount[target]
				mostFrequentTarget = target
			}
		}
	}

	return mostFrequentTarget
}

The Go implementation follows the same logic as the Python version. Instead of a dictionary, we use a map[int]int to count frequencies.

Go maps automatically return the zero value for missing keys, so incrementing:

frequencyCount[target]++

works even when target has not been seen before.

There are no integer overflow concerns because the maximum count is bounded by nums.length, which is at most 1000. Since slices in Go track length dynamically, we safely iterate only until len(nums) - 1 to avoid out-of-bounds access.

Worked Examples

Example 1

nums = [1,100,200,1,100]
key = 1

We iterate through the array and track target frequencies.

Index nums[i] Is key? Target (nums[i+1]) Frequency Map Current Answer
0 1 Yes 100 {100: 1} 100
1 100 No - {100: 1} 100
2 200 No - {100: 1} 100
3 1 Yes 100 {100: 2} 100

The number 100 follows 1 twice, so the answer is:

100

Example 2

nums = [2,2,2,2,3]
key = 2
Index nums[i] Is key? Target (nums[i+1]) Frequency Map Current Answer
0 2 Yes 2 {2: 1} 2
1 2 Yes 2 {2: 2} 2
2 2 Yes 2 {2: 3} 2
3 2 Yes 3 {2: 3, 3: 1} 2

The target 2 appears three times after key, while 3 appears only once.

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the array once
Space O(n) The hash map may store up to all unique targets

The algorithm performs a single traversal of the input array, making the runtime linear in the number of elements. Each hash map operation, insertion and lookup, takes average O(1) time.

The extra space depends on how many distinct targets appear after key. In the worst case, every number following key is different, requiring up to O(n) additional storage.

Test Cases

solution = Solution()

assert solution.mostFrequent([1, 100, 200, 1, 100], 1) == 100
# Provided example 1

assert solution.mostFrequent([2, 2, 2, 2, 3], 2) == 2
# Provided example 2

assert solution.mostFrequent([1, 2], 1) == 2
# Minimum size input

assert solution.mostFrequent([5, 1, 5, 1, 5, 2], 5) == 1
# Same target repeatedly follows key

assert solution.mostFrequent([1, 2, 1, 3, 1, 2], 1) == 2
# One target appears more often

assert solution.mostFrequent([7, 7, 7, 8], 7) == 7
# Consecutive keys where key follows itself

assert solution.mostFrequent([4, 9, 4, 9, 4, 9], 4) == 9
# Only one unique target

assert solution.mostFrequent([3, 5, 3, 6, 3, 6, 3, 6], 3) == 6
# Larger repeated frequency case

assert solution.mostFrequent([10, 20, 30, 40, 50], 30) == 40
# Key appears only once

Test Summary

Test Why
[1,100,200,1,100], key=1 Validates provided example
[2,2,2,2,3], key=2 Tests consecutive repeated keys
[1,2], key=1 Minimum input size
[5,1,5,1,5,2], key=5 Same target appears repeatedly
[1,2,1,3,1,2], key=1 Ensures frequency counting works correctly
[7,7,7,8], key=7 Key followed by itself
[4,9,4,9,4,9], key=4 Single repeated target
[3,5,3,6,3,6,3,6], key=3 Larger repeated counting case
[10,20,30,40,50], key=30 Key appears exactly once

Edge Cases

Consecutive occurrences of key

A tricky case occurs when key appears multiple times in a row, such as:

nums = [2,2,2,2,3]

Here, 2 repeatedly follows itself. A buggy implementation might accidentally skip overlapping matches or incorrectly move indices. Our implementation checks every index independently, so each valid occurrence is counted correctly.

key appears only once

If key occurs exactly once, such as:

nums = [10,20,30,40,50]
key = 30

there is only one possible target, 40. The algorithm still works because the first valid target immediately becomes the most frequent result.

key near the end of the array

An important boundary condition is avoiding out-of-bounds access when checking nums[i + 1]. Since the algorithm iterates only to len(nums) - 2, it never attempts to access an invalid index. This guarantees safety even if key appears near the end of the array.

Target equals key

Sometimes the number following key is the same as key itself:

nums = [7,7,7,8]
key = 7

The algorithm treats this naturally because it simply counts whatever value appears at nums[i + 1], regardless of whether it matches key. This avoids special-case logic and keeps the implementation simple and correct.