Example – [0,0,1,0,1,0,0]

Output – [0,1,0,1], [1,0,1,0] – length = 4

Approaches

  1. Naive O(n^3) – Traverse through each sub-arrays and check for number of 1s and 0s and find the maximum number of length.
  2. O(n) – Change all the 0s to -1 and check for the maximum length sub array with sum = 0 . (While traversing through the array maintain a hash map or dictionary to store sum as key and the ending index of sub array as the value. Check if (curr_sum) is present in the hash map and check for the length of the sub array from current index and index at (curr_sum). Return the sub_array with max length.)

LEAVE A REPLY