0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 18, 2021 at 22:50
  • 2
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Mar 18, 2021 at 22:51
  • $\begingroup$ 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. $\endgroup$ Mar 19, 2021 at 9:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.