Find largest subarray with equal number of 1s and 0s
Given a boolean array with 1s and 0s, find the largest subarray with equal number of 1s and 0s.
Solution: O(n2) solution is trivial.
An O(n) solution is possible if we do the following:
Construct an array sumleft such that sumleft[k] provides the sum of elements from 0 to k.
While constructing sumleft[k], treat 0s as -1 so that sumleft[k] describes the inequality in the number of 1s and 0s from 0 to k.
Iterate once over the sumleft array and store each value in a
HashMap<Integer,Integer> sumToPositionIndexMap
When putting into the map, if same sum is seen again, do not update.
Get the index corresponding to it and diff with current index.
This gives one subarray with an equal number of 1s and 0s.
Choose the subarray with maximum length.
Got a thought to share or found a bug in the code? We'd love to hear from you:
