algoadvance

Leetcode 3005. Count Elements With Maximum Frequency

Problem Statement

Given an integer array nums, return the count of the elements in the array that have the maximum frequency.

Clarifying Questions

  1. Input Format:
    • What is the range of number values in nums? Are there negative numbers?
    • What is the length range of nums?

    Example:

     Input: nums = [1, 2, 2, 3, 3, 3]
 Output: 1
    • Explanation: The number 3 has the highest frequency (3 times).
  2. Constraints:
    • Can the array be empty?
    • Should we consider large input sizes for performance tuning?

Strategy

  1. Step 1: Traverse the array and keep a frequency count of each element using a HashMap.
  2. Step 2: Determine the maximum frequency from the frequency map.
  3. Step 3: Count how many elements have this maximum frequency.
  4. Step 4: Return this count.

Code Implementation

import java.util.HashMap;

public class MaximumFrequencyCounter {

    public static int countElementsWithMaxFrequency(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // Edge case for empty array input
        }

        HashMap<Integer, Integer> frequencyMap = new HashMap<>();

        // Step 1: Count frequency of each element
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Find the maximum frequency
        int maxFrequency = 0;
        for (int freq : frequencyMap.values()) {
            if (freq > maxFrequency) {
                maxFrequency = freq;
            }
        }

        // Step 3: Count how many elements have the max frequency
        int count = 0;
        for (int freq : frequencyMap.values()) {
            if (freq == maxFrequency) {
                count++;
            }
        }

        // Step 4: Return the count
        return count;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 3, 3, 3};
        System.out.println(countElementsWithMaxFrequency(nums1)); // Output: 1

        int[] nums2 = {1, 1, 2, 2, 3, 3};
        System.out.println(countElementsWithMaxFrequency(nums2)); // Output: 3

        int[] nums3 = {};
        System.out.println(countElementsWithMaxFrequency(nums3)); // Output: 0
    }
}

Time Complexity

Thus, the overall time complexity is O(N + M), which simplifies to O(N) since N will dominate if there are many duplicates.

This approach efficiently solves the problem within linear time complexity relative to the input size.

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