Friday, November 9, 2012

Find the next smallest number for a given number


In an unsorted array, given a number 'x',
find the next smallest number.
The number 'x' does exist in the array.
Array {62,50,91,32,60,63,17,36,55,61}
Num = 62
Result = 61

Num = 50
Result = 36

Approach:
Sorting is not a solution, since it will be O(N^2) or atleast O(N log N). 
Create a Binary Search Tree and find the number 'X'. Once found, fetch the right most node of its left subtree. Thats the required element.

Solution

1 comment:

  1. Smart solution, but it still takes O(nlogn) time to build the BST.

    ReplyDelete

UA-36403895-1