>
> I have one more question here , suppose we have some dynamic array
>> ( of const size ) where insertions and removal is happening
>> dynamically --->
>> you want the 2 elements from the array having least difference. Design
>> a data structure for this. Less than O(n) solution appreciated.
>>
>
Thanks Amit and srikanth for pointing that out. I should have done
some analysis before posting this solution.
we can do this problem in 2 steps:
find-min-diff(arr a)
{
sort(a)
find(a, 0, min=INF, i=0, j=0)
return {min, i, j}
}
find(a, index, min, i, j)
{
if(a[index+1] - a[index] < mi
count sort and then find mindiff
fot (int i=1;i wrote:
> Construct a BST for the array - O(nlogn)
> Traverse the tree and find a node which has
> minimum difference with either its left or
> right child in whole of the tree.
> (Because the required numbers have to be
> adjacent to each other in a
Construct a BST for the array - O(nlogn)
Traverse the tree and find a node which has
minimum difference with either its left or
right child in whole of the tree.
(Because the required numbers have to be
adjacent to each other in a sorted array). - O(n)
=> Total order:O(nlogn)
--
You received thi
Vikas,
Consider the following case
2 5 16 17 20 25;
Neither two max nor two min will give the minimum difference.
On Tue, Jul 13, 2010 at 9:52 AM, vikas kumar wrote:
> I did not get your point.
> for 2 6 3 7
> min 2
> sec min 3
> difference is 1
> answer is 2 and 3
> what more is asked??
>
> On
I did not get your point.
for 2 6 3 7
min 2
sec min 3
difference is 1
answer is 2 and 3
what more is asked??
On Jul 12, 2:21 pm, srikanth sg wrote:
> 2 6 3 7
> check for this
>
> On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar wrote:
>
> > traverse array with 2 elements keeping track of 2 min elem
This problem cannot be solved in less than O(nlgn) time with O(1)
space. The Element Distinctness Problem has a proven lower bound of
Omega(nlgn). If the least difference problem could be solved in O(n)
then we can reduce the ED Problem to Least Difference problem and
solve it in O(n) time. This co
oh never mind that was wrong... :P
Anil
On Mon, Jul 12, 2010 at 5:03 PM, Anil C R wrote:
> you can find both the smallest and the second smallest number ...
> Anil
>
>
>
> On Mon, Jul 12, 2010 at 3:21 PM, ankur aggarwal
> wrote:
>
>> order nlogn is trivial ..
>> any thing better ??
>>
>>
>>
>>
you can find both the smallest and the second smallest number ...
Anil
On Mon, Jul 12, 2010 at 3:21 PM, ankur aggarwal wrote:
> order nlogn is trivial ..
> any thing better ??
>
>
>
> On Mon, Jul 12, 2010 at 2:51 PM, srikanth sg wrote:
>
>> 2 6 3 7
>> check for this
>>
>>
>> On Mon, Jul 12, 201
order nlogn is trivial ..
any thing better ??
On Mon, Jul 12, 2010 at 2:51 PM, srikanth sg wrote:
> 2 6 3 7
> check for this
>
>
> On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar wrote:
>
>> traverse array with 2 elements keeping track of 2 min elements. time
>> O(n) space O(1)
>>
>> On Jul 11, 9
2 6 3 7
check for this
On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar wrote:
> traverse array with 2 elements keeping track of 2 min elements. time
> O(n) space O(1)
>
> On Jul 11, 9:34 pm, Amit Jaspal wrote:
> > Constraint - O(n)
> >
> > On Sun, Jul 11, 2010 at 9:24 AM, amit wrote:
> > > Given
traverse array with 2 elements keeping track of 2 min elements. time
O(n) space O(1)
On Jul 11, 9:34 pm, Amit Jaspal wrote:
> Constraint - O(n)
>
> On Sun, Jul 11, 2010 at 9:24 AM, amit wrote:
> > Given an array of size n.find 2 numbers from array whose difference is
> > least.
>
> > --
> > You
traverse array with 2 elements keeping track of 2 min elements. time
O(n) space O(1)
On Jul 11, 9:34 pm, Amit Jaspal wrote:
> Constraint - O(n)
>
> On Sun, Jul 11, 2010 at 9:24 AM, amit wrote:
> > Given an array of size n.find 2 numbers from array whose difference is
> > least.
>
> > --
> > You
13 matches
Mail list logo
