Majority Element-I
Amazon
MakeMyTrip
VisaThe problem
Given an integer array nums of size n, return the majority element of the array.
The majority element of an array is an element that appears more than n/2 times in the array. The array is guaranteed to have a majority element.
Input: nums = [7, 0, 0, 1, 7, 7, 2, 7, 7] Output: 7 Explanation: The number 7 appears 5 times in the 9 sized array
Input: nums = [1, 1, 1, 2, 1, 2] Output: 1 Explanation: The number 1 appears 4 times in the 6 sized array
Input: nums = [-1, -1, -1, -1]
- n == nums.length.
- 1 <= n <= 105
- -104 <= nums[i] <= 104
- One value appears more than n/2 times.
cpp
class Solution {
public:
int majorityElement(vector<int>& nums) {
}
};java
class Solution {
public int majorityElement(int[] nums) {
}
}python
class Solution:
def majorityElement(self, nums):javascript
class Solution {
majorityElement(nums) {
}
}csharp
class Solution {
public int MajorityElement(List<int> nums) {
}
}go
func majorityElement(nums []int) int {
}Stuck? Show a way to structure it+
- 01Maintain a candidate and a vote balance.
- 02Replace the candidate when the balance is zero, then add or cancel a vote.
- 03Return the final candidate under the guaranteed-majority condition.
- 04Add a second verification pass if a majority is not guaranteed.
Reference answer
Then expect these follow-ups
How do you handle the problem when a majority is not guaranteed?
Tests: verification
How does the method generalize to elements occurring more than n/3 times?
Tests: algorithm extension
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question