Make delicious recipes!

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:
  1. 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.
  2. Iterate once over the sumleft array and store each value in a HashMap<Integer,Integer> sumToPositionIndexMap
  3. 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.
  4. Choose the subarray with maximum length.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal