Q1. You have to given an array A of size N. Find all the elements which appear more than floor(N/3) times in the given array. There is a condition that you have to do your job in O(N) time complexity and O(1) space complexity.

Question Link - Click Here to Solve This Problem

Intuition Behind the Algorithm

The algorithm is designed based on the idea that if a number appears more than N/3 times in an array, there can be at most two such numbers. This is because if there were three or more such numbers, their total count would exceed N, which is impossible.

To identify these potential candidates, the algorithm maintains two counters and two potential elements. The key idea is to pair different elements and effectively 'cancel' them out, keeping track of potential majority elements.

#include<iostream>
#include<vector>

using namespace std;

// Function to find all elements appearing more than floor(N/3) times in the array
vector<int> majorityElements(vector<int> v) {
    // Initialize the first potential majority element and its count
    int element1 = v[0];
    int count1 = 1;

    // Initialize the second potential majority element and its count
    int element2 = 0;
    int count2 = 0;

    // First pass: Identify potential majority elements
    for (int i = 1; i < v.size(); i++) {
        if (element1 == v[i]) {
            count1++;
        } else if (element2 == v[i]) {
            count2++;
        } else if (count1 == 0) {
            element1 = v[i];
            count1 = 1;
        } else if (count2 == 0) {
            element2 = v[i];
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    // Reset counts for the second pass
    count1 = count2 = 0;

    // Second pass: Confirm the majority elements
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == element1) count1++;
        else if (v[i] == element2) count2++;
    }

    // Prepare the answer vector
    vector<int> ans;
    if (count1 > v.size() / 3) {
        ans.push_back(element1);
    }
    if (count2 > v.size() / 3) {
        ans.push_back(element2);
    }

    return ans;
}

int main() {
    // Read the size of the array
    int n;
    cin >> n;

    // Read the elements of the array
    vector<int> v;
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        v.push_back(x);
    }

    // Find majority elements
    vector<int> ans = majorityElements(v);

    // Output the results
    if (ans.size() == 0) {
        cout << "No Majority Elements" << endl;
    } else {
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << ' ';
        }
    }

    cout << endl;

    return 0;
}

Description of the Code

1. Initialization:

• Two elements (element1 and element2) are initialized with the first element of the array and a dummy value (0), respectively.
• Corresponding counts (count1 and count2) are set to 1 and 0.

2. First Pass - Identifying Potential Majority Elements:

• Iterate through the array:
  

a) Increment the count of element1 or element2 if the current element matches either.
b) If count1 or count2 is zero, replace the respective element with the current element and reset its count to 1.
c) If the current element matches neither element1 nor element2, decrement both count1 and count2.

• This step ensures that by the end, element1 and element2 are the candidates for being the majority elements.

3. Reset Counts:

• Reset count1 and count2 to zero for the second pass.

4. Second Pass - Confirming Majority Elements:

• Iterate through the array again, counting the occurrences of element1 and element2.
• If the count of either exceeds N/3, they are confirmed as majority elements.

5. Preparing the Answer:

• Check the final counts of element1 and element2.
• If their counts exceed N/3, add them to the answer vector.

6. Output:

• If no majority elements are found, output "No Majority Elements".
• Otherwise, output the majority elements.

Time and Space Complexity

• Time Complexity: O(N). The array is iterated over twice, making the time complexity linear.
• Space Complexity: O(1). The space used does not depend on the size of the input array, as only a fixed number of variables are used.

Key Points

• The algorithm efficiently finds the potential majority elements using a clever counting mechanism.
• It ensures that if there are elements meeting the criteria, they will be among the candidates after the first pass.
• The second pass is crucial to confirm whether the candidates actually meet the criteria.
• This solution elegantly combines the principles of majority voting with an efficient two-pass system, ensuring the desired time and space complexity constraints are met.