algoadvance

Given an integer array nums and an integer key, you want to find the most frequent number that immediately follows an occurrence of key in the array. Return the number which appears most frequently.

Example:

Input: nums = [1,100,200,1,100], key = 1
Output: 100
Explanation: For `key` = 1, the number following it is `100`. Since `100` appears most frequently, we return 100.

Clarifying Questions

1. Are there guaranteed to be at least one instance of key in the array?
2. How should ties be handled if there are multiple numbers with the same frequency?

These questions help ensure that the input is valid and clarify the expected output in ambiguous cases.

Strategy

1. Initialize a Dictionary: Create a dictionary to keep track of how often each number appears immediately after the key.

2. Traverse the Array: Move through the array and check each element:
   • If the current element is the key, increment the count of the element that follows it (if it exists) in the dictionary.

3. Identify the Most Frequent Follower: After populating the dictionary, find the key-value pair with the highest frequency.

4. Return the Result: Return the number that has the highest frequency as the result.

Code

def mostFrequent(nums, key):
    from collections import defaultdict

    # Dictionary to store the frequency of each number following the key
    freq_dict = defaultdict(int)
    
    for i in range(len(nums) - 1):
        if nums[i] == key:
            freq_dict[nums[i + 1]] += 1
    
    # Determine the most frequent following number
    most_frequent_num = max(freq_dict, key=freq_dict.get)
    
    return most_frequent_num

# Example usage:
nums = [1, 100, 200, 1, 100]
key = 1
print(mostFrequent(nums, key))  # Output: 100

Time Complexity

• Time Complexity: O(n) where n is the length of the array nums. This is because we only need to traverse the array once to populate the dictionary.

• Space Complexity: O(k) where k is the number of distinct elements that appear immediately after the key. In the worst case, this is still O(n).

The solution efficiently counts and identifies the most frequent follower and is well-suited for large input sizes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?