Solution by SuperElephant


  • 0
    S

    Approach #1 Count when 1 reset when 0 [Accept]

    Intuition

    Iterate all number, if it equals 1, increase the counter. Else, reset the counter. Then get the max count number after reading all numbers.

    Algorithm

    Firstly, we should have a variable int count as a counter to record the present number of consecutive 1s. Also, we need a variable int max to record the maximum number of consecutive 1s.

    Then we start iterate nums. For each num read, if it equals 1 we get a consecutive 1. So we increase count by count++ (notice, count++ will be efficient then count += num, since it needs an extra access to memory).

    If it equals 0, it means the continuity is broken. Thus, we should set count.However, to save the space, we don't store all number of consecutive 1s. Instead, we compare current count with max. If it is bigger then max, we update max. In this way, we can keep making sure max holds the current maximum number of consecutive 1s.

    And at last, if the last segment is holding most consecutive 1s, we will not able to update max. Since we have no further 0. Therefore, we need to return the bigger number of max and count, which will be our final answer.

    Java

    class Solution {
        public int findMaxConsecutiveOnes(int[] nums) {
            int count = 0;
            int max = 0;
            for (int num : nums) {
                if (num == 1){
                    count++;
                } else {
                    if (count > max)
                        max = count;
                    count = 0;
                }
            }
            return Math.max(max,count);
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.
      For each number of the array (holds $$n$$ numbers) we need to increase the counter or reset the counter. And we need do comparison for $$m$$ times, where $$ m < n $$.
      Thus, the final complexity is $$O(n)$$.

    • Space complexity : $$O(1)$$.
      Since we only use 2 (constant number of) variable.


Log in to reply
 

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