Given an array of 0s and 1s. Find the length of the largest subarray with equal number of 0s and 1s.
Example 1:
Input:
N = 4
A[] = {0,1,0,1}
Output: 4
Explanation: The array from index [0...3]
contains equal number of 0's and 1's.
Thus maximum length of subarray having
equal number of 0's and 1's is 4.
Example 2:
Input:
N = 5
A[] = {0,0,1,0,0}
Output: 2
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxLen() which takes the array arr[] and the size of the array as inputs and returns the length of the largest subarray with equal number of 0s and 1s.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{5}
0 <= A[] <= 1

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3


# arr[] : the input array containing 0s and 1s
# N : size of the input array

# return the maximum length of the subarray
# with equal 0s and 1s
class Solution:
    def maxLen(self,arr, N):
        # code here

Solutions:
class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		s = 0
		a = 0
		d = {0: -1}
		for i in range(N):
			s = s + arr[i]
			if s not in d:
				d[s] = i
			elif i - d[s] > a:
				a = i - d[s]
		return a


class Solution:

	def maxLen(self, arr, N):
		sm = 0
		ans = 0
		hmap = {}
		(zeroes, ones) = (0, 0)
		for i in range(n):
			if arr[i] == 0:
				zeroes += 1
			else:
				ones += 1
			diff = ones - zeroes
			if diff == 0:
				ans = i + 1
			if diff in hmap:
				ans = max(ans, i - hmap[diff])
			else:
				hmap[diff] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		for i in range(0, N):
			if arr[i] == 0:
				arr[i] = -1
		sum = 0
		max = 0
		di = {}
		for i in range(0, N):
			sum += arr[i]
			if sum in di.keys():
				if max > i - di[sum]:
					max = max
				else:
					max = i - di[sum]
			elif sum == 0:
				max = i + 1
			else:
				di[sum] = i
		return max


class Solution:

	def maxLen(self, arr, N):
		ans = 0
		total = 0
		d = dict()
		for i in range(N):
			x = -1 if arr[i] == 0 else 1
			total += x
			if total == 0:
				ans = max(ans, i + 1)
			elif total in d:
				ans = max(ans, i - d[total])
			else:
				d[total] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		Hash = {0: -1}
		total_sum = 0
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		pre_sum = 0
		res = 0
		for i in range(N):
			pre_sum += arr[i]
			if pre_sum in Hash:
				res = max(res, i - Hash[pre_sum])
			else:
				Hash[pre_sum] = i
		return res


class Solution:

	def maxLen(self, arr, N):
		d = {}
		(ans, psum) = (0, 0)
		for i in range(len(arr)):
			if arr[i] == 0:
				psum -= 1
			else:
				psum += 1
			if psum == 0:
				ans = i + 1
			if psum in d:
				ans = max(ans, i - d[psum])
			else:
				d[psum] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		m = {0: -1}
		c = 0
		maxi = 0
		for i in range(N):
			if arr[i] == 0:
				c -= 1
			else:
				c += 1
			if c in m:
				maxi = max(maxi, i - m[c])
			else:
				m[c] = i
		return maxi


class Solution:

	def maxLen(self, arr, N):
		freq = {0: -1}
		ans = 0
		ind = 0
		summ = 0
		for i in range(N):
			if arr[i] == 0:
				summ = summ - 1
			else:
				summ += 1
			if summ in freq:
				ind = freq.get(summ)
				ans = max(ans, abs(ind - i))
			else:
				freq[summ] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		ans = 0
		summ = 0
		dic = dict()
		for i in range(N):
			if arr[i] == 0:
				summ -= 1
			else:
				summ += 1
			if summ == 0:
				ans = max(ans, i + 1)
			if summ in dic:
				ans = max(ans, i - dic[summ])
			else:
				dic[summ] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		d = {0: -1}
		s = 0
		m = 0
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		for i in range(N):
			s += arr[i]
			if s in d:
				m = max(m, abs(i - d[s]))
			else:
				d[s] = i
		return m


import math

class Solution:

	def maxLen(self, arr, N):
		maxi = -math.inf
		if arr[0] == 0:
			arr[0] = -1
		for i in range(1, N):
			if arr[i] == 0:
				arr[i] = -1
			arr[i] += arr[i - 1]
		dicti = {}
		for i in range(N):
			if arr[i] == 0:
				maxi = max(maxi, i + 1)
			if arr[i] not in dicti:
				dicti[arr[i]] = i
			else:
				maxi = max(i - dicti[arr[i]], maxi)
		if maxi < 0:
			return 0
		return maxi


class Solution:

	def maxLen(self, arr, N):
		d = {0: -1}
		index = 0
		sumi = 0
		ans = 0
		for i in range(N):
			if arr[i] == 0:
				sumi = sumi - 1
			else:
				sumi = sumi + 1
			if sumi not in d:
				d[sumi] = i
			else:
				index = d.get(sumi)
				ans = max(ans, abs(index - i))
		return ans


class Solution:

	def maxLen(self, arr, N):
		maxi = 0
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		prefixsum = 0
		dit = {0: -1}
		for (i, val) in enumerate(arr):
			prefixsum += val
			if prefixsum in dit:
				maxi = max(maxi, i - dit[prefixsum])
			else:
				dit[prefixsum] = i
		return maxi


class Solution:

	def maxLen(self, arr, N):
		d = {0: -1}
		index = 0
		sum = 0
		max_len = 0
		for i in range(N):
			if arr[i] == 0:
				sum += -1
			else:
				sum += arr[i]
			if sum in d:
				index = d.get(sum)
				max_len = max(max_len, abs(i - index))
			else:
				d[sum] = i
		return max_len


class Solution:

	def maxLen(self, arr, N):
		count = 0
		max1 = 0
		dic = {0: -1}
		for (i, j) in enumerate(arr):
			if j == 0:
				count -= 1
			else:
				count += 1
			if count in dic:
				max1 = max(max1, i - dic[count])
			else:
				dic[count] = i
		return max1


class Solution:

	def maxLen(self, arr, N):
		map = dict()
		map[0] = -1
		cursum = 0
		maxlen = 0
		for i in range(len(arr)):
			if arr[i] == 0:
				cursum -= 1
			else:
				cursum += 1
			if cursum in map:
				maxlen = max(maxlen, i - map.get(cursum))
			else:
				map[cursum] = i
		return maxlen


class Solution:

	def maxLen(self, arr, n):
		maxlen = 0
		cur_sum = 0
		dic = dict()
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		for i in range(n):
			cur_sum += arr[i]
			if cur_sum == 0:
				maxlen = i + 1
			if cur_sum in dic:
				if i - dic[cur_sum] > maxlen:
					maxlen = i - dic[cur_sum]
			else:
				dic[cur_sum] = i
		return maxlen


class Solution:

	def maxLen(self, arr, N):
		max_len = 0
		count = 0
		hmap = {0: -1}
		for i in range(N):
			if arr[i] == 1:
				count += 1
			else:
				count -= 1
			if count in hmap:
				max_len = max(max_len, i - hmap[count])
			else:
				hmap[count] = i
		return max_len


class Solution:

	def maxLen(self, arr, N):
		count = 0
		map = {0: -1}
		max_length = 0
		for i in range(N):
			if arr[i] == 1:
				count += 1
			else:
				count -= 1
			if count in map:
				max_length = max(max_length, i - map[count])
			else:
				map[count] = i
		return max_length


class Solution:

	def maxLen(self, arr, N):
		dic = {}
		s = 0
		ans = 0
		end = -1
		for i in range(N):
			if arr[i] == 0:
				temp = -1
			else:
				temp = 1
			s += temp
			if s == 0:
				ans = i + 1
				end = i
			if s in dic:
				ans = max(ans, i - dic[s])
				end = i
			else:
				dic[s] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		cnt = {}
		current_sum = 0
		max_range = 0
		for i in range(N):
			current_sum += arr[i]
			if current_sum == 0:
				max_range = i + 1
			if current_sum in cnt:
				max_range = max(max_range, i - cnt[current_sum])
			else:
				cnt[current_sum] = i
		arr = [0 if arr[i] == -1 else 1 for i in range(N)]
		return max_range


from collections import defaultdict

class Solution:

	def maxLen(self, arr, N):
		cur = 0
		res = 0
		a = {0: -1}
		for i in range(N):
			cur += -1 if arr[i] == 0 else 1
			if cur not in a:
				a[cur] = i
			else:
				res = max(res, i - a[cur])
		return res


class Solution:

	def maxLen(self, arr, N):
		hash_map = {}
		curr_sum = 0
		max_len = 0
		ending_index = -1
		for i in range(0, N):
			if arr[i] == 0:
				arr[i] = -1
			else:
				arr[i] = 1
		for i in range(0, N):
			curr_sum = curr_sum + arr[i]
			if curr_sum == 0:
				max_len = i + 1
				ending_index = i
			if curr_sum in hash_map:
				if max_len < i - hash_map[curr_sum]:
					max_len = i - hash_map[curr_sum]
					ending_index = i
			else:
				hash_map[curr_sum] = i
		for i in range(0, N):
			if arr[i] == -1:
				arr[i] = 0
			else:
				arr[i] = 1
		return max_len


class Solution:

	def maxLen(self, arr, n):
		s = [0] * len(arr)
		if arr[0] == 0:
			s[0] = -1
		else:
			s[0] = 1
		for i in range(1, len(s)):
			if arr[i] == 0:
				s[i] = s[i - 1] - 1
			else:
				s[i] = s[i - 1] + 1
		d = dict()
		mx_len = 0
		i = 0
		for j in s:
			if j == 0:
				mx_len = max(mx_len, i + 1)
			if d.get(j) != None:
				mx_len = max(mx_len, i - d[j])
			else:
				d[j] = i
			i = i + 1
		return mx_len


class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		mem = dict()
		summ = l = maxi = 0
		for i in range(N):
			summ += arr[i]
			if summ == 0:
				maxi = max(i + 1, maxi)
			elif summ in mem:
				l = i - mem[summ]
				maxi = max(l, maxi)
			else:
				mem[summ] = i
		return maxi


class Solution:

	def maxLen(self, arr, N):
		ar = []
		for i in arr:
			if i == 0:
				ar.append(-1)
			else:
				ar.append(1)
		mem = dict()
		s = l = m = 0
		for i in range(len(ar)):
			s += ar[i]
			if s == 0:
				m = max(i + 1, m)
			elif s in mem:
				l = i - mem[s]
				m = max(l, m)
			else:
				mem[s] = i
		return m


class Solution:

	def maxLen(self, arr, N):
		dictionary = dict()
		ans = 0
		if N == 0:
			return 0
		elif arr[0] == 0:
			arr[0] = -1
		else:
			arr[0] = 1
		dictionary[0] = -1
		for i in range(1, N):
			if arr[i] == 0:
				arr[i] = arr[i - 1] - 1
			else:
				arr[i] = arr[i - 1] + arr[i]
		for i in range(0, N):
			if arr[i] in dictionary.keys():
				if ans < i - dictionary[arr[i]]:
					ans = i - dictionary[arr[i]]
			else:
				dictionary[arr[i]] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		res = 0
		prefsum = 0
		d = {}
		for i in range(n):
			prefsum += arr[i]
			if prefsum == 0:
				res = i + 1
			if prefsum not in d:
				d[prefsum] = i
			else:
				res = max(res, i - d[prefsum])
		return res


class Solution:

	def maxLen(self, arr, N):
		cache = {0: -1}
		one = 0
		zero = 0
		max_ = 0
		for (i, num) in enumerate(arr):
			if num == 1:
				one += 1
			else:
				zero += 1
			diff = one - zero
			if diff in cache:
				max_ = max(max_, i - cache[diff])
			if diff not in cache:
				cache[diff] = i
		return max_


class Solution:

	def maxLen(self, arr, N):
		d = {}
		s = 0
		m = 0
		for a in range(N):
			if arr[a] == 0:
				s -= 1
			else:
				s += 1
			if s != 0 and s not in d:
				d[s] = a
				continue
			if s in d:
				m = max(m, a - d[s])
			if s == 0:
				m = max(m, a + 1)
		return m


class Solution:

	def maxLen(self, arr, N):
		(res, ones, zeros) = (0, 0, 0)
		dic = {}
		for i in range(0, N):
			if arr[i] == 0:
				zeros = zeros + 1
			else:
				ones = ones + 1
			diff = zeros - ones
			if diff == 0:
				res = i + 1
			if diff not in dic.keys():
				dic[diff] = i
			if diff in dic.keys():
				res = max(res, i - dic[diff])
		return res


class Solution:

	def maxLen(self, arr, N):
		arr = [-1 if not num else 1 for num in arr]
		res = cursum = 0
		d = {0: -1}
		for (i, num) in enumerate(arr):
			cursum += num
			if cursum in d:
				res = max(res, i - d[cursum])
			else:
				d[cursum] = i
		return res


class Solution:

	def maxLen(self, nums, N):
		nums = [-1 if val == 0 else val for val in nums]
		total = 0
		res = 0
		d = {}
		for i in range(len(nums)):
			total += nums[i]
			if total == 0:
				res = max(res, i + 1)
			elif total in d:
				res = max(res, i - d[total])
			else:
				d[total] = i
		return res


class Solution:

	def maxLen(self, a, n):
		for i in range(n):
			if a[i] == 0:
				a[i] = -1
		max_l = 0
		t = 0
		h = {}
		for i in range(n):
			t = t + a[i]
			if t == 0:
				max_l = max(max_l, i + 1)
			if t in h:
				max_l = max(max_l, i - h[t])
			else:
				h[t] = i
		return max_l


class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		(ans, j, s) = (0, 0, 0)
		d = {}
		for i in range(N):
			s += arr[i]
			if s == 0:
				ans = max(ans, i + 1)
			if s in d:
				ans = max(ans, i - d[s])
			else:
				d[s] = i
		return ans


class Solution:

	def maxLen(self, arr, n):
		temp = []
		for a in arr:
			if a == 0:
				temp.append(-1)
			else:
				temp.append(1)
		for i in range(1, n):
			temp[i] += temp[i - 1]
		ha = {}
		ha[0] = -1
		ans = 0
		for i in range(n):
			if temp[i] == 0:
				ans = max(ans, i + 1)
			elif temp[i] in ha.keys():
				ans = max(ans, i - ha[temp[i]])
			else:
				ha[temp[i]] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		maxi = -99999
		d = {}
		s = 0
		for i in range(N):
			if arr[i] == 0:
				s += -1
			else:
				s += 1
			if s == 0:
				if maxi < i + 1:
					maxi = i + 1
			elif s not in d.keys():
				d[s] = i
			elif i - d[s] > maxi:
				maxi = i - d[s]
		if maxi == -99999:
			return 0
		return maxi


class Solution:

	def maxLen(self, arr, N):
		prefix_dict = {}
		ans = 0
		max_length = 0
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		for (i, val) in enumerate(arr):
			ans += val
			if ans == 0:
				max_length = i + 1
			elif ans in prefix_dict:
				max_length = max(max_length, i - prefix_dict[ans])
			else:
				prefix_dict[ans] = i
		return max_length


class Solution:

	def maxLen(self, arr, N):
		data = [0 for i in range(N + 1)]
		d_min_max = {0: [0, 0]}
		for i in range(N):
			data[i + 1] = data[i] + (arr[i] == 1) * 1 - (arr[i] == 0)
			if data[i + 1] not in d_min_max:
				d_min_max[data[i + 1]] = [i + 1, i + 1]
			else:
				d_min_max[data[i + 1]][1] = i + 1
		res = 0
		for i in d_min_max:
			res = max(res, d_min_max[i][1] - d_min_max[i][0])
		return res


class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		l = 0
		r = 0
		s = 0
		diff = 0
		d = dict()
		for i in range(N):
			s += arr[i]
			if s == 0 and diff < i + 1:
				l = 0
				r = i
				diff = i + 1
			if d.get(s) == None:
				d[s] = i + 1
			elif i - d[s] > diff:
				l = d.get(s)
				r = i
				diff = r - l + 1
		return diff


class Solution:

	def maxLen(self, arr, N):
		r = 0
		dic = {0: -1}
		sum = 0
		maxi = 0
		while r < N:
			if arr[r] == 0:
				sum = sum - 1
			else:
				sum = sum + 1
			if sum not in dic:
				dic[sum] = r
			else:
				maxi = max(maxi, r - dic[sum])
			r = r + 1
		return maxi


class Solution:

	def maxLen(self, arr, N):
		sum1 = 0
		ans = 0
		d = dict()
		for i in range(N):
			if arr[i] == 0:
				sum1 = sum1 - 1
			else:
				sum1 = sum1 + 1
			if sum1 == 0:
				ans = max(ans, i + 1)
			if sum1 not in d:
				d[sum1] = i
			else:
				ans = max(ans, i - d[sum1])
		return ans


class Solution:

	def maxLen(self, a, n):
		d = {}
		d[0] = -1
		ans = 0
		sum = 0
		for i in range(n):
			if a[i] == 0:
				a[i] = -1
			sum += a[i]
			if sum in d:
				ans = max(ans, i - d[sum])
			else:
				d[sum] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		mp = dict({0: -1})
		count = 0
		res = 0
		for x in range(len(arr)):
			val = arr[x]
			if val == 1:
				count += 1
			else:
				count -= 1
			if count in mp:
				res = max(res, x - mp[count])
			else:
				mp[count] = x
		return res


class Solution:

	def maxLen(cls, input1, input2):
		s = [0] * len(input1)
		if input1[0] == 0:
			s[0] = -1
		else:
			s[0] = 1
		for i in range(1, len(s)):
			if input1[i] == 0:
				s[i] = s[i - 1] - 1
			else:
				s[i] = s[i - 1] + 1
		d = dict()
		mx_len = 0
		i = 0
		for j in s:
			if j == 0:
				mx_len = max(mx_len, i + 1)
			if d.get(j) != None:
				mx_len = max(mx_len, i - d[j])
			else:
				d[j] = i
			i = i + 1
		return mx_len


class Solution:

	def maxLen(self, arr, N):
		firstOccurence = {}
		ans = 0
		sum = 0
		for i in range(N):
			if arr[i] == 0:
				sum += -1
			else:
				sum += arr[i]
			if sum == 0:
				ans = i + 1
			elif sum in firstOccurence:
				ans = max(ans, i - firstOccurence[sum])
			else:
				firstOccurence[sum] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		maximum = 0
		currentSum = 0
		memo = {0: -1}
		for i in range(0, N):
			if arr[i] is 0:
				currentSum -= 1
			else:
				currentSum += 1
			if currentSum in memo:
				maximum = max(maximum, i - memo[currentSum])
			else:
				memo[currentSum] = i
		return maximum


import collections

class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		total = 0
		hash_map = {}
		max_len = 0
		for i in range(N):
			total += arr[i]
			if total == 0:
				max_len = i + 1
			elif total in hash_map:
				if max_len < i - hash_map[total]:
					max_len = i - hash_map[total]
			else:
				hash_map[total] = i
		return max_len


class Solution:

	def maxLen(self, arr, N):
		hashmap = {}
		maxSubarraySize = 0
		currentSum = 0
		currentSubarraySize = 0
		for i in range(N):
			if arr[i] == 1:
				currentSum += 1
			else:
				currentSum -= 1
			if currentSum not in hashmap:
				hashmap[currentSum] = i
			if currentSum == 0:
				currentSubarraySize = i + 1
				maxSubarraySize = max(maxSubarraySize, currentSubarraySize)
			else:
				currentSubarraySize = i - hashmap[currentSum]
				maxSubarraySize = max(maxSubarraySize, currentSubarraySize)
		return maxSubarraySize


class Solution:

	def maxLen(self, arr, N):
		(l, n) = (arr, N)
		for i in range(n):
			if l[i] == 0:
				l[i] = -1
		d = {}
		res = p_s = k = 0
		for i in range(n):
			p_s += l[i]
			if p_s == k:
				res = i + 1
			if p_s not in d:
				d[p_s] = i
			if p_s - k in d:
				res = max(res, i - d[p_s - k])
		return res


class Solution:

	def maxLen(self, arr, N):
		hashtable = {0: -1}
		prefixsum = 0
		ans = 0
		for i in range(N):
			if arr[i]:
				prefixsum += 1
			else:
				prefixsum -= 1
			if prefixsum in hashtable:
				ans = max(ans, i - hashtable[prefixsum])
			else:
				hashtable[prefixsum] = i
		return ans


class Solution:

	def maxLen(self, arr, n):
		d = {}
		prefix_sum = 0
		count = 0
		d[0] = -1
		for i in range(n):
			if arr[i] == 0:
				prefix_sum -= 1
			else:
				prefix_sum += 1
			if prefix_sum not in d:
				d[prefix_sum] = i
			else:
				cur_count = i - d[prefix_sum]
				if cur_count > count:
					count = cur_count
		return count


class Solution:

	def maxLen(self, arr, N):
		memo = {}
		prefixSum = 0
		ans = 0
		memo[prefixSum] = -1
		for i in range(N):
			if arr[i] == 0:
				prefixSum += -1
			else:
				prefixSum += 1
			if prefixSum in memo:
				temp = i - memo[prefixSum]
				ans = max(ans, temp)
			else:
				memo[prefixSum] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		s = {}
		cur = 0
		s[0] = -1
		m = 0
		for i in range(N):
			cur += arr[i]
			if cur not in s:
				s[cur] = i
			else:
				m = max(m, i - s[cur])
		return m


class Solution:

	def maxLen(self, arr, N):
		curr_sum = 0
		max_len = 0
		dct = {}
		for i in range(N):
			if arr[i]:
				curr_sum += 1
			else:
				curr_sum -= 1
			if curr_sum == 0:
				max_len = i + 1
			if curr_sum in dct:
				max_len = max(max_len, i - dct[curr_sum])
			else:
				dct[curr_sum] = i
		return max_len


class Solution:

	def maxLen(self, arr, N):
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
		cs = 0
		h = {}
		ml = 0
		for i in range(N):
			cs += arr[i]
			if cs == 0:
				ml = max(i + 1, ml)
			if cs in h:
				ml = max(i - h[cs], ml)
			else:
				h[cs] = i
		return ml


class Solution:

	def maxLen(self, arr, n):
		ans = 0
		currS = 0
		dic = {0: -1}
		for i in range(n):
			if arr[i] == 0:
				currS -= 1
			else:
				currS += 1
			if currS not in dic:
				dic[currS] = i
			else:
				ans = max(ans, i - dic[currS])
		return ans


class Solution:

	def maxLen(self, arr, N):
		mp = {0: -1}
		s = 0
		res = 0
		for i in range(N):
			if arr[i] == 0:
				s -= 1
			else:
				s += 1
			if s in mp:
				res = max(res, abs(mp[s] - i))
			else:
				mp[s] = i
		return res


class Solution:

	def maxLen(self, arr, N):
		cs = 0
		m = 0
		d = {0: -1}
		for i in range(len(arr)):
			if arr[i] == 0:
				cs = cs - 1
			else:
				cs = cs + 1
			if cs in d:
				m = max(m, i - d[cs])
			else:
				d[cs] = i
		return m


from collections import defaultdict

class Solution:

	def maxLen(self, arr, N):
		cursum = 0
		res = 0
		a = {0: -1}
		for (i, x) in enumerate(arr):
			cursum += -1 if x == 0 else 1
			if cursum in a:
				res = max(res, i - a[cursum])
			else:
				a[cursum] = i
		return res


class Solution:

	def maxLen(self, arr, N):
		mydict = {0: -1}
		mysum = 0
		maxlen = 0
		for i in range(N):
			if arr[i] == 0:
				mysum -= 1
			else:
				mysum += 1
			if mysum not in mydict:
				mydict[mysum] = i
			else:
				maxlen = max(maxlen, i - mydict[mysum])
		return maxlen


class Solution:

	def maxLen(self, arr, N):
		counts = {}
		counts[0] = -1
		count = 0
		maxi = 0
		for i in range(N):
			count += arr[i]
			count -= not arr[i]
			if count in counts:
				maxi = max(maxi, i - counts[count])
			else:
				counts[count] = i
		return maxi


class Solution:

	def maxLen(self, arr, N):
		dict = {}
		curr_sum = 0
		largest_sum = 0
		s_z = 0
		s_r = 0
		for i in range(N):
			if arr[i] == 0:
				arr[i] = -1
			curr_sum += arr[i]
			if curr_sum == 0:
				s_z = i + 1
				if largest_sum < s_z:
					largest_sum = s_z
			elif curr_sum not in dict:
				dict[curr_sum] = i
			else:
				s_r = i - dict[curr_sum]
				if largest_sum < s_r:
					largest_sum = s_r
		return largest_sum


class Solution:

	def maxLen(self, nums, N):
		for i in range(len(nums)):
			if nums[i] == 0:
				nums[i] = -1
		d = {}
		d[0] = -1
		ans = 0
		ps = 0
		for i in range(len(nums)):
			ps += nums[i]
			if ps in d:
				ans = max(ans, i - d[ps])
			else:
				d[ps] = i
		return ans


class Solution:

	def maxLen(self, arr, N):
		prefixsum = 0
		answer = 0
		memo = {}
		memo[prefixsum] = -1
		for i in range(N):
			currentval = arr[i]
			if currentval == 0:
				prefixsum += -1
			else:
				prefixsum += 1
			if prefixsum in memo:
				temp = i - memo[prefixsum]
				answer = max(answer, temp)
			else:
				memo[prefixsum] = i
		return answer