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.
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1.The idea is to transform the array by converting 0s to -1s, which allows us to restate the problem as finding the longest contiguous subarray with a sum of 0. We can use a hash map to store the first occurrence of each prefix sum.
In this C solution, we allocate an array hashMap to store the first indices of various counts. We initialize the map to -2, and the theoretical zero balance to -1. As we iterate over the array, we update the count for either 0s or 1s. We check if this count has been seen before and update the maximum length accordingly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(n) for the hash map storage.
This simple approach checks every possible subarray and calculates its sum, verifying if it has an equal number of 0s and 1s. This method, while simple, serves as an exercise in understanding the problem better prior to using an optimized solution.
This brute-force method iterates over each possible starting point and ending point of a subarray, counting the number of 0s and 1s and checking their equality. This gives a straightforward, albeit inefficient solution.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(1), as we do not use extra space other than primitive variables.
| Approach | Complexity |
|---|---|
| Prefix Sum with Hash Map | Time Complexity: O(n), where n is the length of the input array. |
| Brute Force Approach | Time Complexity: O(n^2) |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,131 views views
Watch 9 more video solutions →Practice Contiguous Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor