485.max-consecutive-ones.md

485. Max Consecutive Ones

Iteration

We count the 1 and reset the counter as 0 occurs.

fun findMaxConsecutiveOnes(nums: IntArray): Int {
    var count = 0
    var ans = 0
    for (i in nums.indices) {
        if (nums[i] == 1) {
            count++
        } else {
            count = 0
        }
        ans = maxOf(ans, count)
    }
    return ans
}

// Equivalent, the key difference is where to update the answer
fun findMaxConsecutiveOnes(nums: IntArray): Int {
    var count = 0
    var ans = 0
    for (i in nums.indices) {
        if (nums[i] == 1) {
            count++
        } else {
            // Encounter a boundary, update the answer first
            ans = max(ans, count)
            // Then reset the counter
            count = 0
        }
    }
    // Update for the last group like `[..., 1, 1]`
    // For example: [1, 1, 1, 1], there is no 0's, 
    ans = max(ans, count)
    return ans
}

Group by Consecutive

fun findMaxConsecutiveOnes(nums: IntArray): Int {
    var i = 0
    var ans = 0
    while (i < nums.size) {
        // Skip invalid `0`
        if (nums[i] == 0) {
            i++
            continue
        }
        // Start counting the longest `1`.
        val start = i
        i++
        while (i < nums.size && nums[i] == 1) {
            i++
        }
        ans = maxOf(ans, i - start)
    }
    return ans
}

X * 0 = 0

It's a binary array, that means the element is either 0 or 1:

• Every number times zero is zero.
• Every number times one is itself.

fun findMaxConsecutiveOnes(nums: IntArray): Int {
    var maxCount = 0
    var currentCount = 0
    nums.forEach { i ->
        currentCount = (currentCount + i) * i
        maxCount = max(macCount, currentCount)
    }
    return maxCount
}

Both solutions have the same complexity:

• Time Complexity: O(n) for only one for-loop.
• Space Complexity: O(1) for two counters.