maximum number of consecutive in swift

Question

I am trying to learn Swift by solving easy interview questions on LeetCode.

Question is as follows:

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.

Note:

The input array will only contain 0 and 1. The length of input array is a positive integer and will not exceed 10,000

I have solved the following question, no issue, it runs and covers up test cases, but it shows my submission is only 73 percent faster than all the submissions. I wonder whether or not there is a better way to solve this question. My solution time complexity is O(n).

class Solution {
    func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {

        var globalMax = 0
        var localMax = 0

        for num in nums
        {
           if num == 1
           {
              localMax += 1
              globalMax = max(globalMax, localMax)
           }
           else
           {
                localMax = 0
           }  
        }
        return globalMax
    }
}

Answer 1

Two minor adjustments, checking array size isn't really necessary and calling max only needs to be done when a 0 is found and at the end

func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
    var globalMax = 0
    var localMax = 0

    for num in nums {
       if num == 1 {
          localMax += 1              
       } else {
            globalMax = max(globalMax, localMax)
            localMax = 0
       }  
    }
    return max(globalMax, localMax)
}

I did an experiment with split and reduce and this combo seems slightly faster than the one above but about the same as the one linked to in the comments

func findMaxConsecutiveOnes3(_ nums: [Int]) -> Int {
    return nums.split(separator: 0).reduce(ArraySlice<Int>(), { ($1.count > $0.count) ?  $1 : $0 }).count
}

Answer 2

Your question is more appropriate for the Code Review site. The rankings in LeetCode are not reliable and may vary from submission to the next (with the same code).

Here is a solution that avoids if .. else (original java code here) :

func findMaxConsecutiveOnes4(_ nums: [Int]) -> Int {
    var globalMax = 0
    var localMax = 0

    for num in nums {
        localMax *= num
        localMax += num
        globalMax = max(globalMax, localMax)
    }
    return globalMax
}

For benchmarking, I've used the following code :

let array = (0...10_000).map { _ in Int.random(in: 0..<2) }

let start1 = mach_absolute_time()
let x1 = findMaxConsecutiveOnes1(array)
let end1 = mach_absolute_time()
print("1st", x1, Double(end1 - start1)/Double(1e3), "us")

let start2 = mach_absolute_time()
let x2 = findMaxConsecutiveOnes2(array)
let end2 = mach_absolute_time()
print("2nd", x2, Double(end2 - start2)/Double(1e3), "us")

let start3 = mach_absolute_time()
let x3 = findMaxConsecutiveOnes3(array)
let end3 = mach_absolute_time()
print("3rd", x3, Double(end3 - start3)/Double(1e3), "us")

Where findMaxConsecutiveOnes is your solution, findMaxConsecutiveOnes2 is Joakim's, and findMaxConsecutiveOnes3 is the one proposed in this answer.

Compiled with optimizations (-O) in the terminal, here are the execution times:

• findMaxConsecutiveOnes1 : 49.079 us
• findMaxConsecutiveOnes2 : 54.016 us
• findMaxConsecutiveOnes3 : 14.883 us

---

Faster than 100.00% of Swift online submissions (For now)

The following implementation is considered the current fastest by LeetCode :

func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {

    guard !nums.isEmpty else {
        return 0
    }

    var globalMax = 0
    var localMax = -1

    for i in 0..<nums.count {
        if nums[i] != 1 { //It is faster than: if nums[i] == 0
            localMax = i
        }
        globalMax = max(globalMax, i - localMax)
    }
    return globalMax
}

Here is the original C++ implementation.

In my benchmarks, it didn't perform as expected : 33.615 us on a 10,000 element array.

But, on smaller sized arrays, it proved to be the quickest solution.

---

Even faster solution

This is the fastest :

func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {

    guard !nums.isEmpty else {
        return 0
    }

    var globalMax = 0
    var lastZeroIdx = -1

    for i in 0..<nums.count {
        if nums[i] == 0 {
            globalMax = max(lastZeroIdx == -1 ? i : i - lastZeroIdx - 1, globalMax)
            lastZeroIdx = i
        }
    }
    globalMax = max(lastZeroIdx == -1 ? nums.count : nums.count - lastZeroIdx - 1, globalMax)
    return globalMax
}

It was ported from this java implementation.

In my benchmarks, I couldn't notice any improvement in execution time on neither small (10-element) nor big (10,000-element -> 42.363 us) arrays .

Answer 3

Perhaps they expect some Swift-specific tricks.

If not - I could suppose that checking system dislikes calculations at every 1-item.

You can calculate global max only in case of 1-0 transition (or at the end of array). In this case you also need to remember index of 1 in case of 0-1 change.