Majority Element-I

Intuition

Naive way is to count the occurrences of each element. The element which will have count greater than half the array size will be the majority element.

Approach

Iterate in the array to select the elements of the array one by one. Now, for each element, run another loop and count its occurrence in the given array.

If any element occurs more than the floor of (N/2), simply return it.

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

class Solution {
public:
    // Function to find the majority element in an array
    int majorityElement(vector<int>& nums) {
        
        // Size of the given array
        int n = nums.size();
        
        // Iterate through each element of the array
        for (int i = 0; i < n; i++) {
            
            // Counter to count occurrences of nums[i]
            int cnt = 0; 
            
            // Count the frequency of nums[i] in the array
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    cnt++;
                }
            }
            
            // Check if frequency of nums[i] is greater than n/2
            if (cnt > (n / 2)) {
                // Return the majority element
                return nums[i]; 
            }
        }
        
        // Return -1 if no majority element is found
        return -1; 
    }
};

int main() {
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    
    // Create an instance of Solution class
    Solution sol;
 
    int ans = sol.majorityElement(arr);
    
    // Print the majority element found
    cout << "The majority element is: " << ans << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the majority element in an array
    public int majorityElement(int[] nums) {
        
        // Size of the given array
        int n = nums.length;
        
        // Iterate through each element of the array
        for (int i = 0; i < n; i++) {
            
            // Counter to count occurrences of nums[i]
            int cnt = 0; 
            
            // Count the frequency of nums[i] in the array
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    cnt++;
                }
            }
            
            // Check if frequency of nums[i] is greater than n/2
            if (cnt > (n / 2)) {
                // Return the majority element
                return nums[i]; 
            }
        }
        
        // Return -1 if no majority element is found
        return -1; 
    }

    public static void main(String[] args) {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};
        
        // Create an instance of Solution class
        Solution sol = new Solution();
 
        int ans = sol.majorityElement(arr);
        
        // Print the majority element found
        System.out.println("The majority element is: " + ans);
    }
}
from typing import List

class Solution:
    # Function to find the majority element in an array
    def majorityElement(self, nums: List[int]) -> int:
        
        # Size of the given array
        n = len(nums)
        
        # Iterate through each element of the array
        for i in range(n):
            
            # Counter to count occurrences of nums[i]
            cnt = 0 
            
            # Count the frequency of nums[i] in the array
            for j in range(n):
                if nums[j] == nums[i]:
                    cnt += 1
            
            # Check if frequency of nums[i] is greater than n/2
            if cnt > (n // 2):
                # Return the majority element
                return nums[i]
        
        # Return -1 if no majority element is found
        return -1

if __name__ == "__main__":
    arr = [2, 2, 1, 1, 1, 2, 2]
    
    # Create an instance of Solution class
    sol = Solution()
 
    ans = sol.majorityElement(arr)
    
    # Print the majority element found
    print("The majority element is:", ans)
class Solution {
    // Function to find the majority element in an array
    majorityElement(nums) {
        
        // Size of the given array
        let n = nums.length;
        
        // Iterate through each element of the array
        for (let i = 0; i < n; i++) {
            
            // Counter to count occurrences of nums[i]
            let cnt = 0; 
            
            // Count the frequency of nums[i] in the array
            for (let j = 0; j < n; j++) {
                if (nums[j] === nums[i]) {
                    cnt++;
                }
            }
            
            // Check if frequency of nums[i] is greater than n/2
            if (cnt > Math.floor(n / 2)) {
                // Return the majority element
                return nums[i]; 
            }
        }
        
        // Return -1 if no majority element is found
        return -1; 
    }
}

function main() {
    let arr = [2, 2, 1, 1, 1, 2, 2];
    
    // Create an instance of Solution class
    let sol = new Solution();
 
    let ans = sol.majorityElement(arr);
    
    // Print the majority element found
    console.log("The majority element is:", ans);
}

// Execute the main function
main();

Complexity Analysis

Time Complexity: O(N²), for nested for loops used, where N is the size of the array Space Complexity: O(1) as no extra space is used.

Intuition

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

Approach

Use a hashmap and store as (key, value) pairs. Here the key will be the element of the array and the value will be the number of times it occurs.

Traverse the array and update the value of the key. Simultaneously check if the value is greater than the floor of N/2. If yes, return the key, otherwise iterate forward.

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

class Solution {
public:
    // Function to find the majority element in an array
    int majorityElement(vector<int>& nums) {
        
        // Size of the given array
        int n = nums.size();
        
        // Hash map to store element counts
        unordered_map<int, int> mp;
        
        // Count occurrences of each element
        for (int num : nums) {
            mp[num]++;
        }
        
        /* Iterate through the map to
        find the majority element*/
        for (auto& pair : mp) {
            if (pair.second > n / 2) {
                return pair.first;
            }
        }
        
        // Return -1 if no majority element is found
        return -1;
    }
};

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

    int ans = sol.majorityElement(arr);
    
    // Print the majority element found
    cout << "The majority element is: " << ans << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the majority element in an array
    public int majorityElement(int[] nums) {
        
        // Size of the given array
        int n = nums.length;
        
        // Hash map to store element counts
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // Count occurrences of each element
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        /* Iterate through the map to
        find the majority element*/
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > n / 2) {
                return entry.getKey();
            }
        }
        
        // Return -1 if no majority element is found
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};
        
        // Create an instance of Solution class
        Solution sol = new Solution();
 
        int ans = sol.majorityElement(arr);
        
        // Print the majority element found
        System.out.println("The majority element is: " + ans);
    }
}
from typing import List

class Solution:
    # Function to find the majority element in an array
    def majorityElement(self, nums: List[int]) -> int:
        
        # Size of the given array
        n = len(nums)
        
        # Hash map to store element counts
        mp = {}
        
        # Count occurrences of each element
        for num in nums:
            if num in mp:
                mp[num] += 1
            else:
                mp[num] = 1
        
        """ Iterate through the map to
        find the majority element"""
        for num, count in mp.items():
            if count > n // 2:
                return num
        
        # Return -1 if no majority element is found
        return -1

# Main function to test the Solution class
if __name__ == "__main__":
    arr = [2, 2, 1, 1, 1, 2, 2]
    
    # Create an instance of Solution class
    sol = Solution()
 
    ans = sol.majorityElement(arr)
    
    # Print the majority element found
    print("The majority element is:", ans)
class Solution {
    // Function to find the majority element in an array
    majorityElement(nums) {
        
        // Size of the given array
        let n = nums.length;
        
        // Hash map to store element counts
        let map = new Map();
        
        // Count occurrences of each element
        for (let num of nums) {
            map.set(num, (map.get(num) || 0) + 1);
        }
        
        /* Iterate through the map to
        find the majority element */
        for (let [key, value] of map.entries()) {
            if (value > n / 2) {
                return key;
            }
        }
        
        // Return -1 if no majority element is found
        return -1;
    }
}

// Main function to test the Solution class
function main() {
    let arr = [2, 2, 1, 1, 1, 2, 2];
    
    // Create an instance of Solution class
    let sol = new Solution();
 
    let ans = sol.majorityElement(arr);
    
    // Print the majority element found
    console.log("The majority element is:", ans);
}

// Execute the main function
main();

Complexity Analysis

Time Complexity: O(NxlogN) + O(N), where N is the size of the array. This TC is for using a map data structure. Insertion in the map takes log N time. And we are doing it for N elements. So, it results in the first term O(NxlogN). The second O(N) is for checking which element occurs more than floor(N/2) times. On using unordered_map, the first term will be O(N) for the best and average case and for the worst case, it will be O(N²). Space Complexity: O(N) for using a map data structure.

Intuition

Imagine you are at a large party, and you want to determine which dish is the most popular. Each guest has brought a dish, and some dishes are brought by more guests than others. The party is large enough that one dish is guaranteed to be the majority dish, meaning it was brought by more than half of the guests.

Initial observation is as we move around the party, you decide to start keeping track of the dishes in a specific way. Begin with no specific dish in mind and no count. On seeing each dish, do the following:

If you don’t have a dish you’re tracking yet, start tracking the current dish and set its count to 1.

If the current dish matches the one you’re tracking, increase its count by 1.

If the current dish doesn’t match the one you’re tracking, decrease the count by 1. If the count drops to zero, stop tracking that dish and start tracking the next dish.

The idea is that at any point where the count of tracked dishes drops to zero, it means up to that point, the popularity of different dishes has balanced out. This reset allows you to focus on potentially more popular dishes as you continue through the party. At the end check which dish you ended up tracking last. This dish is your candidate for the most popular dish. To confirm if this dish is indeed the majority dish, recount its appearances to see if it indeed makes up more than half of all dishes at the party. If it does, then you have found your majority dish. If it doesn’t, there was an error in the process, but for this scenario, we assume the party is large enough to guarantee one majority dish.

Approach

Initialize 2 variables: countfor tracking the count of elements and element for keeping a track of the element we are counting.

Traverse through the given array. If count is 0 then store the current value of the array as element .

If the current array value andelement are the same increase the count by 1. If they are different decrease the count by 1. The integer present in element should be the result expected.

Dry Run

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

class Solution {
public:
    // Function to find the majority element in an array
    int majorityElement(vector<int>& nums) {
        
        // Size of the given array
        int n = nums.size();
        
        // Count
        int cnt = 0;
        
        // Element
        int el; 
        
        // Applying the algorithm
        for (int i = 0; i < n; i++) {
            if (cnt == 0) {
                cnt = 1;
                el = nums[i];
            } else if (el == nums[i]) {
                cnt++;
            } else {
                cnt--;
            }
        }
        
        /* Checking if the stored element
         is the majority element*/
        int cnt1 = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == el) {
                cnt1++;
            }
        }
        
        //return element if it is a majority element
        if (cnt1 > (n / 2)) {
            return el;
        }
        
        //return -1 if no such element found
        return -1;
    }
};

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

    int ans = sol.majorityElement(arr);
    
    // Print the majority element found
    cout << "The majority element is: " << ans << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the majority element in an array
    public int majorityElement(int[] nums) {
        // Size of the given array
        int n = nums.length;
        
        // Count
        int cnt = 0;
        
        // Element
        int el = 0;
        
        // Applying the algorithm
        for (int i = 0; i < n; i++) {
            if (cnt == 0) {
                cnt = 1;
                el = nums[i];
            } else if (el == nums[i]) {
                cnt++;
            } else {
                cnt--;
            }
        }
        
        /* Checking if the stored element
         is the majority element*/
        int cnt1 = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == el) {
                cnt1++;
            }
        }
        
        // Return element if it is a majority element
        if (cnt1 > (n / 2)) {
            return el;
        }
        
        // Return -1 if no such element found
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        int ans = sol.majorityElement(arr);
        
        // Print the majority element found
        System.out.println("The majority element is: " + ans);
    }
}
from typing import List

class Solution:
    # Function to find the majority element in an array
    def majorityElement(self, nums: List[int]) -> int:
        
        # Size of the given array
        n = len(nums)
        
        # Count
        cnt = 0
        
        # Element
        el = 0
        
        # Applying the algorithm
        for num in nums:
            if cnt == 0:
                cnt = 1
                el = num
            elif el == num:
                cnt += 1
            else:
                cnt -= 1
        
        """ Checking if the stored element
        is the majority element"""
        cnt1 = nums.count(el)
        
        # Return element if it is a majority element
        if cnt1 > (n // 2):
            return el
        
        # Return -1 if no such element found
        return -1

# Test the solution with the given example
arr = [2, 2, 1, 1, 1, 2, 2]

# Create an instance of Solution class
sol = Solution()

ans = sol.majorityElement(arr)

# Print the majority element found
print(f"The majority element is: {ans}")
class Solution {
    // Function to find the majority element in an array
    majorityElement(nums) {
        // Size of the given array
        let n = nums.length;
        
        // Count
        let cnt = 0;
        
        // Element
        let el = 0;
        
        // Applying the algorithm
        for (let num of nums) {
            if (cnt === 0) {
                cnt = 1;
                el = num;
            } else if (el === num) {
                cnt++;
            } else {
                cnt--;
            }
        }
        
        /* Checking if the stored element
         is the majority element*/
        let cnt1 = nums.filter(num => num === el).length;
        
        // Return element if it is a majority element
        if (cnt1 > Math.floor(n / 2)) {
            return el;
        }
        
        // Return -1 if no such element found
        return -1;
    }
}

let arr = [2, 2, 1, 1, 1, 2, 2];

// Create an instance of Solution class
let sol = new Solution();

let ans = sol.majorityElement(arr);

// Print the majority element found
console.log(`The majority element is: ${ans}`);

Complexity Analysis

Time Complexity: O(N) + O(N), where N is size of the given array. The first O(N) is to calculate the count and find the expected majority element. The second one is to check if the expected element is the majority one or not. Space Complexity: O(1) no extra space used.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts