LeetCode 2190. Most Frequent Number Following Key In an Array Solution in Java, C++, Python & More | Explanation + Code

Description

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.

Solutions

Solution 1: Traversal and Counting

We use a hash table or an array cnt to record the number of occurrences of each target, and use a variable mx to maintain the maximum number of occurrences of target. Initially, mx = 0.

Traverse the array nums. If nums[i] = key, increment the count of nums[i + 1] in cnt[nums[i + 1]]. If mx \lt cnt[nums[i + 1]], update mx = cnt[nums[i + 1]] and update the answer ans = nums[i + 1].

After the traversal, return the answer ans.

The time complexity is O(n), and the space complexity is O(M). Here, n and M are the length of the array nums and the maximum value of the elements in the array nums, respectively.

PythonJavaC++GoTypeScriptJavaScriptPHP

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(code-box)

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; } }(code-box)

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; } };(code-box)

func mostFrequent(nums []int, key int) (ans int) { cnt := [1001]int{} mx := 0 for i, x := range nums[1:] { if nums[i] == key { cnt[x]++ if mx < cnt[x] { mx = cnt[x] ans = x } } } return }(code-box)

function mostFrequent(nums: number[], key: number): number { const cnt: number[] = 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; }(code-box)

/** * @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; };(code-box)

class Solution { function mostFrequent($nums, $key) { $cnt = array_fill(0, max($nums) + 1, 0); $ans = 0; $mx = 0; for ($i = 0; $i < count($nums) - 1; ++$i) { if ($nums[$i] === $key) { $cnt[$nums[$i + 1]]++; if ($mx < $cnt[$nums[$i + 1]]) { $mx = $cnt[$nums[$i + 1]]; $ans = $nums[$i + 1]; } } } return $ans; } }(code-box)