Grokking Advanced Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Solution: Count Elements With Maximum Frequency

Problem Statement

Given an array of positive integers named nums, return the total frequencies of the elements in nums that have a maximum frequency.

The frequency of an element is defined as the number of times that element is repeated in the array.

Examples

Example 1:

  • Input: nums = [3, 2, 2, 3, 1, 4]
  • Output: 4
  • Explanation: Both 2 and 3 appear twice, which is the highest frequency. So, the total frequency is 2 + 2 = 4.

Example 2:

  • Input: nums = [5, 5, 5, 2, 2, 3]
  • Output: 3
  • Explanation: The number 5 appears three times, which is the highest frequency. So, the total frequency is 3.

Example 3:

  • Input: nums = [7, 8, 8, 7, 9, 9]
  • Output: 6
  • Explanation: All elements appear twice. So, total maximum frequency is 2 + 2 + 2 = 6.

Constraints:

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

Solution

To solve this problem, the approach involves counting the occurrences of each number in the array nums. We can achieve this by using a hash map (or dictionary) to store the frequency of each element. Once we have the frequencies, we can determine the highest frequency. Finally, we sum the frequencies of all elements that have this highest frequency.

This approach allows you to efficiently count and compare frequencies in a single pass through the array, followed by a second pass through the frequency counts to compute the result.

Step-by-Step Algorithm

  1. Initialize a hash map (frequencyMap) to store the frequency of each element in the array nums.

    • The keys will be the elements of nums.
    • The values will be the count of occurrences of each element.

  2. Calculate the frequency of array elements.

    • For each element in nums, do the following:
      • If the element is already a key in frequencyMap, increment its value by 1.
      • If the element is not a key in frequencyMap, add it with a value of 1.

  3. Find the maximum frequency from the values in the frequency map.

    • Initialize a variable maxFrequency to 0.
    • Iterate through the values in frequencyMap.
      • If the current value is greater than maxFrequency, update maxFrequency with this value.

  4. Sum the frequencies of elements that have the maximum frequency.

    • Initialize a variable totalMaxFrequency to 0.
    • Iterate through the values in frequencyMap.
      • If the value is equal to maxFrequency, add it to totalMaxFrequency.

  5. Return the total frequency of elements that have the maximum frequency (totalMaxFrequency).

Algorithm Walkthrough

Let's consider the Input: nums = [3, 2, 2, 3, 1, 4]

Image

  1. Initialize frequencyMap: Create an empty hash map to store frequencies.

  2. Iterate through nums:

    • For element 3:
      • frequencyMap: {3: 1}
    • For element 2:
      • frequencyMap: {3: 1, 2: 1}
    • For element 2:
      • frequencyMap: {3: 1, 2: 2}
    • For element 3:
      • frequencyMap: {3: 2, 2: 2}
    • For element 1:
      • frequencyMap: {3: 2, 2: 2, 1: 1}
    • For element 4:
      • frequencyMap: {3: 2, 2: 2, 1: 1, 4: 1}

  3. Find the maximum frequency:

    • Iterate through values in frequencyMap: {3: 2, 2: 2, 1: 1, 4: 1}
      • maxFrequency: 2 (found by comparing each value)

  4. Sum the frequencies of elements with maximum frequency:

    • Initialize totalMaxFrequency to 0.
    • Iterate through values in frequencyMap:
      • For value 3: totalMaxFrequency += 2 (totalMaxFrequency = 2)
      • For value 2: totalMaxFrequency += 2 (totalMaxFrequency = 4)
      • For values 4 and 1: No addition as they are less than maxFrequency.

  5. Return totalMaxFrequency:

    • totalMaxFrequency is 4.

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the array nums. This is because we iterate through the array once to build the frequency map and then iterate through the map to find the maximum frequency and sum the frequencies.
  • Space Complexity: The space complexity is O(m), where m is the number of unique elements in the array. This is due to the space needed to store the frequency map.

An Alternate Approach (One-Pass Solution)

In this one-pass solution, we can use a hash map to count the frequency of each element in the array nums. We will also keep track of the maximum frequency encountered. As we iterate through the array, we update the frequency map and compare the current frequency to the maximum frequency. If a new maximum frequency is found, we reset the total frequencies to this new maximum frequency. If the current frequency matches the maximum frequency, we add it to the total frequencies. This approach ensures that we accurately count the total frequencies of elements with the highest frequency.

Step-by-Step Algorithm

  1. Initialize a hash map named frequencies to store the frequency of each element.
  2. Initialize variables maxFrequency and totalFrequencies to 0.
  3. Iterate through the array nums:
    • Update the frequency of the current element in the hash map.
    • If the current element's frequency is greater than maxFrequency, update maxFrequency and reset totalFrequencies to the current frequency.
    • If the current element's frequency is equal to maxFrequency, add the current frequency to totalFrequencies.
  4. Return the totalFrequencies.

Algorithm Walkthrough

Let's use the first example: [3, 2, 2, 3, 1, 4].

  1. Initialize Data Structures:

    • frequencies (hash map): {}
    • maxFrequency: 0
    • totalFrequencies: 0

  2. Process First Element (3):

    • Update frequencies: {3: 1}
    • frequency of 3: 1
    • Since 1 > maxFrequency (0):
      • Update maxFrequency: 1
      • Update totalFrequencies: 1
    • State: frequencies = {3: 1}, maxFrequency = 1, totalFrequencies = 1

  3. Process Second Element (2):

    • Update frequencies: {3: 1, 2: 1}
    • frequency of 2: 1
    • Since 1 == maxFrequency (1):
      • Update totalFrequencies: 1 + 1 = 2
    • State: frequencies = {3: 1, 2: 1}, maxFrequency = 1, totalFrequencies = 2

  4. Process Third Element (2):

    • Update frequencies: {3: 1, 2: 2}
    • frequency of 2: 2
    • Since 2 > maxFrequency (1):
      • Update maxFrequency: 2
      • Update totalFrequencies: 2
    • State: frequencies = {3: 1, 2: 2}, maxFrequency = 2, totalFrequencies = 2

  5. Process Fourth Element (3):

    • Update frequencies: {3: 2, 2: 2}
    • frequency of 3: 2
    • Since 2 == maxFrequency (2):
      • Update totalFrequencies: 2 + 2 = 4
    • State: frequencies = {3: 2, 2: 2}, maxFrequency = 2, totalFrequencies = 4

  6. Process Fifth Element (1):

    • Update frequencies: {3: 2, 2: 2, 1: 1}
    • frequency of 1: 1
    • Since 1 < maxFrequency (2), no changes to maxFrequency or totalFrequencies.
    • State: frequencies = {3: 2, 2: 2, 1: 1}, maxFrequency = 2, totalFrequencies = 4

  7. Process Sixth Element (4):

    • Update frequencies: {3: 2, 2: 2, 1: 1, 4: 1}
    • frequency of 4: 1
    • Since 1 < maxFrequency (2), no changes to maxFrequency or totalFrequencies.
    • State: frequencies = {3: 2, 2: 2, 1: 1, 4: 1}, maxFrequency = 2, totalFrequencies = 4

  8. Final Output:

    • Return totalFrequencies: 4

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the array nums. This is because we iterate through the array only once.
  • Space Complexity: The space complexity is O(m), where m is the number of unique elements in the array. This is due to the space needed to store the frequency map.
Mark as Completed