We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Most Frequent Number Following Key In an Array

Number: 2312

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an integer array nums and an integer key (which is guaranteed to be in nums), count for every unique integer target the number of times target immediately follows an occurrence of key in nums. Return the target with the maximum count, with the guarantee that this target is unique.

Key Insights

  • Scan the array only once, checking each index i (up to n-2) to see if nums[i] equals key.
  • Use a counting data structure (like a dictionary or hash map) to keep track of how many times each candidate (nums[i+1]) appears after key.
  • Return the target with the highest frequency.

Space and Time Complexity

Time Complexity: O(n) where n is the length of nums. Space Complexity: O(n) in the worst case when many different numbers follow key.

Solution

The solution involves iterating over the array from the first index until the second last. Each time we find an occurrence of key, we increment the count for the immediate next number in a hash map (or dictionary). After processing the array, we determine which target has the highest count, ensuring that the result is unique. Key gotchas include iterating only until the second last element and correctly initializing and updating the hash map keys.

Code Solutions

def mostFrequent(nums, key):
    # Initialize a dictionary to count frequency for each target following key
    count_map = {}
    # Loop through elements except the last one since there is no subsequent element
    for i in range(len(nums) - 1):
        if nums[i] == key:
            # Increment count for the number following key
            next_num = nums[i + 1]
            count_map[next_num] = count_map.get(next_num, 0) + 1
    # Return the target with the maximum frequency
    return max(count_map, key=count_map.get)

# Example usage:
print(mostFrequent([1, 100, 200, 1, 100], 1))
← Back to All Questions