Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.
  • Note:
1. The input array will only contain 0 and 1.

2. The length of input array is a positive integer and will not exceed 10,000
  • Examples:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.
  • Analysis:
Use two pointers, left and right.

The left pointer is to find the bit is 1

The right porinter is start from left pointer to find the end of this consecutive ones.
  • Code - Java:
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = 0;
        int result = 0;
        while (true) {
            while (left < len && nums[left] == 0) {
                left++;
            }
            if (left == len) {
                break;
            }
            right = left + 1;
            while (right < len && nums[right] == 1) {
                right++;
            }
            result = Math.max(result, right - left);
            if (right == len) {
                break;
            }
            left = right;
        }
        return result;
    }
}
  • Code - C++:
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int len = nums.size();
        int left = 0;
        int right = 0;
        int result = 0;
        while (true) {
            while (left < len && nums[left] == 0) {
                left++;
            }
            if (left == len) {
                break;
            }
            right = left + 1;
            while (right < len && nums[right] == 1) {
                right++;
            }
            result = max(result, right - left);
            if (right == len) {
                break;
            }
            left = right;
        }
        return result;
    }
};
  • Code - Python:
class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numLen, left, right, result = len(nums), 0, 0, 0
        while True:
            while left < numLen and nums[left] == 0:
                left += 1
            if left == numLen:
                break
            right = left + 1
            while right < numLen and nums[right] == 1:
                right += 1
            result = max(result, (right - left))
            if right == numLen:
                break
            left = right
        return result
  • Code - C:
int findMaxConsecutiveOnes(int* nums, int numsSize) {
    int len = numsSize;
    int left = 0;
    int right = 0;
    int result = 0;
    while (true) {
        while (left < len && nums[left] == 0) {
            left++;
        }
        if (left == len) {
            break;
        }
        right = left + 1;
        while (right < len && nums[right] == 1) {
            right++;
        }
        int diff = right - left;
        result = result < diff ? diff : result;
        if (right == len) {
            break;
        }
        left = right;
    }
    return result;
}
  • Time Complexity: O(N), N is the length of array.
  • Space Complexity: O(1)

results matching ""

    No results matching ""