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.
..
) 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? $\endgroup$