Coder's Cat

LeetCode: Max Consecutive Ones

2020-11-20

Description

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

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.

Naive Solution

Iterating the array, use cnt to record the number of consecutive ones. Update idx to the position of next 0.
The time complexity is: O(N).

class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int ans = 0;
int idx = 0;
int cnt = 0;
while(idx < nums.size()) {
if(nums[idx] == 0) idx++;
else {
cnt = 0;
while(idx < nums.size() && nums[idx] == 1) {
cnt++;
idx++;
}
ans = max(cnt, ans);
}
}
return ans;
}
};

Dynamic programming

Define dp(i) as the length of consecutive 1s ends with position i. The recurrence relation is:

Time complexity is: O(N), space complexity is: O(N)

class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
vector<int> dp(nums.size());
if(nums.size() == 0) return 0;
int ans = 0;
dp[0] = nums[0] == 1 ? 1 : 0;
ans = dp[0];
for(int i=1; i<nums.size(); i++) {
if(nums[i] == 1) {
dp[i] = dp[i-1] + 1;
}
ans = max(dp[i], ans);
}
return ans;
}
};

In this approach we used more memory? Actually, we only need to store the current count of 1s.

If we reduce the array to only a count, seems we get almost the same code with solution #1.

class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
if(nums.size() == 0) return 0;
int count = 0;
int ans = 0;
for(int i=0; i<nums.size(); i++) {
if(nums[i] == 1) {
count++;
} else {
ans = max(count, ans);
count = 0;
}
}
ans = max(count, ans);
return ans;
}
};

Preparing for an interview? Check out this!