algoadvance

Leetcode 2190. Most Frequent Number Following Key In an Array

Problem Statement

You are given an integer array nums and an integer key, which is present in nums.

For every unique integer target such that key is followed immediately by target in the array nums, count the number of occurrences of target in this context, and return the target with the maximum count. If there are multiple targets with the same maximum count, return the smallest one.

Clarifying Questions

  1. Are the numbers in the array positive, negative, or both?
    • The numbers can be both positive and negative.
  2. Can the array be empty or have fewer than 2 elements?
    • No, since the key is guaranteed to be in the array, it implies the array has at least one occurrence of the key.
  3. Can the key be the last element in the array?
    • Yes, but in this case, it won’t have a following number, so it doesn’t count towards any target.

Strategy

  1. Initialize a map to keep track of the counts of each target number that immediately follows an occurrence of key.
  2. Iterate through the array from the first element to the second-to-last element.
  3. For each element, if it equals key, increment the count of the next element in the map.
  4. After populating the map, iterate through the map to determine the target with the maximum count.
  5. Return the target with the maximum count. If there are multiple targets with the same maximum count, return the smallest one.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int mostFrequent(int[] nums, int key) {
        // Map to store the target numbers and their respective counts
        Map<Integer, Integer> targetCount = new HashMap<>();
        
        // Iterate through the array to find key and count the following target numbers
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == key) {
                int target = nums[i + 1];
                targetCount.put(target, targetCount.getOrDefault(target, 0) + 1);
            }
        }
        
        // Find the target with the maximum count
        int mostFrequentTarget = -1;
        int maxCount = 0;
        for (Map.Entry<Integer, Integer> entry : targetCount.entrySet()) {
            int target = entry.getKey();
            int count = entry.getValue();
            if (count > maxCount || (count == maxCount && target < mostFrequentTarget)) {
                mostFrequentTarget = target;
                maxCount = count;
            }
        }
        
        return mostFrequentTarget;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 100, 2, 200, 1, 100}; 
        int key = 1;
        System.out.println(sol.mostFrequent(nums, key)); // Output: 100
    }
}

Time Complexity

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