Most Frequent Number Following Key In an Array

Easy

Asked by:

6 views

Topics:

Arrays

You are given a 0-indexed integer array nums. You are also given an integer key, which is present in nums.

For every unique integer target in nums, count the number of times target immediately follows an occurrence of key in nums. In other words, count the number of indices i such that:

0 <= i <= nums.length - 2,
nums[i] == key and,
nums[i + 1] == target.

Return the target with the maximum count. The test cases will be generated such that the target with maximum count is unique.

Example 1:

Input: nums = [1,100,200,1,100], key = 1
Output: 100
Explanation: For target = 100, there are 2 occurrences at indices 1 and 4 which follow an occurrence of key.
No other integers follow an occurrence of key, so we return 100.

Example 2:

Input: nums = [2,2,2,2,3], key = 2
Output: 2
Explanation: For target = 2, there are 3 occurrences at indices 1, 2, and 3 which follow an occurrence of key.
For target = 3, there is only one occurrence at index 4 which follows an occurrence of key.
target = 2 has the maximum number of occurrences following an occurrence of key, so we return 2.

Constraints:

2 <= nums.length <= 1000
1 <= nums[i] <= 1000
The test cases will be generated such that the answer is unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers within the input array, including the key?
If the key doesn't exist in the array, or no number follows it, what should the function return?
Can the input array be empty or null?
If multiple numbers appear with the same highest frequency after the key, which one should I return?
Is the 'key' guaranteed to appear at least once in the array?

Brute Force Solution

Approach

Imagine you are looking through a line of numbers and you want to find the number that appears most often immediately after a specific key number. The brute force strategy involves checking every number after each appearance of the key, and counting how many times each number shows up.

Here's how the algorithm would work step-by-step:

Go through the entire line of numbers, one by one.
Each time you find the key number, look at the number immediately after it.
Keep a tally of all the numbers you see following the key.
After looking at every number in the line, find the number that has the highest count in your tally.
That number is the number that appears most frequently after the key.

Code Implementation

def most_frequent_number_following_key(numbers, key):
    following_number_counts = {}

    for index in range(len(numbers) - 1):
        # Check if the current number is equal to the key.
        if numbers[index] == key:

            following_number = numbers[index + 1]

            # Update count of number following key.
            if following_number in following_number_counts:
                following_number_counts[following_number] += 1
            else:
                following_number_counts[following_number] = 1

    most_frequent_number = None
    max_count = 0

    # Find the number with the highest count.
    for number, count in following_number_counts.items():
        if count > max_count:

            # Update most frequent number and count
            most_frequent_number = number
            max_count = count

    return most_frequent_number

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of n numbers once to find each occurrence of the key. For each key found, it examines the single number immediately following it. Therefore, the time complexity is directly proportional to the number of elements in the array, resulting in O(n).

Space Complexity

O(N) – The algorithm keeps a tally of all the numbers following the key. This tally is implicitly a hash map or dictionary where the keys are the numbers following the specified key, and the values are the counts of each number. In the worst-case scenario, every number in the input array (excluding the key itself) might follow the key and be unique, resulting in a hash map storing up to N-1 counts. Therefore, the auxiliary space used by the tally scales linearly with the input size N, where N is the number of elements in the input array nums. This results in a space complexity of O(N).

Optimal Solution

Approach

We want to find the number that appears most often right after a specific 'key' number in a list. Instead of checking every number combination, we'll focus only on the numbers directly following the key and keep track of how often each of these 'following' numbers appears.

Here's how the algorithm would work step-by-step:

Go through the list one number at a time.
Check if the current number is the 'key' number we are looking for.
If it is the key, then look at the very next number in the list.
Keep a count of how many times each of these 'next' numbers appears after the key. Imagine a scoreboard for each of these next numbers.
After going through the entire list, find the number on the scoreboard with the highest count.
That number with the highest count is the answer: the number that appeared most frequently right after the key.

Code Implementation

def mostFrequentNumberFollowingKey(nums, key):
    following_number_counts = {}
    maximum_frequency = 0
    most_frequent_number = -1

    for i in range(len(nums) - 1):
        # Check if the current number matches the key.
        if nums[i] == key:

            following_number = nums[i + 1]

            # Count frequency of numbers following the key
            if following_number in following_number_counts:
                following_number_counts[following_number] += 1
            else:
                following_number_counts[following_number] = 1

            # Update most frequent number if needed.
            if following_number_counts[following_number] > maximum_frequency:

                maximum_frequency = following_number_counts[following_number]
                most_frequent_number = following_number

    # Return the number that appeared most frequently.
    return most_frequent_number

Big(O) Analysis

Time Complexity

O(n) – The provided solution involves iterating through the input array nums of size n once. Inside the loop, we check if the current element is equal to the key. If it is, we access the next element in the array. The frequency counting of these next elements can be done using a hash map, which offers O(1) average time complexity for insertion and retrieval. Therefore, the dominant operation is the single pass through the array, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm maintains a scoreboard (frequency map) to count the occurrences of numbers following the key. In the worst-case scenario, where every number following the key is distinct, the scoreboard could store up to N-1 unique numbers, where N is the size of the input array. However, since the problem is to find the *most frequent* number, and the number of unique numbers that can *follow* the key will be smaller than the size of the input array, we must allocate space for these at most N - 1 unique numbers. Furthermore, we store a constant amount of extra variables such as the key and the maximum frequency seen so far, independent of the input size. The storage is proportional to the maximum number of different numbers that follow the key, simplifying to O(1) as the size of this counter will at most be the size of the distinct numbers in the input array.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an IllegalArgumentException since no key or follower can exist.
Input array with fewer than two elements	Return 0, since a key followed by a follower requires at least two elements.
Key does not exist in the array	Return 0 as no followers will be found in this case.
Key appears only at the end of the array	Return 0, as there will be no element following the last occurrence of the key.
Multiple keys with the same most frequent follower	The problem guarantees a single most frequent number, so simply return it; the frequency map inherently handles multiple key occurrences.
Array containing very large numbers that could lead to integer overflow when counting	Use a HashMap<Integer, Integer> to store counts to avoid integer overflow issues.
All elements in the array are the same	If the key is that same element, the next element will be that same element as well and its frequency will be (array length -1).
Large input array to test scalability.	The HashMap approach ensures O(n) time complexity and reasonable space usage, handling large arrays efficiently.

Null or empty input array

How to Handle:

Return 0 or throw an IllegalArgumentException since no key or follower can exist.

Input array with fewer than two elements

How to Handle:

Return 0, since a key followed by a follower requires at least two elements.

Key does not exist in the array

How to Handle:

Return 0 as no followers will be found in this case.

Key appears only at the end of the array

How to Handle:

Return 0, as there will be no element following the last occurrence of the key.

Multiple keys with the same most frequent follower

How to Handle:

The problem guarantees a single most frequent number, so simply return it; the frequency map inherently handles multiple key occurrences.

Array containing very large numbers that could lead to integer overflow when counting

How to Handle:

Use a HashMap<Integer, Integer> to store counts to avoid integer overflow issues.

All elements in the array are the same

How to Handle:

If the key is that same element, the next element will be that same element as well and its frequency will be (array length -1).

Large input array to test scalability.

How to Handle:

The HashMap approach ensures O(n) time complexity and reasonable space usage, handling large arrays efficiently.