10
\$\begingroup\$

The task:

Given a list of elements, find the majority element, which appears more than half the time (> floor(len(lst) / 2.0)).

You can assume that such element exists.

For example, given [1, 2, 1, 1, 3, 4, 0], return 1.

My solution:

const lst = [1, 2, 1, 1, 3, 4, 0];
const findMajorityElem = lst => lst.reduce((acc, x) => {
  acc[x] = acc[x] ? acc[x] + 1 : 1;
// If I can assume that such an element exists, then it's sufficient to check which element occurs the most.
  if (!acc.major || acc.major[1] < acc[x]) { acc.major = [x, acc[x]]; }
  return acc;
}, {major: null}).major[0];

console.log(findMajorityElem(lst));
\$\endgroup\$
  • 5
    \$\begingroup\$ In the example [1, 2, 1, 1, 3, 4, 0], 1 appears 3 times, floor(len(lst) / 2.0)) is 3, and since 3 is not more than 3, therefore 1 is not the majority element, and the example list doesn't have a majority element. \$\endgroup\$ – janos Apr 1 at 16:47
  • \$\begingroup\$ @janos the example is inaccurate. However it explicitly says I can assume that there exists a majority element \$\endgroup\$ – thadeuszlay Apr 1 at 16:54
14
\$\begingroup\$

If it is known that a majority element exists, then the efficient algorithm to use is the Boyer-Moore majority vote algorithm, which requires only O(1) space.

\$\endgroup\$
  • 2
    \$\begingroup\$ That's a little deceptive... it's $\Omega(\log n)$ space in terms of bit complexity. \$\endgroup\$ – Charles Apr 1 at 20:44
  • 2
    \$\begingroup\$ @Charles Why would you want to break it down in terms of bits? \$\endgroup\$ – 200_success Apr 2 at 1:18
  • 1
    \$\begingroup\$ I think the question should be, why hide the size of the space requirements? Calling O(1) is, IMO, deceptive: it makes it sound like a fixed amount of space suffices for arbitrarily large arrays, but the larger the array the larger the numbers you need to store, and the larger the numbers the larger the space they take up. Sure, only logarithmically so, but then let's call it logarithmic space, not constant space. It's only constant space in the sense that you use a constant number of words when the words themselves grow logarithmically, but then you're being tricky and hiding the real size. \$\endgroup\$ – Charles Apr 2 at 1:59
  • 1
    \$\begingroup\$ @Charles I don't understand why there's necessarily a correlation between the size of the array and the size of the values within it. To me those are completely orthogonal concerns. It also doesn't seem particularly relevant here anyway, since Javascript's numbers are fixed-size. \$\endgroup\$ – Kyle Apr 2 at 2:31
  • 1
    \$\begingroup\$ @Charles I don’t think that’s entirely fair. Unlike algorithms and structures that meaningfully depend on bit width (radix sort, van Emde Boas trees, ...), this one only has a dependence on it in that it needs to store an array index and an array element (an offline version can also get away with storing two indices instead). That is, it needs as much space as an array access, and you generally want to count this as O(1). Yes, that means you’re counting words, not bits, but that’s the standard cost model, and it makes perfect sense outside of specialized applications. \$\endgroup\$ – Alex Shpilkin Apr 2 at 14:17
3
\$\begingroup\$

@200_success's suggestion seems like the right play here.

That said, I thought it was worth pointing out a couple small improvements to your approach:

  • major need only be the element itself (since you can look up its value in the accumulator)
  • Since you tagged this functional-programming, you can use expressions everywhere, and avoid the if statement.

Revised code:

const findMajorityElem = lst => lst.reduce((acc, x) => {
  acc[x] = acc[x] ? acc[x] + 1 : 1;
  const maxCnt = acc[acc.major] || 0
  acc.major = acc[x] <= maxCnt ? acc.major : x
  return acc
}, {major: null}).major

And just for fun, again based on your tag, here's a single-expression solution in Ramda. Again, I don't recommend actually using this given that Boyer-Moore exists:

pipe(
  groupBy(identity), 
  map(length), 
  toPairs, 
  converge( reduce(maxBy(last)), [head, identity] ),
  head, 
  parseInt
)(lst)

You can try it here

\$\endgroup\$
1
\$\begingroup\$

If the number exists, it should be done like this and shorter.

let result =
   [2,3,4,5,1,1,1,2,2,22,2,2,2,2,2,2,2,2,1,1,33,3,2,1,1,1,1,2,2,2,2,2].reduce( (a ,b) => {
  console.log(a)
return a.length == null  ? ( a != b ?  [] : a.concat(b)):
       a.length == 0  ? [b] :
       a[a.length-1] == b ?  a.concat(b)  :
       a.slice(0,a.length-2) ;
    })[0]

 console.log(result) //2
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! and shorter is a bit short on what deserves improvement in the code in the question and why the way proposed is better. \$\endgroup\$ – greybeard Apr 2 at 5:42
  • \$\begingroup\$ Shorter means in Javascript, you may write in a neater way. It’s an implementation of voter algorithm. Just compare the last element in result with a new element, if they are different, just cancel them. Then the final survived element will be the result. Time is o(n) and if in-place space is o(1). \$\endgroup\$ – E.Coms Apr 2 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.