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
Hiring now
Visa has 638 open roles right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Director, Greater China Tax
CN - Beijing, China
Sr. Manager, Government Sales Executive
IT - Rome, Italy
Director, Solution Architect, Global Growth Initiatives
GB - London, United Kingdom
Next question