Problem Statement

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

LeetCode:

525. Contiguous Array

Constraints:

• 1 ≤ nums.length ≤ 10^5
• nums[i] is either 0 or 1

From these constraints we can conclude that we have to solve it either in O(n) or O(n log n).

Since the maximum length of the array can be 10^5, an O(n^2) solution would require up to 10^10 operations. This far exceeds the typical computational limit of around 10^8 operations, and thus would result in TLE (Time Limit Exceeded).

Examples

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 the longest contiguous subarray with equal number of 0 and 1.

Example 3:

Input: nums = [0, 1, 1, 1, 1, 1, 0, 0, 0]
Output: 6

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

Different Approaches

1️⃣ Brute Force Approach (TLE)

Intuition:

We consider every possible subarray within the given array and count the number of zeroes and ones in each subarray. Then, we find out the maximum size subarray with equal no. of zeroes and ones out of them.

Code:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int zeroCount = 0;
                int oneCount = 0;

                for (int k = j; k < n; k++) {
                    if (nums[k] == 0) {
                        zeroCount++;
                    } else {
                        oneCount++;
                    }
                    if (zeroCount == oneCount) {
                        maxLength = max(maxLength, zeroCount + oneCount);
                    }
                }
            }
        }
        return maxLength;
    }
};

2️⃣ Better Approach (TLE)

Code:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            int zeroCount = 0;
            int oneCount = 0;
            
            for (int j = i; j < n; j++) {
                    if (nums[j] == 0) {
                        zeroCount++;
                    } else {
                        oneCount++;
                    }
                    if (zeroCount == oneCount) {
                        maxLength = max(maxLength, zeroCount + oneCount);
                    }

            }
        }
        return maxLength;
    }
};

Complexity Analysis:

• Time Complexity: O(n^2)
• Space Complexity: O(1)