algoadvance

Leetcode 2190. Most Frequent Number Following Key In an Array

Problem Statement

You are given an integer array nums and an integer key, in which nums[i] is preceded by nums[i-1] in the array. Your task is to find the most frequent number immediately following an occurrence of key in the array. If there are multiple answers, it is sufficient to return any one of the most frequent numbers.

Clarifying Questions

1. Can the array contain negative numbers?
   • Yes, the array nums can contain negative numbers.
2. What should be returned if the key is not present in the array?
   • The problem guarantees that there is always at least one occurrence of the key in the array.
3. What if two numbers follow the key with the same highest frequency?
   • If there are multiple numbers with the same highest frequency following the key, returning any one of them is acceptable.

Strategy

1. Iterate Through the Array: Traverse the array to find occurrences of the key.
2. Count Frequencies: Use a hash map (unordered_map) to keep track of the frequency of numbers that follow the key.
3. Identify Most Frequent Follower: Find the number with the highest frequency from the hash map.
4. Edge Cases: Handle cases where the key occurs at the end of the array.

Code

#include <vector>
#include <unordered_map>

using namespace std;

int mostFrequentFollowingKey(vector<int>& nums, int key) {
    unordered_map<int, int> frequency_map;
    
    for (size_t i = 0; i < nums.size() - 1; ++i) {
        if (nums[i] == key) {
            int follower = nums[i + 1];
            frequency_map[follower]++;
        }
    }
    
    int most_frequent = -1;
    int max_count = 0;
    
    for (const auto& entry : frequency_map) {
        if (entry.second > max_count) {
            max_count = entry.second;
            most_frequent = entry.first;
        }
    }
    
    return most_frequent;
}

Time Complexity

• Time Complexity: O(n)
  • We traverse the array once, which takes O(n) time.
  • We iterate through the hash map once to find the most frequent follower, which takes O(m) time where m is the number of unique followers. Since m is generally much smaller than n, we can consider this part as O(1) in the context of large n.
• Space Complexity: O(m)
  • The space complexity is O(m) for the hash map, where m is the number of unique followers in nums.

This solution efficiently handles the problem within the given constraints, ensuring minimal time and space overhead.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?