CODEWITHSUNDEEP
algorithmdata-structuressegment-tree
efex09
efex09

Reputation: 419

Find the largest subarray with all ones

Given a binary array (element is 0 or 1), I need to find the maximum length of sub array having all ones for given range(l and r) in the array.

I know the O(n) approach to find such sub array but if there are O(n) queries the overall complexity becomes O(n^2).

I know that segment tree is used for such type of problems but I cant figure out how to build tree for this problem.

Can I build a segment tree using which I can answer queries in log(n) time such that for O(n) queries overall complexity will become O(nlog(n)).

Upvotes: 3

Views: 924

Answers (2)

merlyn
merlyn

Reputation: 2361

Yes, you can use a segment tree to solve this problem.

Let's try to think what that tree must look like. Obviously, every node must contain the length of max subarray of 1s and 0s in that range.

Now, how do we join two nodes into a bigger one. In other words, you have a node representing [low, mid) and a node representing [mid, high). You have to obtain max subarray for [low, high). First things first, max for whole will at least be max for parts. So we have to take the maximum among the left and right values.

But what if the real max subarray overlaps both nodes? Well, then it must be the rightmost part of left node and leftmost part of right node. So, we need to keep track of longest subarray at start and end as well.

Now, how to update these left and rightmost subarray lengths? Well, leftmost of parent node must be leftmost of left child, unless leftmost of left child spans the entire left node. In that case, leftmost of parent node will be leftmost of left + leftmost of right node.

A similar rule applies to tracking the rightmost subarray of 1s.

And we're finished. Here's the final rules in pseudo code.

max_sub[parent] = max(max_sub[left], max_sub[right], right_sub[left] + left_sub[right])
left_sub[parent] = left_sub[left] if left_sub[left] < length[left] else left_sub[left] + left_sub[right]
right_sub[parent] = right_sub[right] if right_sub[right] < length[right] else right_sub[right] + right_sub[left]

Note that you will need to take similar steps when finding the result for a range.

Here's an example tree for the array [0, 1, 1, 0, 1, 1, 1, 0].

An example tree

Upvotes: 1

Nelfeal
Nelfeal

Reputation: 13269

Let A be your binary array.
Build two array IL and IR:
- IL contains, in order, every i such that A[i] = 1 and (i = 0 or A[i-1] = 0);
- IR contains, in order, every i such that A[i-1] = 1 and (i = N or A[i] = 0).

In other words, for any i, the range defined by IL[i] inclusive and IR[i] non-inclusive corresponds to a sequence of 1s in A.

Now, for any query {L, R} (for the range [L; R] inclusive), let S = 0. Traverse both IL and IR with i, until IL[i] >= L. At this point, if IR[i-1] > L, set S = IR[i-1]-L. Continue traversing IL and IR, setting S = max(S, IR[i]-IL[i]), until IR[i] > R. Finally, if IL[i] <= R, set S = max(S, R-IL[i]).

S is now the size of the greatest sequence of 1s in A between L and R.

The complexity of building IL and IR is O(N), and the complexity of answering a query is O(M), with M the length of IL or IR.

Upvotes: 1

Related Questions