Java Straightforward O(n) solution


  • 3

    Also viewable here.

    
        public int findMaxConsecutiveOnes(int[] nums) {
            int maxOnes = 0;
            for (int i = 0; i < nums.length; i++){
                int newOnes = 0;
                while (i < nums.length && nums[i] == 1){
                    newOnes++;
                    i++;
                }
                maxOnes = Math.max(maxOnes, newOnes);
            }
            return maxOnes;
        }
    

  • 1
    V

    @fishercoder It is not O(n) since it have two loop. It should be O(n^2). Can you please clarify your stand?


  • 0

    @vpb8262 Good question, but if you look more closely, the two loops don't overlap each other, it's scanning the array only once.

    Consider this below nested loops:

    for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    //your business logic
                }
    }
    

    This is really O(n^2).


  • 0
    P

    @fishercoder Your inner loop is going to visit same array indices more than once. Your solution definitely is more than O(n).


  • 0

    @parthsha
    If you looks more closely, or if you fire up your IDE and set up a breakpoint, you can see that i keeps incrementing in both for and while loop, you'll never visit the same indices twice.
    It's O(n).


  • 1
    A

    O(n)
    public int findMaxConsecutiveOnes(int[] nums) {
    int max = 0;

        for(int x = 0; x < nums.length; ){
        	int numOnes = 0;
        	if(nums[x++] == 1){
        		numOnes++;
        		while(x < nums.length && nums[x++]==1)
        			numOnes++;
        		if(max < numOnes)
        			max = numOnes;
        	}
        }
        
        return max;
    }

Log in to reply
 

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