Java O(n) time O(1) space optimal solution


  • 17
    public class Solution {
        public int majorityElement(int[] nums) {
            int candidate = 0;
            int count = 0;
            for (int num : nums) {
                if (count == 0) {
                    candidate = num;
                    count++;
                } else if (candidate == num) {
                    count++;
                } else {
                    count--;
                }
            }
            return candidate;
        }
    }

  • 0
    R

    I think I've figured a fail test case for this algorithm?
    nums = {1, 2, 1, 2, 1, 2, 1, 2, 3, 2}
    it outputs 3 while it should be 2


  • 0

    The problem states that majority element is more than half of total. In your case there are five 2 which is equal to half of 10. So it is invalid input. My solution is bug free.


  • 0
    R

    Ahh! You're right, it said more than half.


  • 0
    C

    It does seem to work but whats the mathematical/logical basis for this algorithm?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.