# Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1

Algorithm question:

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

Example 1:
Input: [0,1] Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2: Input: [0,1,0] Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Original source: https://leetcode.com/problems/contiguous-array/

This question reminded me of prefix-sum questions i had done before. Given array nums:

sum(nums[0:i]) + sum(nums[i:j]) = sum(nums[0:j])


So I figured:

Assuming 2*sum(nums[i:j]) =  len(nums[i:j])-> always True for valid subarrays,

2sum(i:j) = 2(sum(0:j)- sum(0:i))

(j-i+1) = 2(sum(0:j)- sum(0:i))

-i+2sum(0:i) +1 = 2sum(0:j)-j


But it looks like Im having trouble with the code assuming this. I was excited to separate the i and the j (indexes) so that i can hash like so:

        key: -i+2sum(0:i) +1,      value: i
check for the key with our j value later,
then do j-i+1
then compare that to a running global max.


Code:

        d = {}
sum = 0
m = 0
for j in range(len(nums)):
sum += nums[j]
if 2*sum - j in d:
i = d[2*sum - j]
m = max(m,j-i+1)
if 2*sum-j+1 not in d:
d[2*sum-j+1] = j
return m


It does not work on this input:

[1,0,0,1,1,0]-> output is 4 instead of 6


I think there might be some sort of indexing issue.

• You seem to have created multiple accounts. I encourage you to merge them: cs.stackexchange.com/help/merging-accounts. This will ensure you keep full access to your question.
– D.W.
Mar 18, 2021 at 22:50
• Coding and implementation questions are off-topic here. Debugging your code and tracking down indexing bugs are off-topic here. If you have a question about algorithms, I encourage you to replace the code with concise pseudocode. Please don't use code blocks (..) for indenting or emphasis; that can be hard to read. Can you tell us the context where you encountered this task, and credit the original source of all copied material?
– D.W.
Mar 18, 2021 at 22:51
• Your idea is sound, hence the problem must be with the implementation. The task will be less confusing if you switch from $0,1$ to $\pm 1$. Now you are looking for identical prefix sums. Mar 19, 2021 at 9:31