# Most Frequent Number Following Key In an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/most-frequent-number-following-key-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/most-frequent-number-following-key-in-an-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## 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 _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.

# Approaches
## Brute Force with Nested Loops
This approach involves iterating through all unique numbers in the input array and, for each unique number, counting its occurrences immediately following the `key`. It uses nested loops: an outer loop for each potential target and an inner loop to scan the array.
**Time:** O(U * N), where N is the length of the `nums` array and U is the number of unique elements. In the worst case, U can be proportional to N, leading to O(N^2) time complexity. · **Space:** O(U), where U is the number of unique elements in `nums`. In the worst case, U can be equal to N, leading to O(N) space complexity to store the set of unique numbers.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient, especially for large arrays with many unique numbers.; Performs redundant scans of the array.
### Explanation
The brute-force method first identifies all unique numbers present in the `nums` array to serve as potential candidates for the `target`. It then iterates through each of these unique candidates. For every candidate, it scans the entire `nums` array again to count how many times this candidate appears right after the specified `key`. While doing this, it keeps track of the candidate with the highest count seen so far. This process is straightforward but computationally expensive due to the repeated scanning of the input array.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int mostFrequent(int[] nums, int key) {
        Set<Integer> uniqueTargets = new HashSet<>();
        for (int num : nums) {
            uniqueTargets.add(num);
        }

        int maxCount = 0;
        int result = -1;

        for (int target : uniqueTargets) {
            int currentCount = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] == key && nums[i + 1] == target) {
                    currentCount++;
                }
            }
            if (currentCount > maxCount) {
                maxCount = currentCount;
                result = target;
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a `Set` of all numbers in `nums` to get the unique potential targets.
- Initialize `maxCount = 0` and `result = -1`.
- Iterate through each `target` in the set of unique numbers.
- For each `target`, initialize a `currentCount = 0`.
- Iterate through the `nums` array from `i = 0` to `nums.length - 2`.
- If `nums[i] == key` and `nums[i+1] == target`, increment `currentCount`.
- After the inner loop, if `currentCount > maxCount`, update `maxCount = currentCount` and `result = target`.
- After iterating through all unique targets, return `result`.

## Single Pass with a HashMap
A more efficient approach is to iterate through the array just once. We can use a HashMap to store the frequency of each number that appears immediately after the `key`. After populating the map, we find the number with the highest frequency.
**Time:** O(N), where N is the length of the array. We perform one pass to populate the map (O(N)) and another pass to find the max frequency (O(U), where U is the number of unique targets, and U <= N). The total time is dominated by the first pass, resulting in O(N). · **Space:** O(U), where U is the number of unique targets that follow the key. In the worst case, this can be O(N).
**Pros:** Significantly faster than the brute-force approach with O(N) time complexity.; Only requires a single pass over the input array to gather counts.
**Cons:** Uses extra space for the HashMap, which can be up to O(N) in the worst case.; Slight overhead from hashing and map operations compared to a simple array.
### Explanation
This approach significantly improves performance by avoiding nested loops. We traverse the `nums` array a single time. During this traversal, whenever we find an element `nums[i]` that matches the `key`, we look at the next element `nums[i+1]` (the target). We use a HashMap to maintain a running count of how many times each target has been seen. The target is the map's key, and its frequency is the value. After this single pass, the map contains all targets and their frequencies. A final, quick iteration over the map's entries is performed to find the target with the maximum frequency.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int mostFrequent(int[] nums, int key) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == key) {
                int target = nums[i + 1];
                counts.put(target, counts.getOrDefault(target, 0) + 1);
            }
        }

        int maxCount = 0;
        int result = -1;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                result = entry.getKey();
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` called `counts` to store the frequency of each target.
- Iterate through the `nums` array from `i = 0` to `nums.length - 2`.
- If `nums[i]` is equal to `key`, get the `target` which is `nums[i+1]`.
- Increment the count for this `target` in the `counts` map using `map.getOrDefault(target, 0) + 1`.
- After the loop, initialize `maxCount = 0` and `result = -1`.
- Iterate through the entries of the `counts` map.
- For each entry, if its value (count) is greater than `maxCount`, update `maxCount` and set `result` to the entry's key (the target).
- Return `result`.

## Optimized Single Pass with a Frequency Array
This is the most efficient approach, leveraging the problem's constraints on the values within the array (`1 <= nums[i] <= 1000`). Instead of a HashMap, we can use a simple array as a frequency map. This eliminates the overhead of hashing and provides constant space complexity.
**Time:** O(N), where N is the length of the array. We iterate through the array once to count frequencies and find the maximum simultaneously. · **Space:** O(1), as the size of the `counts` array (1001) is constant and does not depend on the size of the input array `nums`.
**Pros:** Optimal time complexity of O(N).; Constant space complexity, O(1), making it very memory-efficient.; Generally faster in practice than the HashMap approach due to direct array access and better cache locality.
**Cons:** This approach is only applicable because the range of values in `nums` is known and small.
### Explanation
By observing the constraint that all numbers in the array are between 1 and 1000, we can optimize the HashMap approach. Instead of a map, we use a simple integer array of size 1001 as a direct-access table or frequency map. The index of the array corresponds to the `target` number, and the value at that index stores its frequency. We iterate through the `nums` array once. When we find a `key`, we increment the count for the following `target` at `counts[target]`. We can also track the most frequent target on-the-fly within the same loop, eliminating the need for a second pass. This method is faster due to direct memory access and uses constant extra space.

```java
class Solution {
    public int mostFrequent(int[] nums, int key) {
        int[] counts = new int[1001];
        int maxCount = 0;
        int result = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == key) {
                int target = nums[i + 1];
                counts[target]++;
                if (counts[target] > maxCount) {
                    maxCount = counts[target];
                    result = target;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Create an integer array `counts` of size 1001 (to handle values from 1 to 1000) and initialize it with zeros.
- Initialize `maxCount = 0` and `result = 0`.
- Iterate through the `nums` array from `i = 0` to `nums.length - 2`.
- If `nums[i]` is equal to `key`:
  - Let `target = nums[i+1]`.
  - Increment the count for this target: `counts[target]++`.
  - Check if the new count for this `target` is greater than `maxCount`.
  - If it is, update `maxCount = counts[target]` and `result = target`.
- After the loop, return `result`. This approach finds the max on-the-fly, avoiding a second loop.

# Solutions
### Java

```java
class Solution {
public
  int mostFrequent(int[] nums, int key) {
    int[] cnt = new int[1001];
    int ans = 0, mx = 0;
    for (int i = 0; i < nums.length - 1; ++i) {
      if (nums[i] == key) {
        if (mx < ++cnt[nums[i + 1]]) {
          mx = cnt[nums[i + 1]];
          ans = nums[i + 1];
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} key * @return {number} */ var mostFrequent =
  function (nums, key) {
    const cnt = Array(Math.max(...nums) + 1).fill(0);
    let [ans, mx] = [0, 0];
    for (let i = 0; i < nums.length - 1; ++i) {
      if (nums[i] === key) {
        if (mx < ++cnt[nums[i + 1]]) {
          mx = cnt[nums[i + 1]];
          ans = nums[i + 1];
        }
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int mostFrequent(vector<int> &nums, int key) {
    int cnt[1001]{};
    int ans = 0, mx = 0;
    for (int i = 0; i < nums.size() - 1; ++i) {
      if (nums[i] == key) {
        if (mx < ++cnt[nums[i + 1]]) {
          mx = cnt[nums[i + 1]];
          ans = nums[i + 1];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int: cnt = Counter() ans = mx = 0 for a, b in pairwise(nums): if a == key: cnt[b] += 1 if mx < cnt[b]: mx = cnt[b] ans = b return ans

```