Grind 75 Question 20: Majority Element
Can I get it on my own in under 20 minutes? Of course not…
The Problem
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.
The First Attempts
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let majorityEl = 0;
let totalCount = 1;
nums.sort()
for(i = 0; i<nums.length; i++){
let tempCount = 1;
if(nums[i] == nums[i+1]){
tempCount += i
if(Math.max(tempCount, totalCount) == tempCount){
majorityEl = nums[i];
} else tempCount = 1;
}
}
return majorityEl;
};Holy cow, it’s accepted the first time I run it. Not a missing curly brace to be found. On running all test cases…ACCEPTED OMG OMG. WILL THIS BE THE ONE??
Damn one-element array cramping my style. And the second test case returns incorrectly for some reason also. So, to dig in and fix it. But first, I need to give my poor children some lunch and put them down for naps.
The Solution
Eep! It didn’t take much fixing — the place where tempCount resets to one was just in the wrong spot, and I moved its initialization outside of the for loop because it seemed to be resetting for each iteration. Here it is, in all its unhinged glory:
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let majorityEl = 0;
let totalCount = 1;
let tempCount = 1;
nums.sort()
if (nums.length == 1) majorityEl = nums[0]
for(i = 0; i<nums.length; i++){
if(nums[i] == nums[i+1]){
tempCount += 1
if(Math.max(tempCount, totalCount) == tempCount){
majorityEl = nums[i];
totalCount = tempCount;
}
} else tempCount = 1;
}
return majorityEl;
};Need I explain it? Okay, so there’s a majorityEl variable that stores the current majority element (which will end up being returned). There’s totalCount, which the temporary count is checked against to see if it’s higher. Then I sort the array so all the numbers are next to each other.
Then the for loop begins (well, after I have that little bit about majorityEl being nums[0] if the array length is one):
For each element in nums.length, if the element next to it is the same number, add one to the tempCount. If tempCount is higher than totalCount, nums[i] is stored as the new majority element to be returned, and totalCount is updated to what tempCount is.
If the element next to i isn’t the same number, reset tempCount back to 1 (because there is, at least, a single occurrence of that number). After the array has been looped through one time (O(n), my friends), the majorityEl is returned.
What I Learned
- I maybe can do this! This question was, at least, a confidence boost. I got it, start to finish, on my own. Cool beans.
mins
read
