## Amazon Interview Question

SDE-2s**Country:**United States

```
//O(2*N)
public class HelloWorld{
public static void main(String []args){
int[] arr = { 1,5,4,3,6,10,1,3,2,11};
amzQ(arr);
}
public static void amzQ(int[] nums){
if(nums == null) return;
int len = nums.length;
int[] leftIdx = new int[len];
leftIdx[0]=1;
int[] rightIdx =new int[len];
rightIdx[len-1]=len;
amzQ(nums,leftIdx, rightIdx );
}
public static void amzQ(int[] nums,int[] leftIdx,int[] rightIdx ){
int max = nums[0], maxIdx = leftIdx[0];
for( int i =1; i < nums.length; i++){
if( max < nums[i]){
max = nums[i];
leftIdx[i] = leftIdx[0];
}
if(nums[i-1] > nums[i]){
leftIdx[i] = i+1;
}else{
if(nums[i] != max){
leftIdx[i] = leftIdx[i-1];
}
}
}
max = nums[nums.length-1];
maxIdx = rightIdx[nums.length-1];
for( int i = nums.length-2; i >= 0; i--){
if( max < nums[i]){
max = nums[i];
rightIdx[i] = maxIdx;
}
if(nums[i+1] > nums[i]){
rightIdx[i] = i+1;
}else{
if(nums[i] != max){
rightIdx[i] = rightIdx[i+1];
}
}
}
for(int i =0; i < nums.length; i++){
System.out.println(""+nums[i]+" ["+leftIdx[i] +
" "+rightIdx[i]+" ]");
}
}
}
```

For finding the low (left-hand) MAX of a[i]:

1. If a[i-1] > a[i], return i

2. If we don't know yet the MAX range of a[i-1], find it (recursively)

3. Use the low MAX of a[i-1] to skip elements which are surely smaller than a[i]

4. Repeat steps 2-4 as long as we don't see an element higher than us

```
import random
class Cell():
def __init__(self, pos, val):
self.pos, self.val = pos, val
self.low, self.high, self.queued = -1, -1, False
def get_border(self, side):
return self.low if side < 0 else self.high
def __str__(self):
return ' '.join(["[", str(self.pos), "]", str(self.val),
"(", str(self.low), "->", str(self.high), ")"])
class Array():
def __init__(self, arr):
self.arr = [ Cell(pos, val) for pos, val in enumerate(arr) ]
self.queue = []
self.enqueue( self.arr[ len(self.arr) // 2 ] )
def enqueue(self, cell):
if cell.queued or cell.low > 0:
return
cell.queued = True
self.queue.append(cell)
def dequeue(self):
cell = self.queue.pop()
cell.queued = False
return cell
def process(self):
while len(self.queue):
cell = self.dequeue()
if cell.low < 0:
self.find_range(cell)
def find_range(self, cell):
cell.low = self.find_border(cell, -1)
cell.high = self.find_border(cell, 1)
def find_border(self, cell, delta):
cand = cell.pos + delta
last_cell = cell
while True:
# check array borders
if cand < 0:
return 0
if cand >= len(self.arr):
return len(self.arr) - 1
cand_cell = self.arr[cand]
# check if we reached a cell higher than us
if cand_cell.val > cell.val:
self.enqueue(cand_cell)
# return the position of the last cell which was
# smaller/equal to us
return last_cell.pos
# was this cell calculated already
if cand_cell.low < 0:
self.find_range(cand_cell)
# use cand's own low/high max to skip over values
# which are surely smaller than us
next_cand = cand_cell.get_border(delta)
if next_cand == cand:
# nothing to skip here, so keep crawling in the same direction
next_cand = cand_cell.pos + delta
cand = next_cand
last_cell = cand_cell
def __str__(self):
out = ""
for c in self.arr:
out += str(c) + "\n"
return out
a = [ random.randint(1,100) for i in range(100) ]
arr = Array(a)
arr.process()
print(arr)
```

```
import random
class Cell():
def __init__(self, pos, val):
self.pos, self.val = pos, val
self.low, self.high, self.queued = -1, -1, False
def get_border(self, side):
return self.low if side < 0 else self.high
def __str__(self):
return ' '.join(["[", str(self.pos), "]", str(self.val),
"(", str(self.low), "->", str(self.high), ")"])
class Array():
def __init__(self, arr):
self.arr = [ Cell(pos, val) for pos, val in enumerate(arr) ]
self.queue = []
self.enqueue( self.arr[ len(self.arr) // 2 ] )
def enqueue(self, cell):
if cell.queued or cell.low > 0:
return
cell.queued = True
self.queue.append(cell)
def dequeue(self):
cell = self.queue.pop()
cell.queued = False
return cell
def process(self):
while len(self.queue):
cell = self.dequeue()
if cell.low < 0:
self.find_range(cell)
def find_range(self, cell):
cell.low = self.find_border(cell, -1)
cell.high = self.find_border(cell, 1)
def find_border(self, cell, delta):
cand = cell.pos + delta
last_cell = cell
while True:
# check array borders
if cand < 0:
return 0
if cand >= len(self.arr):
return len(self.arr) - 1
cand_cell = self.arr[cand]
# check if we reached a cell higher than us
if cand_cell.val > cell.val:
self.enqueue(cand_cell)
# return the position of the last cell which was
# smaller/equal to us
return last_cell.pos
# was this cell calculated already
if cand_cell.low < 0:
self.find_range(cand_cell)
# use cand's own low/high max to skip over values
# which are surely smaller than us
next_cand = cand_cell.get_border(delta)
if next_cand == cand:
# nothing to skip here, so keep crawling in the same direction
next_cand = cand_cell.pos + delta
cand = next_cand
last_cell = cand_cell
def __str__(self):
out = ""
for c in self.arr:
out += str(c) + "\n"
return out
a = [ random.randint(1,100) for i in range(100) ]
arr = Array(a)
arr.process()
print(arr)
```

No need of segment tree it will use 2*n space at max. It could be done by as follows:

- Anonymous August 17, 2020take stacks and for every element find position of next and previous max that will we the range. Run time complexity will be O(n).