Problem

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 thetarget with themaximum count. The test cases will be generated such that the target with maximum count is unique.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5

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.

Solution

Method 1 - Hash Map Counting

Intuition

We count how many times each number immediately follows the key in the array. The answer is the number with the highest count.

Approach

Iterate through the array, and for each index where nums[i] == key, increment the count for nums[i+1]. Return the number with the highest count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public int mostFrequent(int[] nums, int key) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == key) {
                count.put(nums[i+1], count.getOrDefault(nums[i+1], 0) + 1);
            }
        }
        int ans = -1, max = 0;
        for (int k : count.keySet()) {
            if (count.get(k) > max) {
                max = count.get(k);
                ans = k;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7

def mostFrequent(nums, key):
    from collections import Counter
    count = Counter()
    for i in range(len(nums) - 1):
        if nums[i] == key:
            count[nums[i+1]] += 1
    return max(count, key=lambda x: count[x])

Complexity

  • ⏰ Time complexity: O(n) — One pass through the array.
  • 🧺 Space complexity: O(n) — For the count map.