You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space algorithm to find the maximum sub sequence which has equal number of 1s and 0s.
Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself
2)1101000
The longest sub sequence that satisfies the problem is 110100
Solution:
1. Worst case algorithm is to list all possible sub sequences and then find the one which is maximum.
2. Take another array which contains the sum of numbers of the orig array
new[i] = orig[0]+...orig[i];
Now we have to find out the sum of each subarray. If the sum of the subarray is half the number of element in the subarray, then check if this subarray can replace the previous maximum. If it can we will replace the current max with this subarray.
Each subarray sum can be found using the following formula
Sum of all elements from j till i = sum[i, j] = new[i] - new[j-1]
9 comments:
hi,
I have a doubt whether this algo is O(n)...since the no of subarrays will be n^2(for each outer j(1 to n), i varies from 1 to j-1)...correct me if im wrong.
yes.. you are right..
If we consider 1 as '(' and 0 as ')'. this question can be mapped as saying find the longest sequence of valid parenthised pairs, isnt it?
Also can we make use of some stack based approach so as to make more efficient ...
@ranga i think your approach wont work. braces have a ordering. in this case we dont have any.
Yep missed that! Thanks sir.
You highlighted 'sub sequence' and solved sub array!
Sub sequences are not contiguous.
Just count the number of zeroes and number of ones and find the minimum of these two values(say x).
Now out put a string with x 0s' and x 1s'.
Let original sequence be A of size "n".
Create another auxiliary array
B of size "n+1" which consists of pairs of numbers. The first number is difference between ( no of 1's - no of 0's) at position i of A. The second number of the pair is (i+1). This will be stored at position i+1 in array B.
E.g.
A = 1010001101
B = (0,0)(1,1)(0,2)(1,3)(0,4)(-1,5)(-2,6)(-1,7)(0,8)(-1,9)(0,10)
Now sort the array B lexicographically. We have.
B = (-2,6)(-1,5)(-1,7)(-1,9)(0,0)(0,2)(0,4)(0,8)(0,10)(1,1)(1,3)
All those numbers whose 1st numbers are same in sorted B would give us a potential answer. Now we only have to find that pair which is farthest.
For e.g. (0,0) and (0,8) ==> from position 1 to position 8 of array A forms a balanced sequence of 0's and 1's. But the longest one is (0,0) to (0,10) i.e full sequence is balanced.
O(n*log(n))
The problem says O(1) space and you choose a new array :O
In Dinesh dharme's solution, use map with values >, as most of the differences are repeating, it saves more space and its o(n)
Post a Comment