DEV Community

Piyush Baraskar
Piyush Baraskar

Posted on

Code and approach to solve Contiguous array problem

#programming #tutorial #python #dsa

image

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        arr2 = []
        for i in nums:
            if i == 0:
                arr2.append(-1)
            else :
                arr2.append(1)

        prefixsum = []
        total = 0

        for i in arr2:
            total += i
            prefixsum.append(total)

        hashmap = {0: -1}
        max_length = 0

        for i in range(len(prefixsum)):

            if prefixsum[i] in hashmap:
                length = i - hashmap[prefixsum[i]]
                max_length = max(max_length, length)

            else:
                hashmap[prefixsum[i]] = i

        return max_length
Enter fullscreen mode Exit fullscreen mode

PROBLEM-
so in the ques we have given a binary array and we have to return longest subarray of equal number of 0,1
like here

nums = [0,1,1,1,1,1,0,0,0]

the


 is the longest subarray the numbers are repeating like three ones and then three zeroes and it will return 6 cuz the total number of elements are six 

APPROACH -
so here we are first converting the 0 into -1 because it helps us to calculate the balanced subarray, because when the sum becomes 0 it means there are equal numbers of 0 and 1. like

 ```0,1```

 convert ->

 ```-1,1```

 -> sum = -1 + 1 = 0 -> length = 2

then we calc the prefixsum so we can store the prefixsum according to key value pairs in the hashmap
after that uses the hashmap

then we calc loop through prefix sum index
and if the element is present in hashmap it calc length from i- previous index
and update the max length

else remember its current index

# CODE EXPLAINATION

`nums = [0,1,1,1,1,1,0,0,0]`



```python
arr2 = []
Enter fullscreen mode Exit fullscreen mode

-> creating a blank array to store -1 and 1.

for i in nums:
    if i == 0:
        arr2.append(-1)
    else:
        arr2.append(1)
Enter fullscreen mode Exit fullscreen mode

-> loops through the nums. If element is 0, replace it with -1, otherwise keep it as 1. So arr2 becomes [-1,1,1,1,1,1,-1,-1,-1].

prefixsum = []
total = 0

for i in arr2:
    total += i
    prefixsum.append(total)
Enter fullscreen mode Exit fullscreen mode

-> calculating the prefixsum by adding each element to total and storing the result in prefixsum.

hashmap = {0: -1}
max_length = 0
Enter fullscreen mode Exit fullscreen mode

-> creating a hashmap where prefixsum is the key and its first index is the value. {0: -1} means prefixsum 0 was present before the array started.

for i in range(len(prefixsum)):
Enter fullscreen mode Exit fullscreen mode

-> looping through the prefixsum using its index and calclating the length = current index i - previous index i which is stored in hashmap

if prefixsum[i] in hashmap:
    length = i - hashmap[prefixsum[i]]
    max_length = max(max_length, length)
Enter fullscreen mode Exit fullscreen mode

-> if the current prefixsum is already in the hashmap, it means the sum between the previous index and current index is 0, so the number of 0s and 1s is equal. Then calculate the length and update the max_length.

else:
    hashmap[prefixsum[i]] = i
Enter fullscreen mode Exit fullscreen mode

-> if the prefixsum is not already in the hashmap, store its current index. We store only the first index because it gives the longest possible subarray.

return max_length
Enter fullscreen mode Exit fullscreen mode

-> returns the longest subarray length.

Top comments (0)