What do you mean by " if this number is less than elements stored in
stack "
There have be N comparisons in the worst case. And that way, you have to do
it for every element.
So it will be governed by O(n^2)
On Wed, Nov 23, 2011 at 12:50 AM, Aamir Khan wrote:
>
>
> On Tue, Nov 22, 2011 at 11:5
On Tue, Nov 22, 2011 at 11:50 PM, tech coder wrote:
> here is an O(n) approach using a stack.
>
> problem can be stated as " find the 1st smaller element on the right.
>
> put the first element in stack.
> take next element suppose "num" if this number is less than elements
> stored in stack,
here is an O(n) approach using a stack.
problem can be stated as " find the 1st smaller element on the right.
put the first element in stack.
take next element suppose "num" if this number is less than elements
stored in stack, pop those elements , for these pooped elements num will
be the r
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta wrote:
> Input: A unsorted array of size n.
> Output: An array of size n.
>
> Relationship:
>
> > elements of input array and output array have 1:1 correspondence.
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
> elements of input array and output array have 1:1 correspondence.
> output[i] is equal to the input[j] (j>i) which is smaller than input[i] and
> jth is nearest to ith ( i.e. first element which is smaller).
> If no s
