Algorithms for detecting when one value makes up more than half of an array
This was a coding challenge that was on an a shared-coding website that an interviewer sent to me a couple days before the interview. I worked on the problem for a few hours across two nights, and while it turned out that the interviewer had a different problem that he pasted in when the interview started, I offered to share what I had come up with on this problem.
Given an array, detect if there is a majority value, a value that shows up as more than half of the values of the array. If there is no majority value, return -1. Expected Time Complexity: O(n) Expected Space Complexity: O(1)