We solve this using segment tree.
http://codepad.org/5jVxLmsA
On Sat, Jun 26, 2010 at 1:38 PM, Amit Jaspal wrote:
> Srry i wrote wrongly i will store C[i] if C[i]-K is not found in BST.if
> found there is a sub array..
> So now dry run...
> C[]=6,-1,7.
> K=7.
> And Yeah we will have to build a
Srry i wrote wrongly i will store C[i] if C[i]-K is not found in BST.if
found there is a sub array..
So now dry run...
C[]=6,-1,7.
K=7.
And Yeah we will have to build a balanced BST for sure..
On Sun, Jun 27, 2010 at 1:57 AM, Dhritiman Das wrote:
>
> @amit: Need to store indices also in the tree
@amit: Need to store indices also in the tree.
Did you mean a "self-balancing" BST, like AVL or RB-Tree.
Else worst case is O(n^2) for all positive numbers
On Jun 25, 2:55 am, Amir hossein Shahriari
wrote:
> @divya: yes you're right my algo doesn't work for negative values
>
> @amit