I have one more approach in mind where it requires T(n) = O(n) and
O(1) space complexity. here it goes:
1) Start traversing the array.
2)Store the location when 0 and 1 both appears for the first time in
some variable.
3)Similarly store the location of 0 and 1 when both appears for the
last time
@sunny: if a[i]==0 then 0,i is the solution
suppose a[i]==a[j] ==0 now 0,i and 0,j is the solution. is i,j also
the solution??
On Jul 1, 4:08 pm, sunny agrawal sunny816.i...@gmail.com wrote:
String = 1 0 1 1 0 1 1 1.
1. make the array = 1 -1 1 1 -1 1 1 1
2. after second operation
array = 1 0
yes but for largest interval we need only one index :) greater of i or j
On Fri, Jul 1, 2011 at 6:01 PM, Dumanshu duman...@gmail.com wrote:
@sunny: if a[i]==0 then 0,i is the solution
suppose a[i]==a[j] ==0 now 0,i and 0,j is the solution. is i,j also
the solution??
On Jul 1, 4:08 pm, sunny