Consecutive Ones Algorithm

You are given a list of integers nums which contains at least one 1. Return whether all the 1s appear consecutively.

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [0, 1, 1, 1, 2, 3]
Output
True
Explanation
All the 1s appear consecutively here in the middle.

Example 2
Input
nums = [1, 1, 0, 1, 1]
Output
False
Explanation
There’s two groups of consecutive 1s.

Hints:
Try to find the minimal distance between all two ones that appear one after another. Try to find a relation between this minimal distance and the solution.
Alternative: Try compressing the ones, then count the number of ones in the array is one or not

Linear Algorithm to Check if All Ones are Consecutive

When we meet one, we set meetOne flag to true, and after that when we meet a space, we set the corresponding flag to true. We can return false if we have meet one and there was a space and previous one(s).

The following C++ code to check if all ones are consecutive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool consecutiveOnes(vector<int>& nums) {
    bool meetOne = false;
    bool space = false;
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] == 1) {
            if (space) return false;
            meetOne = true;
        } else {
            if (meetOne) {
                space = true;
            }
        }
    }
    return true;
}

bool consecutiveOnes(vector<int>& nums) {
    bool meetOne = false;
    bool space = false;
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] == 1) {
            if (space) return false;
            meetOne = true;
        } else {
            if (meetOne) {
                space = true;
            }
        }
    }
    return true;
}

Single pass O(N) time and O(1) space.

–EOF (The Ultimate Computing & Technology Blog) —