Largest subarray of 0’s and 1’s

Given an array arr of 0s and 1s. Find and return the length of the longest subarray with equal number of 0s and 1s.

Examples:

Input: arr[] = [1, 0, 1, 1, 1, 0, 0]
Output: 6
Explanation: arr[1...6] is the longest subarray with three 0s and three 1s.

Input: arr[] = [0, 0, 1, 1, 0]
Output: 4
Explnation: arr[0...3] or arr[1...4] is the longest subarray with two 0s and two 1s.

Input: arr[] = [0]
Output: 0
Explnation: There is no subarray with an equal number of 0s and 1s.

Constraints:
1 <= arr.size() <= 10⁵
0 <= arr[i] <= 1

Approach 01:

class Solution {
public:
    int maxLen(vector<int>& nums) {
        unordered_map<int, int> prefixSumMap = {{0, -1}};
        int currentSum = 0;
        int maxLength = 0;

        // Traverse the array and maintain prefix sum
        for (int i = 0; i < nums.size(); ++i) {
            currentSum += (nums[i] == 1 ? 1 : -1);

            // Check if the prefix sum has been seen before
            if (prefixSumMap.find(currentSum) != prefixSumMap.end()) {
                maxLength = max(maxLength, i - prefixSumMap[currentSum]);
            }

            // Store the prefix sum if it's not already present
            if (prefixSumMap.find(currentSum) == prefixSumMap.end()) {
                prefixSumMap[currentSum] = i;
            }
        }

        return maxLength;
    }
};

class Solution:
    def maxLen(self, nums):
        prefixSumMap = {0: -1}
        currentSum = 0
        maxLength = 0

        # Traverse the array and maintain prefix sum
        for i in range(len(nums)):
            currentSum += 1 if nums[i] == 1 else -1

            # Check if the prefix sum has been seen before
            if currentSum in prefixSumMap:
                maxLength = max(maxLength, i - prefixSumMap[currentSum])

            # Store the prefix sum if it's not already present
            if currentSum not in prefixSumMap:
                prefixSumMap[currentSum] = i

        return maxLength

Time Complexity:

• Array Traversal:

  We traverse the array once, which takes \( O(n) \), where \( n \) is the size of the array.

• Hash Map Operations:

  For each element, we perform at most one insertion and one lookup in the hash map. Since both operations take \( O(1) \) on average, the total time complexity for hash map operations is \( O(n) \).

• Overall Time Complexity:

  The total time complexity is \( O(n) \).

Space Complexity:

• Hash Map Space:

  The hash map stores prefix sums, which are unique. In the worst case, there can be \( O(n) \) unique prefix sums, so the space complexity for the hash map is \( O(n) \).

• Overall Space Complexity:

  The total space complexity is \( O(n) \).