Amazon Interview Question
SDE-2sCountry: United States
No explicit Stack needed, I build array walking backwards, as a max of current input index and prev output index
can you explain how you arrived at the time complexity?....the way i see it both algorithms are using two loops..and both have comparisons..
The elements in the stack will always be stored in descending order.
So, each element will be pushed once and popped once. Hence O(n).
Thus for all the cases the time complexity is O(n) or more generally O(2n) which gives us O(n) only.
while( !stk.empty() && (Arr[idx] > Arr[stk.top()]) )
is this line correct?
i am talking about the check -- Arr[idx] > Arr[stk.top()])
Arr[stk.top()] may lead to index out of bound error?
If you run your algorithm with i/p in o/p's example, you will run into problem when processing 1 and 2. You will pop out 1 after assigning 2 to 1. Then when you meet 10, u will only assign 10 to item 8 6 and 5.
The question is asking to replace each element with the next element in the list which is larger than it.
Which is not at all clear from the phrase "Next Largest Element".
stack = Stack.new
stack.push(ary[len(ary)-1])
for i in range(len(ary)-2,0,-1):
while(ary[i]>stack.peek()):
stack.pop()
if(stack.peek()>ary[i]):
ary[i]=stack.peek()
stack.push(ary[i])
replace each element with its Next Largest Element == replace each element with the next element in the list which is larger than it
@zack.kenyon --- The i/p and o/p clearly showed what is required. Anyway,I have updated the question for clarity.
@Ramesh I agree that the input and output you listed convey what you mean. just that, there is a formal statement of the question which is precise and accurate, and not at all complex.
the next largest element in english would most commonly mean the least element in the array with is larger than it, whereas the "next, largER element" would probably be closer.
@zack.kenyon --- I just gave tech description of the question. I didn't think of the Literal meaning of the same :-)
public class ReplaceNextGreaterElement {
public static void main(String[] args) {
int a[] = { 2, 12, 8, 6, 5, 1, 2, 10, 3, 2 };
greaterElement(a);
display(a);
}
public static void display(int a[])
{
for(int a1:a)
{
System.out.print(a1+",");
}
}
public static void greaterElement(int a[]) {
int len = a.length;
for (int i = 0; i < len-1; i++) {
for (int j = 0; j < len-1; j++) {
if(a[j]<a[j+1])
{
a[j]=a[j+1];
}
}
}
}
}
this is a solution in C#. The number of arrays used can be minimized further. The time complexity is o(n)
static void Main(string[] args)
{
int[] retArray = GetChangedArray(intArray); // intArray is the integer array and retArray is the final array
}
public static int[] GetChangedArray(int[] origArr)
{
if (origArr == null || origArr.Length == 0) return origArr;
int len = origArr.Length;
int max = origArr[len - 1];
int[] MaxArr = new int[len];
for (int i = len - 1; i >= 0; i--)
{
MaxArr[i] = GetMax(max, origArr[i]);
max = MaxArr[i];
}
for (int i = 0; i < len; i++)
{
origArr[i] = GetMax(origArr[i], MaxArr[i]);
}
return origArr;
}
private static int GetMax(int x, int y)
{
return x > y ? x : y;
}
Can be solved in O(n) with two pointers.
1) slow and fast pointer initially points to zero'th element.
2) start moving fast pointer forward until its in increasing order.
3) on fast pointer reach a element that is less than prev.
4) start copying fast[i-1] to slow[j] until j reaches i-1.
Work backwards. Last element of array will always be max element in that position. Previous element should be compared with last element. If it is smaller then copy last element to previous element position. Similarly continue till the first element in array.
public class ReplaceLargestRHS {
private static void replaceLargestRHS(int a[])
{
int output[] = new int[a.length];
output[a.length -1] = a[a.length -1] ;
for(int i = a.length -2; i >=0; --i)
{
if(a[i] < output[i+1])
{
output[i] = output[i+1];
}
else
output[i] = a[i];
}
System.out.println("Input :" + Arrays.toString(a));
System.out.println("Output:" + Arrays.toString(output));
}
public static void main(String[] args) {
replaceLargestRHS(new int[]{2,12,8,6,5,1,2,10,3,2});
}
}
O(n)
void replaceNextLargest(int *arr, size_t size)
{
int max = arr[size - 1];
for (int i = size - 2; i >= 0; --i)
{
if (arr[i] > max)
{
max = arr[i];
}
else
{
arr[i] = max;
}
}
}
Just go from right to left keeping the max value found so far. Replace every element with such value (which can be the current element). O(N) time and O(1) space.
Why is it incorrect? I think it makes sense to go from right to left. But I think it is not to keep max. Instead, we record the value of current index from right to left in a variable which initially is minus infinity. During each step backward, we compare current value V.S value saved in the variable. If V<current value, then we replace current value. Continue stepping backward.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int A[] = {2,12,8,6,5,1,2,10,3,2};
const int N = sizeof(A) / sizeof(A[0]);
int m = A[N - 1];
for (int i = N - 2; i >= 0; i--) {
m = max(m, A[i]); // m = max(A[i], A[i+1], .... A[N-1]
A[i] = m;
}
for_each(A, A + N, [](int n) { cout << n << " "; });
cout << endl;
}
// output: 12 12 10 10 10 10 10 10 3 2
If it's the next largest, how come the first element becomes 12. When we consider A[0], the largest element from A[0] is 12, and the second largest is 10. If you want the second largest, A[0] should become 10.
The code can be easily adapted to handle the second largest case.
@Westlake - The question is clearly finding the Next Largest Element. I think to be more specific it is Next Immediate Largest Element.
So, for the First Element is 2 and the Next Immediate Largest Element is 12. So, it is 12.
I didn't understand how you came to finding Second Largest?
The question is misleading. I think it asks to replace A[i] with the first A[j] with condition i < j and A[i] <A[j]. If no such element exists, no change is needed.
C++ Version:
O(n2) version:
O(n) Version:
> Take stack and Initially push the Index 0 on to the stack.
> Traverse All Elements of the Array from left to right.
>> If the stack is Empty push the element in the stack.
>> If the stack is Non-Empty AND Current-Element > Stack-Top-Index-Element, then replace the Stack-Top-Index element in Array with Current-Element and Pop the Stack. Else Push the Index on to the Stack.
- R@M3$H.N March 03, 2014