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.

Improve this question
$\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$
    – Yuval Filmus
    Mar 19, 2021 at 9:31

0

Reset to default

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.