Cassidoo’s Interview question of the week | 446

Learning Resources
1

Hello :waving_hand:

This week question is about finding the majority element in an array. Here it is.

Find the majority element in an array (one that appears more than n/2 times) in O(n) time and O(1) space without hashmaps. Hint: the Boyer-Moore Voting algorithm might help if you can’t figure this one out!

Example

> majorityElement([2, 2, 1, 1, 2, 2, 1, 2, 2])
2

> majorityElement([3, 3, 4, 2, 3, 3, 1])
3

Happy coding!

2 Likes
2 
# Boyer-Moore voting algorithm
def majority_element(numbers)
  numbers
    .reduce([nil, 0]) { |(candidate, count), el|
      candidate = el if count.zero?
      [candidate, count + ((el == candidate) ? 1 : -1)]
    }
    .first
end
2 Likes
3 
def majority_element(numbers)
  candidate = numbers.first

  numbers.reduce(0) do |vote_total, number|
    candidate = number if vote_total.zero?
    vote_total + (number == candidate ? 1 : -1)
  end

  candidate
end

One of those I’ve committed to memory (along with last week’s Kadane’s algorithm).

I will say that from my (admittedly somewhat lazy) benchmarks, the Ruby runtime tends to perform this better, even on arrays with thousands of elements.

def majority_element(numbers)
  midpoint = numbers.size / 2

  # because of the 'appears more than n/2 times' aspect, 
  # the answer will equal the median of all the numbers
  numbers.sort[midpoint]
end

But I also wouldn’t be surprised if there’s some more optimized way to write the Boyer-Moore voting algorithm in Ruby.

1 Like