Solution Explanation: Most Frequent Number Following Key

This problem asks us to find the most frequent number that immediately follows a given key in an array. The solution involves iterating through the array and counting the occurrences of each number following the key.

Approach:

The most efficient approach uses a hash map (or dictionary in Python) to store the counts of numbers following the key. We iterate through the array, and whenever we encounter the key, we increment the count of the subsequent number in our hash map. Finally, we iterate through the hash map to find the number with the maximum count.

Algorithm:

1. Initialization: Create a hash map (e.g., Counter in Python, HashMap in Java) to store the counts of numbers following the key. Initialize a variable max_count to 0 and result to store the number with the maximum count.

2. Iteration: Iterate through the nums array using a loop. For each element at index i:

   • If nums[i] is equal to the key and i + 1 is within the array bounds:
     • Increment the count of nums[i+1] in the hash map.
     • If this count is greater than max_count:
       • Update max_count with the new count.
       • Update result with nums[i+1].

3. Return Result: After iterating through the entire array, return the result.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the nums array. We iterate through the array once. The final lookup for the max count is also O(k) in the worst case, where k is the number of unique elements following the key. However, k is generally much smaller than n, so we can still consider the overall time complexity to be O(n).

• Space Complexity: O(k), where k is the number of unique numbers following the key. In the worst case, we store the counts of all unique numbers. The space used is proportional to the number of unique elements following the key, and not the size of the input array.

Code Examples:

The code examples below demonstrate the solution in several programming languages. Note that Python uses itertools.pairwise for a more concise iteration, but it can be easily adapted for other languages.

Python:

from collections import Counter
from itertools import pairwise
 
class Solution:
    def mostFrequent(self, nums: list[int], key: int) -> int:
        counts = Counter()
        max_count = 0
        result = 0
        for a, b in pairwise(nums):
            if a == key:
                counts[b] += 1
                if counts[b] > max_count:
                    max_count = counts[b]
                    result = b
        return result
 

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int mostFrequent(int[] nums, int key) {
        Map<Integer, Integer> counts = new HashMap<>();
        int maxCount = 0;
        int result = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == key) {
                counts.put(nums[i + 1], counts.getOrDefault(nums[i + 1], 0) + 1);
                if (counts.get(nums[i + 1]) > maxCount) {
                    maxCount = counts.get(nums[i + 1]);
                    result = nums[i + 1];
                }
            }
        }
        return result;
    }
}

JavaScript:

/**
 * @param {number[]} nums
 * @param {number} key
 * @return {number}
 */
var mostFrequent = function(nums, key) {
    const counts = {};
    let maxCount = 0;
    let result = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === key) {
            counts[nums[i + 1]] = (counts[nums[i + 1]] || 0) + 1;
            if (counts[nums[i + 1]] > maxCount) {
                maxCount = counts[nums[i + 1]];
                result = nums[i + 1];
            }
        }
    }
    return result;
};

These code examples all follow the same basic algorithm, demonstrating its adaptability across different programming languages. The choice of data structure (hash map) ensures efficient counting and lookup operations.