A naive Java solution using O(1) extra space (thus must be O(n) time)

  • 2

    public class Solution {

    public int majorityElement(int[] nums) {
        int majority = nums[0];
        int cnt = 1;
        for(int i = 1; i < nums.length; ++i){
            if(cnt == 0){
                majority = nums[i];
                if(majority == nums[i])
        return majority;


  • -2

    you answer is not right even it passes the OJ. Try[1,2,3,4,5,6,7,7], it will give answer 7 which is not right.
    It is half Boyer-Moore Implementation, it only makes sure majority has the max occurrence but not greater than ⌊ n/2 ⌋
    you need to loop through the array again to check if majority is actually the answer.

  • 0

    "You may assume that the array is non-empty and the majority element always exist in the array."-- Please read the description again.

Log in to reply

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