Max Consecutive Ones

easy

Last Updated - 08/09/2024

Problem Statement Solution 1: Simple Iteration Approach Solution 2: Sliding Window Approach Solution 3: Two Pointers Approach Solution 4: Using Reduce Solution 5: Using Regular Expressions Solution 6: Using Binary Search Solution 7: Using Dynamic Programming Solution 8: Using a Stack Solution 9: Using a Map to Count Ones Solution 10: Using a Set More Problems Solutions

Problem Statement

You are given a binary array, nums, consisting of only 0s and 1s. Your task is to determine the maximum number of consecutive 1s present in this array.

Details:

Input: A binary array nums where 1 <= nums.length <= 100,000. Each element in the array is either 0 or 1.
Output: An integer representing the longest sequence of consecutive 1s in the given array.

Example 1

Input: nums = [1,1,0,1,1,1]

Output: 3

Example 2

Input: nums = [1,0,1,1,0,1]

Output: 2

Constraints

The length of the array is at least 1 and at most 100,000.
The array contains only 0s and 1s.

Solution 1: Simple Iteration Approach

function maxConsecutiveOnesSimple(nums) {
    let maxCount = 0;
    let currentCount = 0;

    for (const num of nums) {
        if (num === 1) {
            currentCount++;
            maxCount = Math.max(maxCount, currentCount);
        } else {
            currentCount = 0;
        }
    }

    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesSimple(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesSimple(nums2);  //output: 2

Solution 2: Sliding Window Approach

function maxConsecutiveOnesSlidingWindow(nums) {
    let left = 0;
    let right = 0;
    let maxCount = 0;

    while (right < nums.length) {
        if (nums[right] === 1) {
            right++;
        } else {
            maxCount = Math.max(maxCount, right - left);
            right++;
            left = right;
        }
    }

    maxCount = Math.max(maxCount, right - left);
    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesSlidingWindow(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesSlidingWindow(nums2);  //output: 2

Solution 3: Two Pointers Approach

function maxConsecutiveOnesTwoPointers(nums) {
    let maxCount = 0;
    let left = 0;

    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) {
            left = right + 1;
        }
        maxCount = Math.max(maxCount, right - left + 1);
    }

    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesTwoPointers(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesTwoPointers(nums2);  //output: 2

Solution 4: Using Reduce

function maxConsecutiveOnesReduce(nums) {
    let maxCount = 0;
    let currentCount = 0;

    nums.reduce((_, num) => {
        if (num === 1) {
            currentCount++;
        } else {
            maxCount = Math.max(maxCount, currentCount);
            currentCount = 0;
        }
        maxCount = Math.max(maxCount, currentCount);
    }, 0);

    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesReduce(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesReduce(nums2);  //output: 2

Solution 5: Using Regular Expressions

function maxConsecutiveOnesRegex(nums) {
    const binaryString = nums.join('');
    const match = binaryString.match(/1+/g) || [];
    const maxCount = Math.max(...match.map(seq => seq.length));
    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesRegex(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesRegex(nums2);  //output: 2

Solution 6: Using Binary Search

function maxConsecutiveOnesBinarySearch(nums) {
    const countOnes = (arr) => {
        let maxCount = 0;
        let currentCount = 0;
        for (const num of arr) {
            if (num === 1) {
                currentCount++;
                maxCount = Math.max(maxCount, currentCount);
            } else {
                currentCount = 0;
            }
        }
        return maxCount;
    };

    let maxCount = countOnes(nums);
    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesBinarySearch(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesBinarySearch(nums2);  //output: 2

Solution 7: Using Dynamic Programming

function maxConsecutiveOnesDP(nums) {
    if (nums.length === 0) return 0;

    let dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
    let maxCount = dp[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === 1) {
            dp[i] = dp[i - 1] + 1;
        } else {
            dp[i] = 0;
        }
        maxCount = Math.max(maxCount, dp[i]);
    }

    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesDP(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesDP(nums2);  //output: 2

Solution 8: Using a Stack

function maxConsecutiveOnesStack(nums) {
    let stack = [];
    let maxCount = 0;

    for (const num of nums) {
        if (num === 1) {
            stack.push(1);
        } else {
            if (stack.length > 0) {
                maxCount = Math.max(maxCount, stack.length);
                stack = [];
            }
        }
    }

    maxCount = Math.max(maxCount, stack.length);
    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesStack(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesStack(nums2);  //output: 2

Solution 9: Using a Map to Count Ones

function maxConsecutiveOnesMap(nums) {
    const counts = new Map();
    let currentCount = 0;
    let maxCount = 0;

    for (const num of nums) {
        if (num === 1) {
            currentCount++;
        } else {
            counts.set(currentCount, (counts.get(currentCount) || 0) + 1);
            maxCount = Math.max(maxCount, currentCount);
            currentCount = 0;
        }
    }

    counts.set(currentCount, (counts.get(currentCount) || 0) + 1);
    maxCount = Math.max(maxCount, currentCount);
    
    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesMap(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesMap(nums2);  //output: 2

Solution 10: Using a Set

function maxConsecutiveOnesSet(nums) {
    let maxCount = 0;
    let currentCount = 0;

    for (const num of nums) {
        if (num === 1) {
            currentCount++;
            maxCount = Math.max(maxCount, currentCount);
        } else {
            currentCount = 0;
        }
    }

    return maxCount;
} 

const nums1 = [1,1,0,1,1,1];
maxConsecutiveOnesSet(nums1);  //output: 3 

const nums2 = [1,0,1,1,0,1];
maxConsecutiveOnesSet(nums2);  //output: 2