Most Frequent Number Following Key In an Array

Easy
1791.

Most Frequent Number Following Key In an Array

Most Frequent Number Following Key In an Array is an easy coding problem on arrays, hash table and counting, asked in Google interviews.

You are given an integer array nums and an integer key that occurs in nums.

For every distinct value target in nums, count the indices i with 0 <= i <= nums.length - 2, nums[i] == key and nums[i + 1] == target — that is, how often target comes immediately after an occurrence of key.

Return the target with the maximum count. The input guarantees that this target is unique.

Example 1

Input
nums = [3,8,3,8,3,5], key = 3
Output
8
Explanation
The values right after a 3 are 8, 8 and 5, so 8 follows the key twice.

Example 2

Input
nums = [9,9,9,4], key = 9
Output
9
Explanation
After the 9s come 9, 9 and 4: the key can follow itself.

Example 3

Input
nums = [6,1], key = 6
Output
1

Constraints

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • key occurs in nums
  • the answer is unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} key
 * @return {number}
 */
var mostFrequent = function(nums, key) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Most Frequent Number Following Key In an Array — Solution

Most Frequent Number Following Key In an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Most Frequent Number Following Key In an Array is an easy coding problem on arrays, hash table and counting, asked in Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums and an integer key that occurs in nums.

For every distinct value target in nums, count the indices i with 0 <= i <= nums.length - 2, nums[i] == key and nums[i + 1] == target — that is, how often target comes immediately after an occurrence of key.

Return the target with the maximum count. The input guarantees that this target is unique.

Example 1

Input: nums = [3,8,3,8,3,5], key = 3
Output: 8
Explanation: The values right after a 3 are 8, 8 and 5, so 8 follows the key twice.

Example 2

Input: nums = [9,9,9,4], key = 9
Output: 9
Explanation: After the 9s come 9, 9 and 4: the key can follow itself.

Example 3

Input: nums = [6,1], key = 6
Output: 1

Constraints

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • key occurs in nums
  • the answer is unique

Hints for Most Frequent Number Following Key In an Array

  1. Hint 1

    Only the element right after each occurrence of key matters.

  2. Hint 2

    Walk the array once and, whenever nums[i] == key, count nums[i + 1].

  3. Hint 3

    Return the value with the largest count — values are at most 1000, so an array of counters works.

How to solve Most Frequent Number Following Key In an Array

A single scan of adjacent pairs (nums[i], nums[i + 1]) collects exactly the values that follow key; the most counted one is the answer.

Approach

  1. Create counters for the values 1–1000.
  2. For i from 0 to n - 2, if nums[i] == key, increment count[nums[i + 1]].
  3. Return the value with the largest count.

Why it works

Each index i contributes to exactly one target — the element after it — and only when nums[i] is the key, which is precisely the definition of the count. Uniqueness of the maximum makes the answer well defined.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Stop at n - 2: the last element has no successor.
  • Count what follows the key, not the key's own occurrences.

Reference solution

Python

from typing import List

def mostFrequent(nums: List[int], key: int) -> int:
    cnt = [0] * 1001
    for i in range(len(nums) - 1):
        if nums[i] == key:
            cnt[nums[i + 1]] += 1
    return max(range(1001), key=lambda v: cnt[v])

Java

public static int mostFrequent(int[] nums, int key) {
    int[] cnt = new int[1001];
    int best = 0;
    for (int i = 0; i + 1 < nums.length; i++) {
        if (nums[i] != key) continue;
        int t = nums[i + 1];
        cnt[t]++;
        if (cnt[t] > cnt[best]) best = t;
    }
    return best;
}

C++

int mostFrequent(vector<int>& nums, int key) {
    vector<int> cnt(1001, 0);
    int best = 0;
    for (size_t i = 0; i + 1 < nums.size(); i++) {
        if (nums[i] != key) continue;
        int t = nums[i + 1];
        if (++cnt[t] > cnt[best]) best = t;
    }
    return best;
}

JavaScript

var mostFrequent = function(nums, key) {
    var cnt = new Array(1001).fill(0);
    var best = 0;
    for (var i = 0; i + 1 < nums.length; i++) {
        if (nums[i] !== key) continue;
        var t = nums[i + 1];
        cnt[t]++;
        if (cnt[t] > cnt[best]) best = t;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets