Last updated on February 20th, 2025 at 08:59 am
Here, we see a Contiguous Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table
Companies
Level of Question
Medium
Contiguous Array LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in the Java, JavaScript, and Python implementations is “Prefix Sum with Hash Map”. The C++ implementation, however, uses a Brute Force approach.
3. Code Implementation in Different Languages
3.1 Contiguous Array C++
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int maxlen = 0;
for (int i = 0; i < nums.size(); i++) {
int zeroes = 0, ones = 0;
for (int j = i; j < nums.size(); j++) {
if (nums[j] == 0) {
zeroes++;
} else {
ones++;
}
if (zeroes == ones) {
maxlen = max(maxlen, j - i + 1);
}
}
}
return maxlen;
}
};
3.2 Contiguous Array Java
class Solution {
public int findMaxLength(int[] nums) {
int n = nums.length;
Map<Integer, Integer> mp = new HashMap<>();
int sum = 0;
int subArrayLength = 0;
for (int i = 0; i < n; i++) {
sum += nums[i] == 0 ? -1 : 1;
if (sum == 0) {
subArrayLength = i + 1;
} else if (mp.containsKey(sum)) {
subArrayLength = Math.max(subArrayLength, i - mp.get(sum));
} else {
mp.put(sum, i);
}
}
return subArrayLength;
}
}
3.3 Contiguous Array JavaScript
var findMaxLength = function(nums) {
let mp = new Map();
let sum = 0;
let subArrayLength = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i] === 0 ? -1 : 1;
if (sum === 0) {
subArrayLength = i + 1;
} else if (mp.has(sum)) {
subArrayLength = Math.max(subArrayLength, i - mp.get(sum));
} else {
mp.set(sum, i);
}
}
return subArrayLength;
};
3.4 Contiguous Array Python
class Solution(object):
def findMaxLength(self, nums):
mp = {}
sum_val = 0
max_len = 0
for i, num in enumerate(nums):
sum_val += 1 if num == 1 else -1
if sum_val == 0:
max_len = i + 1
elif sum_val in mp:
max_len = max(max_len, i - mp[sum_val])
else:
mp[sum_val] = i
return max_len
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n²) | O(1) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |
- C++ Brute Force:
- Inefficient for large arrays due to the O(n²) time complexity.
- No additional space is used, making it space-efficient.
- Java, JavaScript, and Python (Prefix Sum with Hash Map):
- Efficient with O(n) time complexity due to the single traversal of the array.
- Requires O(n) space for the hash map to store prefix sums.