Majority Element Leetcode Problem 169 [Python Solution]

In this blog post, we will tackle the Majority Element problem from LeetCode.

This problem falls under the "Arrays & Hashing" category and is considered an easy one.

We'll provide you with a Python solution that not only solves the problem but does so efficiently.

Problem Overview

The problem statement is as follows:

Given an array nums of size n, your task is to return the majority element.

The majority element is defined as the element that appears more than ⌊n / 2⌋ times.

You can safely assume that the majority element always exists in the array.

To illustrate this problem with an example:

Example 1:

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

Example 2:

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

The problem is straightforward to understand.

You are given an array, and you need to find the element that occurs more than half of the time in the array.

Problem Constraints

Before we delve into the solution, let's take a closer look at the constraints of this problem:

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

These constraints give us insights into the scale of the problem.

We're dealing with arrays of potentially large sizes, and the elements within the array can be both positive and negative integers.

Now, let's explore two approaches to solving this problem: the Bruteforce Approach and the Efficient Approach.

Example 1:

Let's start with a basic brute-force solution and then optimize it.

We will also provide a Python code solution for both approaches.

1. Bruteforce Approach

The brute-force approach to this problem involves counting the occurrences of each value in the array using a hash map.

While this approach is simple to implement, it uses extra memory for the hash map and has a time complexity of O(n).

Below is the Python code for this approach:

def majorityElement(nums):
    count = {}  # Create a dictionary to store counts
    max_count = 0  # Initialize max_count
    result = None  # Initialize result

    for num in nums:
        # Increment the count for the current number
        if num in count:
            count[num] += 1
        else:
            count[num] = 1

        # Update max_count and result if necessary
        if count[num] > max_count:
            max_count = count[num]
            result = num

    return result

In this code, we iterate through the array, keeping track of the count of each element using a dictionary.

If we encounter a count greater than the current max_count, we update the result.

This solution is intuitive but uses extra memory and has a time complexity of O(n).

2. Efficient Approach with Boyer-Moore Algorithm

Now, let's explore a more efficient approach that doesn't require extra memory.

We'll use the Boyer-Moore algorithm, which allows us to find the majority element in linear time (O(n)) and constant space (O(1)).

The algorithm is based on the intuition that the majority element will dominate the rest of the elements.

Efficient Python Code Solution

Here's the Python code for the efficient Boyer-Moore algorithm:

def majorityElement(nums):
    count = 0  # Initialize count
    result = None  # Initialize result

    for num in nums:
        if count == 0:
            result = num
        count += 1 if num == result else -1

    return result

In this efficient solution, we initialize the count and result variables.

We iterate through the array, and for each element, we update the count.

If the count reaches zero, we update the result to the current element.

This algorithm guarantees that the result will be the majority element in the end, given that a majority element exists.

Time and Space Complexity

Let's analyze the time and space complexity of the efficient Boyer-Moore algorithm:

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

The algorithm operates in linear time and uses constant space, making it highly efficient for solving this problem.

Reasoning Behind Our Approach

The Boyer-Moore algorithm is based on the observation that the majority element will always have a count that is greater than the sum of counts of all other elements.

As we traverse the array, we maintain two variables: count and result.

We increment count when we encounter an element that matches the current result, and we decrement count when we encounter an element different from the result.

Whenever count reaches zero, we update the result to the current element.

This algorithm guarantees that the final result is the majority element, if it exists, due to the property of the majority element appearing more than ⌊n / 2⌋ times.

Related Interview Questions By Company:

• Invert Binary Tree LeetCode
• Min Cost Climbing Stairs LeetCode
• Reverse Linked List LeetCode

Related Interview Questions By Difficulty:

• Find All Numbers Disappeared In An Array LeetCode
• Best Time To Buy And Sell Stock II LeetCode
• Maximum Number Of Balloons LeetCode

Related Interview Questions By Category:

• Combinations LeetCode
• Palindrome Number LeetCode
• Seat Reservation Manager LeetCode

Conclusion

In this blog post, we've explored the Majority Element problem on LeetCode.

We've provided two solutions: a brute-force approach using a hash map and an efficient approach based on the Boyer-Moore algorithm.

The efficient approach has a time complexity of O(n) and a space complexity of O(1), making it the optimal solution for this problem.

We encourage you to try both solutions and see how they perform on different test cases.

Feel free to comment, ask questions, make suggestions, and share this content with others.

Happy coding!

Question Link: Majority Element – LeetCode

If you found this blog post helpful, please like and engage to support the our platform.

You can also consider checking out our Patreon for further support.

We look forward to sharing more coding solutions with you in the future.

Thanks for watching!