Subarray with equal occurrences — Asked in Amazon Interview

Problem Statement :

You have been given an array/list ARR of length N consisting of 0s and 1s only. Your task is to find the number of subarrays(non-empty) in which the number of 0s and 1s are equal.

Sample Input:

7
1 0 0 1 0 1 1

Sample Output:

8

Explanation of Sample Test Case :

There are such 8 subarrays with index range [0, 1], [2, 3], [0, 3], [3, 4], [4, 5], [2, 5], [0, 5], [1, 6].

Approach :

CUMULATIVE SUM METHOD

If we consider every ‘0’ as -1, then a subarray containing equal 0s and 1s will give a sum of 0. So, we can use the cumulative sum to count these subarrays with sum 0 easily.

The idea is based on the fact that if a cumulative sum appears again in the array, then the subarray between these two occurrences of cumulative sum, will have a sum of 0.

For example-
Given ARR = [1, 1, 1, 0, 0, 1]

Cumulative Sum = [1, 2, 3, 2, 1, 2]

Here, one of the required subarrays has index range[1, 4]. We can see that 1 appears again in the cumulative sum at index 4 (previously at index 0). Hence, the subarray between index 0(exclusive) and index 4(inclusive) is one of the subarrays with equal 0s and 1s.

Here is the algorithm:

Time Complexity : O(N)
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.