Most Frequent Number Following Key In an Array

Most Frequent Number Following Key In an Array - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,100,200,1,100], key = 1

› Output: 100

💡 Note: Key 1 appears at indices 0 and 3. Following elements are 100 (twice) and 100. So 100 appears 2 times after key, which is maximum.

Example 2 — Different Followers

$ Input: nums = [2,2,2,2,3], key = 2

› Output: 2

💡 Note: Key 2 appears at indices 0, 1, 2, 3. Following elements are 2, 2, 2, 3. Element 2 follows key 3 times, element 3 follows once.

Example 3 — Single Occurrence

$ Input: nums = [1,2,3,4,5], key = 3

› Output: 4

💡 Note: Key 3 appears only at index 2. The following element is 4, so 4 has count 1 (maximum).

Constraints

2 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000
The test cases will be generated such that key appears in nums and the answer is unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array with key occurrences

Process

Count elements following key

Output

Most frequent follower

Key Takeaway

🎯 Key Insight: Use hash map to count followers of key in single pass

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to scan the array and count which elements follow the given key most frequently. The optimal approach uses a hash map to track follower frequencies in a single pass. Time: O(n), Space: O(k) where k is unique followers.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Hash Map	O(n)	O(k)	Single pass with hash map to count followers
Brute Force	O(n)	O(n)	Check every position for key and count what follows

Optimized Hash Map — Algorithm Steps

Step 1: Iterate through array except last element
Step 2: When nums[i] equals key, increment count for nums[i+1]
Step 3: Return target with maximum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Single Pass

Scan array once, counting as we go

Update Maximum

Track max count and corresponding target

Return Best

Return target with highest frequency

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

typedef struct {
    int target;
    int count;
} TargetCount;

int solution(int* nums, int numsSize, int key) {
    TargetCount counts[MAX_SIZE];
    int countSize = 0;
    int maxCount = 0;
    int result = 0;
    
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == key) {
            int target = nums[i + 1];
            
            // Find if target already exists
            int found = -1;
            for (int j = 0; j < countSize; j++) {
                if (counts[j].target == target) {
                    found = j;
                    break;
                }
            }
            
            int newCount;
            if (found != -1) {
                counts[found].count++;
                newCount = counts[found].count;
            } else {
                counts[countSize].target = target;
                counts[countSize].count = 1;
                newCount = 1;
                countSize++;
            }
            
            if (newCount > maxCount) {
                maxCount = newCount;
                result = target;
            }
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[MAX_SIZE];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int key;
    scanf("%d", &key);
    
    int result = solution(nums, numsSize, key);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, hash map operations are O(1)

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most k unique targets that follow key, where k ≤ n

✓ Linear Space

32.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler