Given an array of 0s and 1s, find out:
1. all the
subarrays where number of 0s = number of 1s
2. max length subarrays where number of 0s = number of 1s
The array is not sorted and can be in any order. Can you do it in O(n) time?
The O(n^2) solution is easy to think of. use proprocessing and check every possible subarray.
But for the O(n) one, it's tricky. Here's one best solution
Loler has come up with.
Basically, use divide and conquer. if there's n subarrays that matches the requirement and you add 1 or 0 after that, how many you can get in total? That becomes straight forward. assume we keep the sum and add 1 if is 1, minus
1 if is 0.
eg. 1001, we have 3 subs that match the requirement, then 1001 1 has 4 subs. why? cause the sum becomes 1, and the it has appeared before only once. so it will be 3+1=4.
if not clear see the codes below.
Below is his explanation:
Assuming by subsequence you actually meant _subarray_, an O(n) time (expected) algorithm is possible.
Traverse the array from left to right, and maintain a running sum of number of ones - number of zeroes.
You also have a hashtable keyed on the running sum, and which contains information regarding the number of times that running sum appears,
and also the leftmost index for which that sum appears.
Using this structure, we can compute the answers for both 1 and 2.
For instance, to compute the number, we check if the running sum appeared before. If it appeared k times before, then we get k new sub-arrays
with equal number of zeroes and ones.
The max length uses the left most such idx.
Here is quick code in python
def equal_count(lst):
bits = [-1,1]
counts = {}
counts[0] = 1, -1
run_sum = 0
total_count = 0
max_len = 0
cur_idx = -1
for bit in lst:
cur_idx += 1
run_sum += bits[bit]
if run_sum in counts:
c, idx = counts[run_sum]
total_count += c
if cur_idx - idx > max_len:
max_len = cur_idx - idx
counts[run_sum] = c+1, idx
else:
counts[run_sum] = 1, cur_idx
return total_count, max_len
def main():
print equal_count([0,1,0,1,0,1])
if __name__ == "__main__":
main()