Majority Element - LeetCode Daily Challenge

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1

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

Example 2

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

Try here before watching the video.

Video Solution

Java Code

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

C++ Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int majorityElement = -1;
        for (int num : nums) {
            if (count == 0) {
                majorityElement = num;
            }
            if (num == majorityElement) {
                count++;
            } else {
                count--;
            }
        }
        return majorityElement;
    }
};

Python Code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        majority_element = None
        for num in nums:
            if count == 0:
                majority_element = num
            if num == majority_element:
                count += 1
            else:
                count -= 1
        return majority_element

Javascript Code

var majorityElement = function(nums) {
    let count = 0;
    let majorityElement = null;
    for (const num of nums) {
        if (count === 0) {
            majorityElement = num;
        }
        if (num === majorityElement) {
            count++;
        } else {
            count--;
        }
    }
    return majorityElement;
};

Go Code

func majorityElement(nums []int) int {
    count := 0
    majorityElement := -1
    for _, num := range nums {
        if count == 0 {
            majorityElement = num
        }
        if num == majorityElement {
            count++
        } else {
            count--
        }
    }
    return majorityElement
}

Complexity Analysis

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