Amazon Interview Question
Software TraineesCountry: India
Interview Type: Phone Interview
@Ashish: good solution
Its hard to understand but great solution time complexity is O(n)
Given input ascending or descending in two cases it is O(n)
+1 d
Note: In stack adding only indexes and doing in-place good
@Venkatesh Not only for ascending or descending cases, but for all the cases the time complexity is O(n) or more generally O(2n) which gives us O(n) only.
Ashish, you are replacing the last element which has not yet got a greater number. Once it gets a greater number, its pop-ed out and never processed again, which will fail in the below case:
Input: {3, 4, 1, 5, 2} gives {4, 5, 5, -1, -1} as output as per your solution.
Actual output should be: {4, 5, 2, -1, -1}.
@KP23 The output for 3,4,1,5,2 should be 4,5,5,-1,-1 . Question asks for the nearest greater on the right. For 1 the nearest greater is 5 and not 2. So the output given by my code is correct.
For this input
3 1 2 7 6 10 9 15 0 1 2 8, the output shud be
7 2 7 10 15 15 15 1 8 8
I don't see the stack based solution give a correct answer to this...
do we really need a stack here?
why can't we save value and index of an element and when a larger element is found update every element from saved index to current index..
There is no need to use any extra stack or other DS..
simple O(n) solution without extra space....
Please comment on it.
#include<stdio.h>
#define SIZE 10
int main(void)
{
int arr[SIZE];
int i, j;
for(i=0; i<SIZE; i++)
{
printf("Enter the Element for Array[%d] : ", i);
scanf("%d", &arr[i]);
}
printf("\n Original Array : ");
for(i=0; i<SIZE; i++)
printf(" %d", arr[i]);
j=0;
for(i=0; i<SIZE-1; i++)
{
if(i == j)
for(j=i+1; j<SIZE && arr[i]>=arr[j]; j++);
if(j > i && j < SIZE) //Extra condition has been added to see whether have to replace or not.
arr[i] = arr[j];
}
printf("\n Modified Array : ");
for(i=0; i<SIZE; i++)
printf(" %d", arr[i]);
printf("\n\n");
return 0;
}
An elegant solution in O(n) is given here
geeksforgeeks.org/replace-every-element-with-the-greatest-on-right-side/
this solution replaces the current element with the greatest number which is present on the right side not the nearest greater element
Yes question asking near greater element not greatest on right.
Same solution with minor change:
Replace every element with the maximum element only if it is greater than current element otherwise -1.
input {16, 17, 4, 3, 5, 2},
output {17, -1, 5, 5, -1 -1}
Here is a O(n) solution:
a. Keep the first element in temp and its index stored in k.
b. For every element see the difference with the next element
c. When the difference is greater than 0 then update the k variable and also the j variable.
d. Note for finding the difference of the element there are two pointers in the array that is j and k k runs the loop and j finds the difference.
e. If the element does not have a large element then it is updated to -1.
#include <stdio.h>
#include <conio.h>
void findNextGreater(int arr[],int n)
{
int j,temp,k=0;
temp=arr[k];
j=1;
while(k!=n-1)
{
if(arr[j]-temp<0&&j==n-1)
{
arr[k]=-1;
k=k+1;
temp=arr[k];
j=k;
}
if(arr[j]-temp>0)
{
arr[k]=arr[j];
k=k+1;
j=k;
temp=arr[k];
}
else
{
j=j+1;
}
}
arr[n-1]=-1;
for(j=0;j<n;j++)
printf(" %d ",arr[j]);
}
int main()
{
int arr[]={11,13,21,32,10};
int n=sizeof(arr)/sizeof(arr[0]);
findNextGreater(arr,n);
}
@vgeek:
Good try I appreciate, program gives correct solution but problem in time complexity in worst case.
If given input is in descending and last value is greatest then this time complexity is O(n^2) where everytime your j variable goes end.
ex: 10,9,8,7,6,5,4,3,2,1,11
@Ashish: solution always gives O(N)
@Ashish, If I understand your solution correctly, it replaces element with next greater element on right side. But problem is is element should be replaced with NEAREST GREATER element.
Correct me if I am wrong.
Input: 22 5 4 20 13 17 12 3
Output: 22 7 7 20 17 17 12 3
I also didn't understand why people are replacing with -1. If we don't have greater element on right side, I believe we should keep that element as it is. am I right?
Yes for that you can just ignore the -1 step that is if you use a stack or if you are doing an array traversal so you can skip that step where in an array if we reach the last element then it ignore the -1 step and also in stack you can pop the elements if they are left while storing the numbers
@kallu: I agree with -1
but what is the difference between next greater and nearest greater on right.
your Input: 22 5 4 20 13 17 12 3
output : 22 20 20 20 17 17 12 3
public static int[] getReplacement(int[] data){
int[] index = new int[data.length];
int[] newData = new int[data.length];
index[index.length - 1] = -1;
for(int i = data.length - 1; i >= 1; i--){
int j = i;
while(true){
if(data[i - 1] < data[j]){
index[i - 1] = j;
break;
}else{
j = index[j];
if(j == -1){
index[i - 1] = -1;
break;
}
}
}
}
for(int i = 0; i < newData.length; i++)
newData[i] = index[i] == -1 ? data[i] : data[index[i]];
return newData;
}
Replace all elements using one traversal of the array.
The idea is to start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element only if it is greater than current element otherwise -1.
input {16, 17, 4, 3, 5, 2},
output {17, -1, 5, 5, -1 -1}
void nearGreater(int arr[], int size)
{
int max_from_right = arr[size-1];
int current;
arr[size-1] = -1;
for(int i = size-2; i >= 0; i--)
{
current = arr[i];
if(max_from_right > current)
arr[i] = max_from_right;
else {
arr[i] = -1;
max_from_right = current;
}
}
O(n)
modified http://www.geeksforgeeks.org/replace-every-element-with-the-greatest-on-right-side
for input {14,11,3,13,15,20}
your output = {20,20,20,,20,20,-1}
actual output = {15,13,13,15,20,-1}
It cannot be done in O(n).
In below case
13,12,11,10,9,8,7
for above example array will remain unchanged after replacing near greater element on the right. But for each element we have to check all the elements to its right. Best solution will be of nlogn complexity.
@Anonymous, the solution may not be done in O(n), but for your case/example it can be done in O(n), if you maintain the right largest element. Start from right side and check whether current element is greater than largest element traversed so far. If it is greater than that then no need to traverse the right side list again. Perhaps, this should be the one if the optimization step in solution.
public static void replaceWithGreaterNumber(int[] A)
{
int len = A.length;
int grt = -1; // assign with default value -1
for(int i = len-1; i >= 0; i--)
{
int tmp = A[i];
if (grt > tmp) // ith index value smaller than previous greater value, then assign A[i] with grt
{
A[i] = grt;
}
else
{
A[i] = -1; // else assign A[i] with -1
if (tmp > grt)
{
grt = tmp; // updating grt (greater value) with A[i] that is with tmp
}
}
}
for(int i = 0;i < len; i++)
System.out.print(A[i] + " ");
}
Time complexity : O(n)
Space complexity : O(1)
Pls point out if there is any bug
Using a stack we can push the element's index on the stack till the next element is smaller. Once we get a larger number we can pop till the number is larger. The poped index can be used to modify the array.
- Ashish July 31, 2013