Day 13 of 30 days Leetcode Challenge

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note:
The length of the given binary array will not exceed 50,000.

Solution

Brute force approach, with two loops, takes O(n^2) time.

We can use same technique as prefix sum, count (0,1) appearances so far.
If difference between them was added to hash table, we can tell the result is maximum of substraction of first index and last index.

O(n) for time complexity, O(n) for space.

class Solution {
    func findMaxLength(_ nums: [Int]) -> Int {
        var zeroAppearance = 0
        var oneAppearance = 0
        
        var firstIndex = [0: -1]
        var longest = 0     

        for i in 0..<nums.count {
            if nums[i] == 0 {
                zeroAppearance += 1
            }else{
                oneAppearance += 1
            }
            
            let diff = zeroAppearance - oneAppearance
            
            guard let found = firstIndex[diff] else {
                firstIndex[diff] = i
                continue
            }
            
            longest = max(i - found, longest)
        }
    
        return longest
    }
}

Day 13 of 30 days Leetcode Challenge - Contiguous Array

Comments