Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
share my O(n) solution:
public static int[] replaceNextHigher(int[] nums){
if(nums == null || nums.length<=1){
return nums;
}
Deque<Integer> deque = new ArrayDeque<>();
int[] array = new int[nums.length];
for(int i = nums.length-1;i>=0;i--){
if(i==nums.length-1){
array[i]=nums[i];
deque.offer(nums[i]);
}else{
while(!deque.isEmpty()&&nums[i]>=deque.peekFirst()){
deque.pollFirst();
}
if(deque.isEmpty()){
array[i] = nums[i];
}else{
array[i]=deque.peekFirst();
}
deque.offerFirst(nums[i]);
}
}
return array;
}
public static void main(String args[]) throws Exception {
int arr[] = { 1, 2, 3, 4, 9, 5, 6 };
nextHigherElem(arr);
System.out.println(Arrays.toString(arr));
}
public static int[] nextHigherElem(int arr[]) {
int op[] = new int[arr.length];
Stack<Integer> stack = new Stack<Integer>();
for (int i = arr.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
op[i] = arr[stack.peek()];
} else {
op[i] = -1;
}
stack.push(i);
}
System.arraycopy(op, 0, arr, 0, arr.length);
return arr;
}
I m not sure why to use any exotic structures for this problem, I can think of the solution below:
a) Copy the whole array into a temporary array and sort it.
b) Iterate through each element in original array and do binary search in the sorted array to give last occurrence - not the element - but the occurrence i.e. index of the element in the sorted array. Then you get next bigger by sorted[ lastOccurrence + 1 ] if lastOccurrence < originalarray.length - 1.
Replace the original 's element with this one.
Complexity :
Space = O(n)
Time = O(nlogn) for sort
O(nlogn) for replace. - because for each i in n there is a binary search with log n time.
import java.util.Stack;
import java.util.Arrays;
public class NextHigher
{
public static void main(String[] args)
{
int[] a = {10, 5, 2, 1, 4, 6, 7};
//int[] a = {1, 2, 3};
//int[] a = {5, 4, 3, 2, 1};
//int[] a = {1, 1, 1};
NextHigher n = new NextHigher();
System.out.println(Arrays.toString(n.populateNextHigher(a)));
}
public int[] populateNextHigher(int[] a)
{
Stack<Integer> stack = new Stack<>();
int[] res = new int[a.length];
for(int i = a.length-1;i>=0;i--)
{
if(stack.isEmpty())
{
stack.push(a[i]);
res[i] = a[i];
}
else
{
while(!stack.isEmpty() && stack.peek()<a[i])
stack.pop();
if(!stack.isEmpty())
res[i] = stack.peek();
else
res[i] = a[i];
stack.push(a[i]);
}
}
return res;
}
}
We can build a Binary Search Tree, keeping mapping of idx_in_orig_array => node_in_bst.
Then, we iterate through the array. We remove the BST node of the i-th element in the array. We do a search in the BST to find the value which is next higher of the value of the i-th element. We replace the i-th element with the next higher value, if any. Then, we do the same for the next element.
Worst case time is O(N^2), because the BST can degrade into a list, and searching for the next higher value would be O(N). But expected time would be something like O(N log N).
- shweta.agarwal21 August 30, 2017