Given the array, find the last smaller item for each item
Given the array, find the last index of the smallest element in the array for each element.
For example, suppose the given array is {4,2,1,5,3}
. Then the last smallest element for each element will be next.
4->3
2->1
1->Null
5->3
3->Null
Note for 1st pair 4-> 3, 3 is the last element in the array is less than 4.
The resulting / output array will have indices not on the elements themselves. The result will be{4,2,-1,4,-1}
I was asked this question in an interview, but I couldn't think of a better solution than a trivial solution O(n^2)
.
Any help would be much appreciated.
source to share
We need to compute max(index)
over all elements with lower values.
Let's sort the pairs (item, index) in lexicographic order and iterate over them, keeping track of the largest index seen so far. This is exactly the position of the rightmost smallest element. Here's how you can do it:
def get_right_smaller(xs):
res = [-1] * len(xs)
right_index = -1
for val, idx in sorted((val, idx) for idx, val in enumerate(xs)):
res[idx] = right_index if right_index > idx else -1
right_index = max(right_index, idx)
return res
This solution works correctly even if the input array contains equal numbers, because the element with the lower index comes first if the values of the two elements are the same.
The time complexity of this solution is O(N log N + N) = O(N log N)
(it does sort and one linear pass).
If all the elements are in an array O(N)
, you can make this solution linear using count sort.
source to share
Make a list, add last element index.
Walk through array right to left.
For every element:
if list tail value is smaller then current element
find the most first smaller list element (binary search, list is sorted)
otherwise
add element index to the list tail, output -1
for {4,2,1,5,3,6,2}
a list of examples will containindex 6 (value 2); index 2 (value 1)
source to share