major.js

const assert = require('assert');
// Given an array of integers, more than half of which are the same integer. Please print out that integer.
// Moore’s Voting Algorithm
// time: O(n)
// space: O(1)
// https://leetcode.com/problems/majority-element/
// more than n/2 times
// hash counter solution? space O(n)
const major1 = function(a) {
  let cnt = 0,
    x = null;

  for (let i = 0, l = a.length; i < l; i++) {
    if (x === a[i]) {
      cnt++;
    } else if (cnt === 0) {
      cnt++;
      x = a[i];
    } else {
      cnt--;
    }
  }

  // no need to check if we are told more than half of the elements are the same integer
  let c = 0;
  for (let i = 0, l = a.length; i < l; i++) {
    if (a[i] === x) {
      c++;
    }
  }

  if (c > a.length / 2) {
    return x;
  }

  return -1;
};

// more than n/3 times
// https://leetcode.com/problems/majority-element-ii/
const major2 = function(a) {
  let cnt1 = 0,
    cnt2 = 0,
    x = null,
    y = null;

  for (let i = 0, l = a.length; i < l; i++) {
    if (x === a[i]) {
      cnt1++;
    } else if (y === a[i]) {
      cnt2++;
    } else if (cnt1 === 0) {
      cnt1++;
      x = a[i];
    } else if (cnt2 === 0) {
      cnt2++;
      y = a[i];
    } else {
      cnt1--;
      cnt2--;
    }
  }

  const r = [];

  let c1 = 0,
    c2 = 0;
  for (let i = 0, l = a.length; i < l; i++) {
    if (a[i] === x) {
      c1++;
    }
    if (a[i] === y) {
      c2++;
    }
  }

  if (c1 > a.length / 3) r.push(x);
  if (c2 > a.length / 3) r.push(y);

  return r;
};

// general form
// Given an array of of size n and a number k, find all elements that appear more than n/k times
// (k-1) candidates
const major3 = function(a, k) {};

// follow up: what if >= n/k (can be equal)?
// hash counter solution

assert.equal(major1([3, 3, 4, 2, 4, 4, 2, 4, 4]), 4);
assert.equal(major1([3, 3, 4, 2, 4, 4, 2, 4]), -1);
assert.deepEqual(major2([10, 10, 20, 30, 10, 10]), [10]);
assert.deepEqual(major2([20, 30, 10, 10, 5, 4, 20, 1, 2]), []);
assert.deepEqual(major2([3, 2, 3]), [3]);
assert.deepEqual(major2([1, 1, 1, 3, 3, 2, 2, 2]), [1, 2]);