Largest subarray with equal number of 0s and 1s
You are given an array consisting of 0s and 1s. You need to find the length of the largest subarray with an equal number of 0s and 1s.

For example:

If the given array is: [0, 0, 1, 0, 1] The largest subarray would be: [0, 1, 0, 1] (last 4 elements) having length 4.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains a single integer N denoting the length of the array. The second line of each test case contains N space-separated integers representing the array elements.

Output Format:

For each test case, return the length of the largest subarray with the equal number of 0s and 1s, in a new line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 ≤ T ≤ 10 1 ≤ N ≤ 10^5 0 ≤ Ai ≤ 1 Time Limit : 1 sec

Question

Largest subarray with equal number of 0s and 1s

You are given an array consisting of 0s and 1s. You need to find the length of the largest subarray with an equal number of 0s and 1s.

For example:

If the given array is: [0, 0, 1, 0, 1] The largest subarray would be: [0, 1, 0, 1] (last 4 elements) having length 4.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of each test case contains a single integer N denoting the length of the array.

The second line of each test case contains N space-separated integers representing the array elements.

Output Format:

For each test case, return the length of the largest subarray with the equal number of 0s and 1s, in a new line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
0 ≤ Ai ≤ 1

Time Limit : 1 sec

Accepted Answer

Approach : I changed array entry for 0 to -1.
Then I took Prefix sum of array and then the problem changed to finding two index in array such that arr[i]=arr[j] and abs(j-i) is maximum.
Time Complexity : O(n) where n= number of elements in array.
Space Complexity : O(n)

Accepted Answer

Brute Force

We generate all the possible subarrays by using two nested loops.
We can run two nested loops, the outer loop picks the starting element and the inner loop picks the ending element.
The third loop considers all elements in between the starting and ending elements.
Check if each subarray has equal number of 0s and 1s
This can be easily done by considering 0 as -1 and 1 as 1 since the sum for equal numbers of 0s and 1s would be 0.
For all subarrays with equal numbers of 0s and 1s, we take the one with the largest length.

Space Complexity: O(1)Explanation:

O(1)

As there is no extra space required.

Time Complexity: O(n^3)Explanation:

O(N^3), where N is the size of the array.

Since there are three nested loops where we are iterating over all possible subarrays and considering all elements in the subarrays and checking if any of them have equal numbers of 1's and 0's and returning the one with the largest length. Therefore the time complexity here grows by order O(N^3).

Accepted Answer

Optimised Brute Force

We generate all the possible subarrays by using nested loops.
We can run two nested loops, the outer loop picks the starting element and the inner loop considers all elements on the right of the picked elements as the ending element of the subarray.
Check if each subarray has equal number of 0s and 1s
This can be easily done by considering 0 as -1 and 1 as 1 since the sum for equal numbers of 0s and 1s would be 0.
For all subarrays with equal numbers of 0s and 1s, we take the one with the largest length.

Space Complexity: O(1)Explanation:

O(1)

As there is no extra space required.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the size of the array.

Since we are iterating over the N elements in the array/list (all items) where we check the maximum sized sub-array that has equal numbers of 0s and 1s, therefore, the time complexity here grows by the order O(N^2).

Accepted Answer

Optimal Solution

For simplicity, consider 0 as -1 and 1 as 1 since the sum for equal numbers of 0s and 1s would be 0.
Store the cumulative sums in a hashmap. There can be two cases:
- When cumulative sum is 0: This means that the subarray from index 0 to the present index has equal number of 0s and 1s
- When cumulative sum is not equal to 0: This means that the subarray from the index which had this sum before to the present index has equal number of 0s and 1s
Note that you only need to store the first occurrence of each sum, since we need to find the largest subarray.

Space Complexity: O(n)Explanation:

O(N), where N is the size of the array.

Since using a hashmap would cost O(N)

Time Complexity: O(n)Explanation: