Alkesh

LeetCode - Contiguous Array

Problem statement

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

Problem statement taken from: https://leetcode.com/problems/contiguous-array.

Example 1:

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

Example 2:

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

Constraints:

- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1

Explanation

Brute Force approach

The naive approach is to consider every subset of the array and verify if it has an equal number of 0's and 1's. Then we find out the maximum size subarray with equal no of 0's and 1's.

A C++ snippet of this approach looks as below:

int maxLength = 0;

for (int i = 0; i < nums.size(); i++) {
    int zeroes = 0, ones = 0;
    for (int j = i; j < nums.length; j++) {
        if (nums[j] == 0) {
            zeroes++;
        } else {
            ones++;
        }
        if (zeroes == ones) {
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }
}

return maxLength;

The time complexity of the above approach is O(N^2) which will timeout for big arrays.

Using additional array

In this approach, we use an additional array of size 2n + 1. We use an additional sum variable which will track the sum of the array elements while traversing. We will increment the sum by 1 when an element at a particular index is 1 and decrement the sum by -1 if the element is 0.

So the maximum and minimum sum we can reach is n and -n, where n is the size of the array. So we create an array of size 2n + 1 to keep track of the various sum's encountered so far. Whenever we come across the same sum value while traversing the array, we compute the length of the subarray by subtracting the value at that index from the current index. We compare the above value with the maximum subarray we might have encountered previously.

A C++ snippet of this optimized approach looks as below:

int n = nums.size();
int array[2 * n + 1];
array[n] = -1;
int maxLength = 0, count = 0;

for (int i = 0; i < n; i++) {
    count = count + (nums[i] == 0 ? -1 : 1);

    if (array[count + n] >= -1) {
        maxLength = max(maxLength, i - array[count + n]);
    } else {
        array[count + n] = i;
    }
}

return maxLength;

The time complexity of the above approach is O(N), and space complexity is O(N) for an array of size 2n + 1.

Using hash map

We can optimize the space to n by using a hash map instead of an array. The hash map will store the key-value pair in the form of index-sum.

We create an entry for a sum in the hash map whenever we encounter that sum for the first time and store its index as value. If we encounter the sum again, we subtract the existing index (value of hash map) from the current index.

Let's check the algorithm.

- set unordered_map[int, int] = {0 , -1}
  set maxLength = 0, sum = 0

- loop for i = 0; i < nums.size(); i++
  - sum = sum + (nums[i] == 1 ? 1 : -1)

  // the sum exists in the hash map update the maxLength
  // else set the current index for that sum
  - if m.count(sum)
    - maxLength = max(maxLength, i - m[sum])
  - else
    - m[sum] = i

- return maxLength

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> m{{0, -1}};
        int maxLength = 0, sum = 0;

        for(int i = 0; i < nums.size(); i++) {
            sum = sum + (nums[i] == 1 ? 1 : -1);

            if(m.count(sum)) {
                maxLength = max(maxLength, i - m[sum]);
            } else {
                m[sum] = i;
            }
        }

        return maxLength;
    }
};

Golang solution

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func findMaxLength(nums []int) int {
    m := make(map[int]int)
    maxLength, sum := 0, 0
    m[0] = -1

    for i := 0; i < len(nums); i++ {
        if nums[i] == 1 {
            sum = sum + 1
        } else {
            sum = sum - 1
        }

        if index, ok := m[sum]; ok  {
            maxLength = max(maxLength, i - index)
        } else {
            m[sum] = i
        }
    }

    return maxLength
}

Javascript solution

var findMaxLength = function(nums) {
    let m = {0: -1};
    let maxLength = 0, sum = 0;

    for(let i = 0; i < nums.length; i++) {
        sum = sum + (nums[i] == 1 ? 1 : -1);

        if(m[sum] === undefined) {
            m[sum] = i;
        } else {
            maxLength = Math.max(maxLength, i - m[sum]);
        }
    }

    return maxLength;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: [0, 1, 1, 0, 1, 1, 1, 0]

Step 1: unordered_map<int, int> m{{0, -1}}
        maxLength = 0, sum = 0

Step 2: loop for i = 0; i < nums.size()
        0 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = 0 + (nums[0] == 1 ? 1 : -1)
            = 0 + (0 == 1 ? 1 : -1)
            = 0 + -1
            = -1

        if m.count(sum)
           m.count(-1) // no key with -1
           false
        else
           m[sum] = i
           m[-1] = 0

        i++
        i = 1

Step 3: i < nums.size()
        1 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = -1 + (num[1] == 1 ? 1 : -1)
            = -1 + (1 == 1 ? 1 : -1)
            = -1 + 1
            = 0

        if m.count(sum)
           m.count(0) // has key with 0
           true

           maxLength = max(maxLength, i - m[sum])
                     = max(0, 1 - (-1))
                     = max(0, 2)
                     = 2

        i++
        i = 2

Step 4: i < nums.size()
        2 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = 0 + (num[2] == 1 ? 1 : -1)
            = 0 + (1 == 1 ? 1 : -1)
            = 0 + 1
            = 1

        if m.count(sum)
           m.count(1) // no key with -1
           false
        else
           m[sum] = i
           m[1] = 2

        i++
        i = 3

Step 5: i < nums.size()
        3 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = 1 + (num[3] == 1 ? 1 : -1)
            = 1 + (0 == 1 ? 1 : -1)
            = 1 + -1
            = 0

        if m.count(sum)
           m.count(0) // has key with 0
           true

           maxLength = max(maxLength, i - m[sum])
                     = max(2, 3 - (-1))
                     = max(2, 4)
                     = 4

        i++
        i = 4

Step 6: i < nums.size()
        4 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = 0 + (num[4] == 1 ? 1 : -1)
            = 0 + (1 == 1 ? 1 : -1)
            = 0 + 1
            = 1

        if m.count(sum)
           m.count(1) // has key with 1
           true

           maxLength = max(maxLength, i - m[sum])
                     = max(4, 4 - 2)
                     = max(4, 2)
                     = 2

        i++
        i = 5

Step 7: i < nums.size()
        5 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = 1 + (num[5] == 1 ? 1 : -1)
            = 1 + (1 == 1 ? 1 : -1)
            = 1 + 1
            = 2

        if m.count(sum)
           m.count(2) // no key with 2
           false
        else
           m[sum] = i
           m[2] = 5

        i++
        i = 6

Step 8: i < nums.size()
        6 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = 2 + (num[6] == 1 ? 1 : -1)
            = 2 + (1 == 1 ? 1 : -1)
            = 2 + 1
            = 3

        if m.count(sum)
           m.count(3) // no key with 3
           false
        else
           m[sum] = i
           m[3] = 6

        i++
        i = 7

Step 9: i < nums.size()
        7 < 8
        true

        sum = sum + (nums[i] == 1 ? 1 : -1)
            = 3 + (num[7] == 1 ? 1 : -1)
            = 3 + (0 == 1 ? 1 : -1)
            = 3 + -1
            = 2

        if m.count(sum)
           m.count(2) // has key with 0
           true

           maxLength = max(maxLength, i - m[sum])
                     = max(4, 7 - 5)
                     = max(4, 2)
                     = 4

        i++
        i = 8

Step 10: i < nums.size()
         8 < 8
         false

Step 11: return maxLength

So we return the answer as 4.
Share this post!