Most Frequent Number Following Key In an Array

Difficulty: Easy | Acceptance: 59.50% | Paid: No Topics: Array, Hash Table, Counting

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 follows key in the array. In other words, count the number of indices i such that:

0 <= i <= n - 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.

• Examples
• Constraints
• Hash Map Frequency Count
• Fixed Array Counting
• Brute Force Scanning

Examples

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 key = 1.
All other numbers follow key = 1 only once.

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 key = 2.
All other numbers follow key = 2 only once.

Constraints

2 <= nums.length <= 1000
1 <= nums[i] <= 1000
key is an element of nums.

Hash Map Frequency Count

Intuition We can iterate through the array once. Whenever we encounter the key, we look at the next number (the target) and increment its count in a hash map. Finally, we find the target with the highest count.

Steps

• Initialize an empty hash map to store the frequency of targets.
• Iterate through the array from index 0 to n - 2.
• If nums[i] equals key, increment the count for nums[i + 1] in the hash map.
• Iterate through the hash map entries to find the number with the maximum frequency. If there is a tie, the problem guarantees a unique maximum, but we typically prefer the larger number if logic requires it (though the problem statement says the max count target is unique).

from typing import List
from collections import defaultdict

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        counts = defaultdict(int)
        for i in range(len(nums) - 1):
            if nums[i] == key:
                target = nums[i + 1]
                counts[target] += 1
        
        max_count = -1
        result = -1
        for num, count in counts.items():
            if count > max_count:
                max_count = count
                result = num
        return result

Complexity

• Time: O(n) where n is the length of the array.
• Space: O(n) in the worst case to store the frequency map.
• Notes: This is the standard approach for frequency counting problems.

Fixed Array Counting

Intuition The problem constraints state that 1 <= nums[i] <= 1000. Since the range of possible values is small and fixed, we can use an array of size 1001 (or 1002) instead of a hash map. This avoids the overhead of hashing and is slightly faster.

Steps

• Initialize an integer array counts of size 1001 with all zeros.
• Iterate through the array from index 0 to n - 2.
• If nums[i] equals key, increment counts[nums[i + 1]].
• Iterate through the counts array to find the index with the maximum value.

from typing import List

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        counts = [0] * 1001
        for i in range(len(nums) - 1):
            if nums[i] == key:
                target = nums[i + 1]
                counts[target] += 1
        
        max_count = -1
        result = -1
        for i in range(len(counts)):
            if counts[i] > max_count:
                max_count = counts[i]
                result = i
        return result

Complexity

• Time: O(n) where n is the length of the array.
• Space: O(1) because the array size is constant (1001) regardless of input size.
• Notes: This is the most optimal approach for this specific problem due to constraints.

Brute Force Scanning

Intuition For every unique number in the array, we can scan the entire array to count how many times it appears immediately after the key. This is inefficient but conceptually simple.

Steps

• Identify all unique numbers in the array.
• Initialize a variable maxCount to 0 and result to 0.
• For each unique number target:
  • Initialize currentCount to 0.
  • Iterate through the array. If nums[i] == key and nums[i+1] == target, increment currentCount.
  • If currentCount is greater than maxCount, update maxCount and result.
• Return result.

from typing import List

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        unique_nums = set(nums)
        max_count = 0
        result = 0
        
        for target in unique_nums:
            count = 0
            for i in range(len(nums) - 1):
                if nums[i] == key and nums[i + 1] == target:
                    count += 1
            if count > max_count:
                max_count = count
                result = target
                
        return result

Complexity

• Time: O(n²) where n is the length of the array. In the worst case, we iterate through the array for every unique number.
• Space: O(n) to store the set of unique numbers.
• Notes: This approach is not recommended for large inputs but demonstrates a straightforward brute-force logic.