寻找最大平衡子数组

1. Introduction

In this tutorial, we’ll see how to find the largest balanced subarray in a binary array.

2. Problem Description

Given a binary array consisting of only zeros and ones, find the maximum length of a contiguous subarray with an equal number of zero and one. For example, if the array is , then the maximum length of the balanced subarray is 4. Also, the related balanced subarray is .

3. Brute Force Approach

Let’s suppose the number index of the array starts with , i.e., . We can explore every possible subarray and count the number of zeros and ones in each subarray:

algorithm MaxBalancedSubarrayLength(A, n):
    // INPUT
    //    A = a binary array
    //    n = the length of A
    // OUTPUT
    //    The length of the maximum balanced subarray of A

    maxLength <- 0

    for i <- 0 to n - 2:
        zeroCount <- 0
        oneCount <- 0

        for j <- i to n - 1:
            if A[j] = 0:
                zeroCount <- zeroCount + 1
            else:
                oneCount <- oneCount + 1

            if zeroCount = oneCount:
                maxLength <- max(maxLength, j - i + 1)

    return maxLength

This algorithm uses two nested loops to go through all possible subarrays of . The outer loop defines the start position, , of the subarray. The inner loop defines the end position, , of the subarray that starts at the position . In each iteration, we count the number of zeros and ones of the subarray. If we see an equal number of zeros and ones, we check the subarray size and record the maximum one.

Since we have two nested loops over the array , the overall time complexity of this algorithm is , where is the number of elements in the array . Also, the space requirement is as we only use a constant number of variables, such as and .

4. Hash Table Approach

We can use a variable to store the relative number of ones and zeros encountered so far while traversing the array. In each iteration we increase the by if we see . Otherwise, we decrease the by .

Suppose the value is at position . Later, we encounter the same value at position . Then, we have the same amount of increments and decrements during the traversal. Therefore, the subarray from position to position contains the same number of zeros and ones. Also, the length of the corresponding subarray is .

For example, if the array is , we can have the following value changes:

index

-1

0

1

2

3

4

5

6

7

8

array

0

1

1

0

1

1

1

1

0

counter

0

-1

0

1

0

1

2

3

4

3

We start the value with . If in the future, the becomes again at position index , the subarray from beginning index till the current index is a balanced array. Also, the length of the subarray is . Therefore, we associate index with value . In this way, we can calculate the subarray length easily by subtracting two indexes.

In our example, we again encounter twice at indexes and , and the corresponding array lengths are and . Also, we see value at index and meet it again at index . Therefore, the subarray from index to is also a balanced array with a length of . Similarly, we have another balanced array from index to as we encounter twice. Overall, the maximum balanced array length is . The corresponding subarray starts at index and ends at index , which is .

4.1. Hash Table

Based on the above observations, we can use a hash table to store all possible values. Each entry of a hash table contains a pair . We can use as the key and the corresponding index position as the entry value. If we encounter the same again, we can then use the indexes to calculate the length of the subarray:

algorithm HashTableApproach(A, n):
    // INPUT
    //    A = a binary array
    //    n = the size of array A
    // OUTPUT
    //    The length of the maximum balanced subarray of A

    hashTable <- construct an empty hash table
    maxLength <- 0
    counter <- 0
    Put (0, -1) into hashTable

    for i <- 0 to n - 1:
        if A[i] = 1:
            counter <- counter + 1
        else:
            counter <- counter - 1
        
        if hashTable contains counter as a key:
            start <- hashTable.getValue(counter)
            maxLength <- max(maxLength, i - start)
        else:
            Put (counter, i) into hashTable

    return maxLength

In this algorithm, we first initialize an empty hash table. Then, we create a variable with the initial value of . Also, we add the hash table entry for the value 0. In each iteration, we increase or decrease the value by 1 based on the array number value. Also, if we see the hash table contains the value, we calculate the subarray size and record the maximum one.

Since we only go through the array once, the overall time complexity of this algorithm is . However, the maximum size of the hashtable is if all the elements are either 1 or 0. Therefore, the space requirement is .

5. Conclusion

In this tutorial, we showed two algorithms to find the largest balanced subarray in a binary array. The brute force approach takes time to solve the problem with space. We can also use a hash table approach to solve this problem with a better performance of but with space.