algoadvance

Leetcode 169. Majority Element

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.

Clarifying Questions

1. Input constraints: Are we guaranteed that the input array will always have a majority element?
   • Yes, it is guaranteed as per the problem statement.
2. Data type for elements: What type of elements does the array contain?
   • The array contains integer elements.
3. Array size: Are there any constraints on the size of the input array?
   • There is no explicit constraint on the size of the array, but the focus should be on achieving the solution with the lowest possible time complexity.
4. Output format: What should be the return type of the function?
   • The return type should be an integer representing the majority element.

Given these clarifications, we can proceed to solve the problem.

Strategy

One efficient method to solve this problem is by using the Boyer-Moore Voting Algorithm. This algorithm works in linear time (O(n)) and constant space (O(1)). The idea behind the algorithm is to maintain a candidate for the majority element and a count that represents how many times we have found the candidate element.

1. Initialize: Start with the first element as the candidate and set count to 1.
2. Iterate through the array:
   • If the current element is the same as candidate, increment count.
   • If the current element is different from candidate, decrement count.
   • If count becomes 0, change the candidate to the current element and reset count to 1.
3. Return the candidate after completing the iteration since the majority element is guaranteed to exist.

Code

#include <vector>

class Solution {
public:
    int majorityElement(std::vector<int>& nums) {
        int candidate = nums[0];
        int count = 1;

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }

            if (count == 0) {
                candidate = nums[i];
                count = 1;
            }
        }

        return candidate;
    }
};

Time Complexity

• Time Complexity: The algorithm iterates through the array once, which means the time complexity is (O(n)), where (n) is the number of elements in the array.
• Space Complexity: The algorithm uses a constant amount of space, i.e., (O(1)), for storing variables candidate and count.

This solution is optimal for solving the majority element problem under the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?