Learning Javascript — Elections Challenge
I came across another challenge question on codefights.com. However, the challenge here is to get the hidden tests to execute under a certain timeframe. Here is the challenge:
Elections are in progress!
Given an array of the numbers of votes given to each of the candidates so far, and an integer k equal to the number of voters who haven't cast their vote yet, find the number of candidates who still have a chance to win the election.
The winner of the election must secure strictly more votes than any other candidate. If two or more candidates receive the same (maximum) number of votes, assume there is no winner at all.
Example
For votes = [2, 3, 5, 2] and k = 3, the output should beelectionsWinners(votes, k) = 2.
- The first candidate got
2votes. Even if all of the remaining3candidates vote for him, he will still have only5votes, i.e. the same number as the third candidate, so there will be no winner. - The second candidate can win if all the remaining candidates vote for him (
3 + 3 = 6 > 5). - The third candidate can win even if none of the remaining candidates vote for him. For example, if each of the remaining voters cast their votes for each of his opponents, he will still be the winner (the
votesarray will thus be[3, 4, 5, 3]). - The last candidate can’t win no matter what (for the same reason as the first candidate).
Thus, only 2 candidates can win (the second and the third), which is the answer.
Input/Output:
[time limit] 4000ms (js)
[input] array.integer votes
- A non-empty array of non-negative integers. Its
ithelement denotes the number of votes cast for theithcandidate. - Guaranteed constraints:
4 ≤ votes.length ≤ 10^5,0 ≤ votes[i] ≤ 10^4.
[input] integer k
- The number of voters who haven’t cast their vote yet.
- Guaranteed constraints:
0 ≤ k ≤ 105
[output] integer
While I got the logic correct at first, one of the hidden tests (the last one!) must have had a sufficiently large dataset and therefore the solution could have been more optimized. Here is the solution that passed the challenge:
function electionsWinners(votes, k) {
//Returns Indices of all the elements with the Maximum Vote Counts
function findMaxVotesIndex(votes) {
var maxIndexArray = [];
var maxIndex;
for (var i = 0; i < votes.length; i++) {
if (i === 0) {
maxIndex = 0;
maxIndexArray.push(i);
}
else if (votes[i] > votes[maxIndex]) {
maxIndexArray = [];
maxIndexArray.push(i);
maxIndex = i;
}
else if (votes[i] === votes[maxIndex]) {
maxIndexArray.push(i);
}
}
return maxIndexArray;
}
//Is votes[index] unique in the votes array
function boolUniqueVote(index, votes) {
var voteCount = votes[index] + k;
for (var i = 0; i < votes.length; i++) {
if (i != index && votes[i] === voteCount) {
return false;
}
}
return true;
}
var possibleWinners = 0;
var maxIndexArray = findMaxVotesIndex(votes);
var maxVotes = votes[maxIndexArray[0]]; //This is the maximum vote count value without k
if (k === 0) {
if (maxIndexArray.length === 1) {
return 1; //Only 1 Maximum Vote Count
}
else {
return 0; //There is a tie
}
}
else {
if (maxIndexArray.length === votes.length) {
return votes.length; //The case were all elements in the votes array are the same which means each element in the votes array is a potential winner
}
for (var i = 0; i < votes.length; i++) {
if (votes[i] + k > maxVotes && boolUniqueVote(i, votes)) { //The necessary condition to account for possible winners: The element's vote count + k should be greater than the max vote count and that element value is unique in the array
possibleWinners++;
}
}
return possibleWinners;
}
}Again, Im sure there are more elegant ways of doing it. :)