Problem Statement

Given an integer array nums of size n. Return all elements which appear more than n/3 times in the array. The output can be returned in any order.

Examples

Example 1:

Input: nums = [1, 2, 1, 1, 3, 2]
Output: [1]

Explanation: Here, n / 3 = 6 / 3 = 2
Therefore the elements appearing 3 or more times is: [1]

Example 2:

Input: nums = [1, 2, 1, 1, 3, 2]
Output: [1, 2]

Explanation: Here, n / 3 = 7 / 3 = 2
Therefore the elements appearing 3 or more times is: [1, 2]

Example 3:

Input: nums = [1, 2, 1, 1, 3, 2, 2, 3]
Output: [1, 2]

Explanation: Here, n / 3 = 8 / 3 = 2
Therefore the elements appearing 3 or more times is: [1, 2]

Different Approaches

Key Observations:

• There can be at most two elements that appear more than n/3 times.

1️⃣ Brute Force Approach

Intuition:

The naive way is to use nested loops to count the occurrences of each of the elements and if the count is greater than one third of the size of array, include the element in the answer.

Can there be more than 2 majority elements ? Let's understand the scenario!

To understand why there can't be more than two majority elements (elements that appear more than n/3 times) in an array of size n, let's use a simple mathematical reasoning. A majority element in this context is defined as an element that appears more than n/3 times in the array. For an element to be a majority element, it must appear more than n/3 times. Let's assume there are more than two such majority elements. Let's denote these elements as A, B, and C.

Since each of these elements appears more than n/3 times, the combined frequency of these three elements would be: frequency of 𝐴 + frequency of 𝐵 + frequency of 𝐶 > 𝑛/3 + 𝑛/3 + 𝑛/3 = 𝑛

Now, the total number of occurrences of all elements in the array cannot exceed n, the size of the array. This means the combined frequency of any three elements each appearing more than n/3 times would exceed the total size of the array, which is a contradiction. Therefore, it's mathematically impossible for there to be more than two elements in the array that each appear more than n/3 times.

Approach:

1. Iterate in the array to select the elements of the array one by one. Now, for each unique element, run another loop and count its occurrence in the given array. If any element occurs more than the floor of (N/3), include it in our answer.
2. While traversing if any element that is already included in our answer is found, just skip it. When the answer array size is already 2, break out of loop, as there cant be more than 2 elements.
3. Return the answer array or -1 if no such element is found.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find majority elements in an array
    vector<int> majorityElementTwo(vector<int>& nums) {
        
        // Size of the array
        int n = nums.size(); 
        
        // List of answers
        vector<int> result;
        
         for (int i = 0; i < n; i++) {
             
        /*Checking if nums[i] is not 
        already part of the answer*/
        if (result.size() == 0 || result[0] != nums[i]) {
            
            int cnt = 0;
            
            for (int j = 0; j < n; j++) {
                // counting the frequency of nums[i]
                if (nums[j] == nums[i]) {
                    cnt++;
                }
            }

            // check if frquency is greater than n/3:
            if (cnt > (n / 3))
                result.push_back(nums[i]);
        }
        
        //if result size is equal to 2 break out of loop
        if (result.size() == 2) break;
    }
    
    //return the majority elements
    return result;
    }
};

int main() {
    vector<int> arr = {11, 33, 33, 11, 33, 11};
    
    // Create an instance of Solution class
    Solution sol;

    vector<int> ans = sol.majorityElementTwo(arr);
    
    // Print the majority elements found
    cout << "The majority elements are: ";
    for (auto it : ans) {
        cout << it << " ";
    }
    cout << "\n";

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2), where N is the size of the array. As for every element of the array the inner loop runs for N times.
• Space Complexity: O(1) the space used is so small that it can be considered constant.

2️⃣ Better Approach

Intuition:

A better idea is to use a data structure to reduce the number of look-up operations and hence to reduce the time complexity. Moreover, we have been calculating the count of the same element again and again, so reduce that also.

Approach:

1. Use a hashmap and store the elements as pairs. (Can also use frequency array based on the size of nums). Here the key will be the element of the array and the value will be the number of times it occurs.
2. Traverse the whole array and update the occurrence of each element.
3. After that, check the map if the value for any element is greater than the floor of N/3. If yes, include it in the answer. Else, iterate forward. At any point if we find that the size of answer array is 2, break out of the loop. Finally, return the answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find majority elements in an array
    vector<int> majorityElementTwo(vector<int>& nums) {
        
        // size of the array
        int n = nums.size();
        
        // list of answers
        vector<int> result;
        
        // declaring a map
        unordered_map<int, int> mpp;
        
        // least occurrence of the majority element
        int mini = int(n / 3) + 1;
        
        // storing the elements with its occurrence
        for (int i = 0; i < n; i++) {
            mpp[nums[i]]++;
            
            // checking if nums[i] is the majority element
            if (mpp[nums[i]] == mini) {
                result.push_back(nums[i]);
            }
            
            // if result size is equal to 2 break out of loop
            if (result.size() == 2) {
                break;
            }
        }
        
        // return the majority elements
        return result;
    }
};

int main() {
    vector<int> arr = {11, 33, 33, 11, 33, 11};
    
    // Create an instance of Solution class
    Solution sol;
    
    vector<int> ans = sol.majorityElementTwo(arr);
    
    // Print the majority elements found
    cout << "The majority elements are: ";
    for (auto it : ans) {
        cout << it << " ";
    }
    cout << "\n";
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N * logN), where N is size of the given array. For using a map data structure, where insertion in the map takes logN time. And we are doing it for N elements. So, it results in the first term O(N*logN). On using unordered_map instead, the first term will be O(N) for the best and average case and for the worst case, it will be O(N^2).
• Space Complexity: O(N) for using a map data structure. A list that stores a maximum of 2 elements is also used, but that space used is so small that it can be considered constant.

3️⃣ Optimal Approach

Algorithm Steps:

1. Candidate Selection Phase: Traverse through the array and use two candidate variables (candidate1, candidate2) and two count variables (count1, count2). As you iterate:
   • If the current element matches one of the candidates, increment its count.
   • If count1 or count2 is zero, assign the current element to that candidate and set the count to 1.
   • If the current element matches neither candidate, decrement both counts.
2. Validation Phase: After finding the two candidates, iterate through the array again and count their occurrences to ensure they appear more than n/3 times.

Code:

#include <iostream>
#include <vector>

using namespace std;

vector<int> majorityElement(vector<int>& nums) {
    int n = nums.size();
    
    // Edge case: if the array has less than 2 elements, return the array itself.
    if (n == 0) return {};
    if (n == 1) return {nums[0]};
    
    // Step 1: Find potential candidates
    int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else if (num == candidate2) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    // Step 2: Validate the candidates
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else if (num == candidate2) {
            count2++;
        }
    }

    vector<int> result;
    if (count1 > n / 3) result.push_back(candidate1);
    if (count2 > n / 3) result.push_back(candidate2);

    return result;
}

int main() {
    vector<int> nums = {3, 2, 3};
    
    vector<int> result = majorityElement(nums);
    
    cout << "Elements that appear more than n/3 times: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:
  • O(n): The algorithm makes two passes over the array, resulting in a linear time complexity.
• Space Complexity:
  • O(1): The algorithm uses constant extra space, as we only need a few integer variables for candidates and counts.