Majority Element
EasyPrompt
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: 3Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
Follow-up: Could you solve the problem in linear time and in
O(1) space?Approaches
4 approaches with complexity analysis and trade-offs.
This approach involves iterating through the array for each element and counting its occurrences. If an element's count exceeds n/2, it is returned as the majority element.
Algorithm
- Get the size of the array,
n. - Use an outer loop to iterate from
i = 0ton-1. - Inside the outer loop, select
nums[i]as the candidate and initializecount = 0. - Use an inner loop to iterate from
j = 0ton-1. - Inside the inner loop, if
nums[j]is equal to the candidatenums[i], incrementcount. - After the inner loop completes, check if
count > n / 2. - If the condition is true, return the candidate
nums[i].
Walkthrough
The brute force method uses two nested loops. The outer loop picks an element from the array as a potential candidate for the majority element. The inner loop then iterates through the entire array to count the occurrences of this candidate element.
If the count for any candidate becomes greater than n/2, that candidate is the majority element, and we can return it immediately. Since the problem guarantees that a majority element always exists, this process will always find and return the correct element.
class Solution { public int majorityElement(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < n; j++) { if (nums[j] == nums[i]) { count++; } } if (count > n / 2) { return nums[i]; } } // This part is unreachable given the problem constraints // but is needed for the compiler. return -1; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Highly inefficient, with a quadratic time complexity, making it unsuitable for large datasets.
Solutions
Solution
public class Solution { public int MajorityElement ( int [] nums ) { int cnt = 0 , m = 0 ; foreach ( int x in nums ) { if ( cnt == 0 ) { m = x ; cnt = 1 ; } else { cnt += m == x ? 1 : - 1 ; } } return m ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.