LeetCode 169: Majority Element Solution

Problem Explanation

Explanation:

To find the majority element in an array, we can use the Boyer-Moore Voting Algorithm. The idea is to cancel out each occurrence of a majority element with all other elements. If there is a majority element in the array, it will be left as the last candidate after all the elements are processed.

Algorithm:

Initialize a variable candidate to store the current candidate for the majority element and a variable count to keep track of its frequency.
Iterate through the array:
- If the count is 0, set the current element as the candidate and increment the count.
- If the current element is the same as the candidate, increment the count; otherwise, decrement the count.
The majority element will be the last remaining candidate.

Time Complexity: O(n) Space Complexity: O(1)

Solution Code

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        
        return candidate;
    }
}

Frequently Asked Questions

How to solve LeetCode 169 (Majority Element)?

This page provides optimized solutions for LeetCode problem 169 (Majority Element) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 169 (Majority Element)?

The time complexity for LeetCode 169 (Majority Element) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 169 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 169 in Java, C++, or Python.