Most Frequent Number Following Key In an Array

Problem 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. Return the target with the maximum count, which is guaranteed to be unique.

Key Insights

• We need to look for instances where key is followed by other numbers in the array.
• A dictionary (hash table) can be used to keep track of counts of numbers that follow the key.
• The problem guarantees that the answer will be unique.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the nums array, as we need to traverse the array once. Space Complexity: O(m) where m is the number of unique targets that can follow the key, as we store counts in a hash table.

Solution

To solve this problem, we will use a hash table (or dictionary) to count how many times each unique number follows the key. The steps are as follows:

1. Initialize a hash table to store counts of each number that follows the key.
2. Traverse the nums array. For each occurrence of key, increment the count of the subsequent number in the hash table.
3. After populating the hash table, find the number with the maximum count.
4. Return this number as the result.

Code Solutions