Skip to content

Instantly share code, notes, and snippets.

@Muzietto
Last active January 10, 2017 08:51
Show Gist options
  • Save Muzietto/388d5916930a85182587b0e336dfe174 to your computer and use it in GitHub Desktop.
Save Muzietto/388d5916930a85182587b0e336dfe174 to your computer and use it in GitHub Desktop.
Finding a vector leader faking the usage of a stack
function stackBasedLeader(A) {
var n = A.length;
var occurrences = {};
var stackSize = 0;
var stackElem = -1;
for (let a of A) {
if (!occurrences[a]) occurrences[a] = 0;
occurrences[a]++;
if (stackSize > 0 && a !== stackElem) {
stackSize--;
continue;
}
if (stackSize === 0) {
stackSize++;
stackElem = a;
continue;
}
if (a === stackElem) {
stackSize++;
}
}
return (occurrences[stackElem] > n/2) ? stackElem : -1;
}
@Muzietto
Copy link
Author

Muzietto commented Jan 10, 2017

Finding a vector leader in O(n) time is achieved using a stack to pop couples of not-equal elements and returning either what's left in the stack or -1. As mentioned here, we don't need a real stack, as the stack will always contain elements of the same value.
Therefore we implement the stack using a stackSize and a stackElem.
Accumulator occurrences is needed for the final check.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment