Contiguous Array — Leetcode 525

Java Solution for finding Contiguous Array

1. Problem

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

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.

Example 3:

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

2. Solution

2.1. Brute Force

we can use a brute-force approach by checking every possible subarray and counting the number of 0s and 1s in each:

class Solution {
    
    public int findMaxLength(int[] nums) {
        int result = 0;

        // Iterate over all possible starting points of subarrays
        for(int i=0; i < nums.length; i++){
            int zeroCount = 0;
            int oneCount = 0;
        // For each starting point, iterate over all possible ending points
            for(int j=i; j< nums.length; j++){
                // Update counts based on the current element
                if(nums[j] == 0) zeroCount++;
                if(nums[j] == 1) oneCount++;
                // Check if the subarray has an equal number of 0s and 1s
                if(zeroCount == oneCount){
                   result = Math.max(result, j - i + 1);
                }
            }
        }

        return result;
    }
}

Explanation:

Outer Loop (i):

• This loop iterates through every possible starting point of the subarray. The index i represents the starting point of a subarray.

Inner Loop (j):

• For each starting point i, we then iterate over every possible ending point j, where j starts from i and goes to the end of the array. This loop defines the subarray [i, j].

Counting 0s and 1s:

• For every subarray [i, j], we maintain two counters: zeroCount and oneCount. Each time we encounter a 0, we increment zeroCount, and each time we encounter a 1, we increment oneCount.

Checking Equal Counts:

• After updating the counts for each subarray, we check if zeroCount equals oneCount. If they are equal, it means the current subarray has an equal number of 0s and 1s, and we update maxLength if this subarray is longer than the previously found subarrays.

Return:

• After both loops finish, we return the maxLength, which contains the length of the longest subarray with an equal number of 0s and 1s.

Time Complexity:

• Outer loop (i): Runs n times, where n is the length of the array.

• Inner loop (j): For each value of i, j runs (n - i) times, making the total complexity O(n2)O(n^2)O(n2).

Space Complexity:

• O(1): No extra data structures are used except for the counters (zeroCount, oneCount) and maxLength, so the space complexity is constant.

2.2. Optimized Solution

Optimized solution to the problem of finding the maximum length of a contiguous subarray with an equal number of 0s and 1s can be achieved using a hash map (or hash table) approach. This approach leverages the concept of prefix sums and efficiently tracks when a balanced subarray is encountered by using a running sum (or "count") to map the difference between the number of 0s and 1s.

Here’s how the O(N) solution works:

Key Idea:

• Replace 0 with -1 to transform the problem into finding a subarray whose sum is zero.

• Keep a running sum (count), where you:

• Add 1 for each 1 in the array.

• Subtract 1 for each 0 in the array.

• If the same count is encountered again, it means that the subarray between the previous occurrence of this count and the current index has an equal number of 0s and 1s. The length of this subarray is the difference between the two indices.

class Solution {    
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> lookup = new HashMap<>();
        lookup.put(0, -1);

        int count = 0;
        int maxLength = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] == 0){
                count -= 1;
            }else if(nums[i] == 1){
                count += 1;
            }

            if(lookup.containsKey(count)){
                int index = lookup.get(count);
                maxLength = Math.max(i-index, maxLength);
            }else{
                lookup.put(count, i);
            }
        }

        return maxLength;
    }
}

Explanation:

Transform the problem: Treat 0 as -1 and leave 1 as 1. This transforms the task of finding an equal number of 0s and 1s into finding subarrays whose sum is 0.

Hash Map (countMap):

• The hash map countMap stores the first occurrence of each running sum (count).

• The key is the count, and the value is the index where that count was first encountered.

Running sum (count):

• As we iterate through the array, we update the count:

• Increment by 1 for a 1.

• Decrement by 1 for a 0.

• If the same count is seen again, it means that the subarray between the first occurrence of this count and the current index has an equal number of 0s and 1s.

Initial state:

• We initialize countMap.put(0, -1) to handle the case where the entire subarray from the start has an equal number of 0s and 1s.

Result:

• The result is stored in maxLength, which keeps track of the longest balanced subarray found during the iteration.

Time Complexity:

• O(n): We traverse the array exactly once (where n is the number of elements in the array).

• O(1) (amortized): Insertions and lookups in the hash map take constant time on average.

Space Complexity:

• O(n): In the worst case, the hash map could store all n entries if no duplicate count values are found during traversal.

3. Conclusion

While the brute-force approach works for small arrays, its O(N²) complexity is inefficient for larger datasets. The hash map method is the optimal solution, achieving O(N) time complexity and O(N) space complexity, making it far more suitable for handling large inputs. This problem highlights the effectiveness of leveraging hash maps and running sums to optimize subarray problems that involve balance criteria, reducing complexity from quadratic to linear.