Count Elements With Maximum Frequency

EASY

Description

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Approaches

Checkout 3 different approaches to solve Count Elements With Maximum Frequency. Click on different approaches to view the approach and algorithm in detail.

One-Pass with Frequency Array

This is the most efficient approach, tailored to the problem's constraints (1 <= nums[i] <= 100). Instead of a hash map, we use a simple array of size 101 as a frequency map. This eliminates the overhead of hashing and provides constant-time access for frequency updates, leading to better performance and constant space complexity.

Algorithm

Create an integer array freq of size 101, initialized to zeros.
Initialize maxFreq = 0 and totalFreq = 0.
Iterate through each num in the nums array.
Increment freq[num] and get its currentFreq.
If currentFreq > maxFreq:
- Set maxFreq = currentFreq.
- Set totalFreq = currentFreq.
Else if currentFreq == maxFreq:
- Add maxFreq to totalFreq.
After the loop, return totalFreq.

Given the constraint that all numbers in nums are between 1 and 100, we can replace the HashMap with a simple integer array of size 101. This array will act as a direct-access frequency map, where freq[i] stores the frequency of the number i.

The logic is identical to the single-pass hash map approach. We iterate through nums once, maintaining maxFreq and totalFreq variables. For each num:

We increment freq[num].
We check the new frequency freq[num] against maxFreq and update maxFreq and totalFreq accordingly. This method is faster due to direct array indexing instead of hash computations and has a constant space complexity because the array size is fixed regardless of the input size.

class Solution {
    public int maxFrequencyElements(int[] nums) {
        int[] freq = new int[101]; // Constraints: 1 <= nums[i] <= 100
        int maxFreq = 0;
        int totalFreq = 0;

        for (int num : nums) {
            freq[num]++;
            int currentFreq = freq[num];

            if (currentFreq > maxFreq) {
                maxFreq = currentFreq;
                totalFreq = currentFreq;
            } else if (currentFreq == maxFreq) {
                totalFreq += maxFreq;
            }
        }
        return totalFreq;
    }
}

Complexity Analysis

Time Complexity: O(N), for a single pass over the `nums` array. Array access is an O(1) operation.Space Complexity: O(1). The space used by the frequency array is constant (101 integers), regardless of the size of the input array `nums`.

Pros and Cons

Pros:

Most efficient in terms of both time and space due to the use of a fixed-size array and a single pass.
Simple and clean implementation with no hashing overhead.

Cons:

This solution is specific to the given constraints on the range of numbers. It would not be suitable if the numbers could be very large or negative without modification.

Code Solutions

Checking out 3 solutions in different languages for Count Elements With Maximum Frequency. Click on different languages to view the code.

class Solution {
public
  int maxFrequencyElements(int[] nums) {
    int[] cnt = new int[101];
    for (int x : nums) {
      ++cnt[x];
    }
    int ans = 0, mx = -1;
    for (int x : cnt) {
      if (mx < x) {
        mx = x;
        ans = x;
      } else if (mx == x) {
        ans += x;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Count Elements With Maximum Frequency

Patterns:

Counting

Data Structures:

ArrayHash Table

Companies:

Capgemini |CRED |