Soyo

May Leetcode Challenge - Day 26

Contiguous Array

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

Count appearance of one and zero
Save different of appearance in a hashtable for further comparision

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
    }
}

Comments