CODEWITHSUNDEEP
pythonalgorithmdynamic-programming
newBike
newBike

Reputation: 14992

DP solution to find the maximum length of a contiguous subarray with equal number of 0 and 1

The question is from here https://leetcode.com/problems/contiguous-array/

Actually, I came up with a DP solution for this question. However, It won't pass one test case.

Any thought?

DP[i][j] ==1 meaning from substring[i] to substring[j] is valid

Divide the question into smaller

DP[i][j]==1

- if DP[i+2][j]==1 and DP[i][i+1]==1
- else if DP[i][j-2]==1 and DP[j-1][j]==1
- else if num[i],num[j] == set([0,1]) and DP[i+1][j-1]==1

``` current_max_len = 0 if not nums: return current_max_len

    dp = [] * len(nums)
    for _ in range(len(nums)):
        dp.append([None] * len(nums))

    for thisLen in range(2, len(nums)+1, 2):
        for i in range(len(nums)):
            last_index = i + thisLen -1
            if i + thisLen > len(nums):
                continue

            if thisLen==2:
                if set(nums[i:i+2]) == set([0, 1]):
                    dp[i][last_index] = 1
            elif dp[i][last_index-2] and dp[last_index-1][last_index]:
                dp[i][last_index] = 1
            elif dp[i][i + 1] and dp[i + 2][last_index]:
                dp[i][last_index] = 1
            elif dp[i + 1][last_index-1] and set([nums[i], nums[last_index]]) == set([0, 1]):
                dp[i][last_index] = 1
            else:
                dp[i][last_index] = 0
            if dp[i][last_index] == 1:
                current_max_len = max(current_max_len, thisLen)

    return current_max_len

```

enter image description here

Upvotes: 0

Views: 834

Answers (3)

BishalG
BishalG

Reputation: 1424

Since given length of binary string may be at most 50000. So, running O(n * n) algorithm may lead to time limit exceed. I would like to suggest you to solve it in O(n) time and space complexity. The idea is :

  • If we take any valid contiguous sub-sequence and perform summation of numbers treating 0 as -1 then, total summation should be zero always.
  • If we keep track of prefix summation then we can get zero summation in the range L to R, if prefix summation up to L - 1 and prefix summation up to R are equal.
  • Since we are looking for maximum length, we will always treat index of newly found summation as a first one and put it into hash map with value as current index and which will persist forever for that particular summation.
  • Every time we calculate cumulative summation, we look whether it has any previous occurrence. If it has previous occurrence we calculate length and try to maximize , otherwise it will be the first one and will persist forever in hash map with value as current index.
  • Note: To calculate pure prefix, we must treat summation 0 is already in map and paired with value -1 as index.

The sample code in C++ is as follow:

int findMaxLength(vector<int>& nums) {
    unordered_map<int,int>lastIndex;
    lastIndex[0] = -1;
    int cumulativeSum = 0;
    int maxLen = 0;
    for (int i = 0; i < nums.size(); ++i) {
        cumulativeSum += (nums[i] == 0 ? -1 : 1);
        if (lastIndex.find(cumulativeSum) != lastIndex.end()) {
            maxLen = max(maxLen, i - lastIndex[cumulativeSum]);
        } else {
            lastIndex[cumulativeSum] = i;
        }
    }
    return maxLen;
}

Upvotes: 0

sahasrara62
sahasrara62

Reputation: 11228

here is python code 

def func( nums):       
    track,has=0,{0:-1}
    length=len(nums);
    ress_max=0;

    for i in range(0,length):
        track += (1 if nums[i]==1 else -1)
        if  track not in has:
            has[track]=i
        elif ress_max <i-has[track]:
            ress_max = i-has[track]
    return ress_max

l = list(map(int,input().strip().split()))
print(func(l))

Upvotes: 0

m7mdbadawy
m7mdbadawy

Reputation: 920

Here is a counter example [1, 1, 0, 0, 0, 0, 1, 1]. The problem with you solution that it requires a list to be composed of smaller valid lists of size n-1 or n-2 in this counter example it's two lists of length 4 or n-2 . -- SPOILER ALERT -- You can solve the problem by using other dp technique basically for every i,j you can find the number of ones and zeroes between them in constant time to do that just store the number of ones from the start of the list to every index i

Upvotes: 1

Related Questions