Most Frequent Number Following Key In An Array - Leetcode Solution

Problem Statement:

Given an array of integers nums and an integer key, return the most frequently occurring integer after the key in the array.

If multiple numbers have the same highest frequency, return the smallest one.

Example 1: Input: nums = [3,4,3,2,4,2,4,5,6,5], key = 4 Output: 3 Explanation: The integers that come after 4 are [3,2,5,6,5]. The most frequently occurring of these is 3.

Example 2: Input: nums = [1,2,3,2,3,4,3,4,5,6], key = 4 Output: 5 Explanation: The integers that come after 4 are [3,5,6]. Both 5 and 6 occur once, but 5 is smaller.

Approach:

We will use a hash map to store the frequency of each number that comes after the key in the array. We will iterate through the array and count the frequency of each number that comes after the key.

After counting the frequency of each number, we will find the number with the highest frequency. If multiple numbers have the highest frequency, we will return the smallest one.

Algorithm:

1. Initialize a hash map to store the frequency of each number that comes after the key.
2. Initialize a variable maxFreq to store the maximum frequency of a number that comes after the key.
3. Iterate through the array and count the frequency of each number that comes after the key.
4. Find the number with the maximum frequency and store it in a variable maxNum.
5. Iterate through the hash map and find the number with the maximum frequency that is also the smallest.
6. Return the number with the highest frequency that is also the smallest.

Code:

The Python implementation of the above algorithm is as follows:

def findMostFrequent(nums, key): freq = {} maxFreq = 0 maxNum = 0

# Count the frequency of each number that comes after the key
for i in range(len(nums)):
    if nums[i] == key and i < len(nums)-1:
        if nums[i+1] not in freq:
            freq[nums[i+1]] = 1
        else:
            freq[nums[i+1]] += 1
        # Update max frequency and max number
        if freq[nums[i+1]] > maxFreq:
            maxFreq = freq[nums[i+1]]
            maxNum = nums[i+1]

# Find the number with the maximum frequency that is also the smallest
for key in freq:
    if freq[key] == maxFreq:
        if key < maxNum:
            maxNum = key

return maxNum

1