Given an array of 0's and 1's. only, find the maximum length of the subarray such that the number of 0's and 1's in that subarray are equal.

Subscribe to:
Post Comments
(
Atom
)

change 0 to -1 on the original array. now define S[i] = a[1] + ... + a[i] (a being the input)

ReplyDeleteyou want to find indices i and j such that a[i]+...+a[j] = 0

that is the same as

S[j]-S[i-1] = 0

S[j] = S[i-1]

now you can hash these values (they range from -n to n, so you can do this in O(n) memory)and find the indices in O(n).

Excellent :)

Deletein order to find the maximum j-i, you can keep a max hash with the index of the max and a min hash. now find the largest difference subtracting.

ReplyDelete@imavalon ... there is a small catch

ReplyDeleteif(s[0] - a[0] == s[n-1]) len = n;

this is the case when the max subarray is the whole array ....

further there is no need of hash map .... u can take an array of size 2n+1 ... and store the first index containing the value seen and compute difference whenever u see the value again ..

Regards

find the subarray whose sum is the half of the size of the subarray

ReplyDelete@vivek ... and how will you do that ... ?? (remember you need to consider all the possible subarrays )

ReplyDeleteRegards

A linear sweep through the array would do it.

ReplyDelete1. XOR neighbors, maintain two counters;

2. if (XOR result is 0 AND a[i] is 0)

increment zeroCount;

else if (XOR result is 0 AND a[i] is 1)

increment oneCount;

3. return min(zeroCount, oneCount);

Sweep through the input maintaining the zero-one balance information.

ReplyDeleteBalance is defined as follows:

balance = 0 (initialization)

If we find a '1' in the input increment by 1, else decrement by 1(we found a zero).

balance = 0;

max_length = 0;

for(int i=0; i<input(length); i++) {

if (input[i] == 1)

balance = balance + 1;

else

balance = balance - 1;

if(balance ==0) {

max_length++;

}

}

max_length has the answer.

@dayadru .... ur solution only consider the case in which subarray starts at position 0.

ReplyDeleteRegards