Problem

Given an array of n numbers from 0 to n-1, find the element occurring most number of times

Examples

Example 1:

1
2
3

Input: nums = [1, 2, 2, 2, 3, 3]
Output: 2
Explanation: The number 2 occurs the most number of times (3 times).

Example 2:

1
2
3

Input: nums = [0, 1, 1, 2, 2, 2, 3]
Output: 2
Explanation: The number 2 occurs the most number of times (3 times).

Solution

This problem is similar to following problem :

We can use some of the method used there.

Method 1 - Brute force

We will compare adjacent elements and increment their count accordingly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {
    public int mostFrequentElement(int[] nums) {
        int n = nums.length;
        int maxCount = 0;
        int mostFrequent = nums[0];

        // Brute force approach: Compare each element with every other element
        for (int i = 0; i < n; i++) {
            int currentCount = 0;
            for (int j = 0; j < n; j++) {
                if (nums[i] == nums[j]) {
                    currentCount++;
                }
            }

            // Update the most frequent element if the current count is greater
            if (currentCount > maxCount) {
                maxCount = currentCount;
                mostFrequent = nums[i];
            }
        }

        return mostFrequent;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 2, 2, 3, 3};
        System.out.println("Most frequent element: " + sol.mostFrequentElement(nums)); // Expected output: 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def most_frequent_element(self, nums: List[int]) -> int:
        n = len(nums)
        max_count = 0
        most_frequent = nums[0]

        # Brute force approach: Compare each element with every other element
        for i in range(n):
            current_count = 0
            for j in range(n):
                if nums[i] == nums[j]:
                    current_count += 1

            # Update the most frequent element if the current count is greater
            if current_count > max_count:
                max_count = current_count
                most_frequent = nums[i]

        return most_frequent

# Example usage
sol = Solution()
nums = [1, 2, 2, 2, 3, 3]
print("Most frequent element:", sol.most_frequent_element(nums))  # Expected output: 2

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - hashing or count array

Here is the approach:

  1. Use a dictionary (or a HashMap) to count the occurrences of each element in the array.
  2. Traverse the array and update the count of each element in the dictionary.
  3. Find the element with the maximum count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public int mostFrequentElement(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int maxCount = 0;
        int mostFrequent = nums[0];

        // Count the occurrences of each element
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            // Update the most frequent element
            if (countMap.get(num) > maxCount) {
                maxCount = countMap.get(num);
                mostFrequent = num;
            }
        }

        return mostFrequent;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 2, 2, 3, 3};
        System.out.println("Most frequent element: " + sol.mostFrequentElement(nums)); // Expected output: 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def most_frequent_element(self, nums: List[int]) -> int:
        count_map = {}
        max_count = 0
        most_frequent = nums[0]

        # Count the occurrences of each element
        for num in nums:
            count_map[num] = count_map.get(num, 0) + 1
            # Update the most frequent element
            if count_map[num] > max_count:
                max_count = count_map[num]
                most_frequent = num

        return most_frequent

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the array. Each element is processed once.
  • 🧺 Space complexity: O(n), to store the count of each element.

Method 3 - Counting sort or normal sort

Time complexity - O(n log n) for comparison based sort and O(n) for counting sort.

Method 4 - Using numbers as index

Method 5 and 6 of XORing and negation, mentioned here - Find two repeating elements in a given ranged array, will not work, but following is the O(n) time and O(1) extra space approach.

Let’s understand by example: Consider the array nums = [2, 3, 3, 5, 3, 4, 1, 7], where n = 8 (number of elements in nums).

  1. Iterate through the input array nums, and for every element nums[i], increment nums[nums[i] % n] by n. The array transforms to [2, 11, 11, 29, 11, 12, 1, 15].
  2. Find the maximum value in the modified array. The index of this maximum value is the most frequent element (the index of 29 is 3).
  3. To restore the original array, iterate through the array again and set nums[i] = nums[i] % n for all i from 0 to n-1.

Note:

  • If we replace the condition nums[i] / n > max with nums[i] > n, the solution will only print one repeating element and will not work for printing all maximum repeating elements. For example, given [2, 3, 2, 3], the solution would only print 3. To print both 2 and 3 (since both occur the maximum number of times), use the maximum quotient nums[i] / n instead of the maximum value in step 2.
  • Be cautious as this method may cause overflow if adding n repeatedly makes the value exceed INT_MAX.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public int mostFrequentElement(int[] arr) {
        int n = arr.length;
        int maxCount = 0;
        int mostFrequent = -1;

        // Increment the counts based on modulo operation
        for (int i = 0; i < n; i++) {
            arr[arr[i] % n] += n;
        }

        // Find the maximum value's index (most frequent element)
        for (int i = 0; i < n; i++) {
            if (arr[i] / n > maxCount) {
                maxCount = arr[i] / n;
                mostFrequent = i;
            }
        }

        // Optionally, restore the original array
        for (int i = 0; i < n; i++) {
            arr[i] = arr[i] % n;
        }

        return mostFrequent;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def mostFrequentElement(self, arr: List[int]) -> int:
        n = len(arr)
        max_count = 0
        most_frequent = -1

        # Increment the counts based on modulo operation
        for i in range(n):
            arr[arr[i] % n] += n

        # Find the maximum value's index (most frequent element)
        for i in range(n):
            if arr[i] // n > max_count:
                max_count = arr[i] // n
                most_frequent = i

        # Optionally, restore the original array
        for i in range(n):
            arr[i] = arr[i] % n

        return most_frequent

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)