Find nearest by index numbers in array less than number at given index

Question

This is an algorithm optimization problem.

I have an integer array A and want to build array B such that B[i] contains index j of the element in A[j] such that (B[i] = j)

1. j > i
2. A[j] < A[i]
3. j is minimum of all possible j's.

For example if A is:

   A = [1,5,6,4,3,1,2]

Then B will be (indexing from 0)

   B = [-1,3,3,4,5,-1,-1]

B[0] = -1 because there is no numbers less than 1 with indices more than 0. B[1] = 3 because A[3] is the right-closest element to index 1 in A that contains number less than A[1]=5. And so forth.

I know the solution with O(n*log(n)) complexity using binary search tree. How can I enhance the complexity to O(n) or prove that it is impossible?

checked again, b[1] is not equal to 2 because a[2] = 6 > 5 = a[1] — Daniel
– Daniel, Commented Apr 17, 2013 at 18:18

rici · Accepted Answer · 2013-04-15 18:03:32Z

4

Unless I misunderstand the problem, you can solve it in a simple left-to-right scan, keeping a stack of indices for which you have not yet encountered a smaller element. (The values corresponding to the indices on the stack must be monotonically non-decreasing, for obvious reasons.)

For each value in the input list, while that value is less than the value corresponding to the top index (if any) of the stack, set the corresponding element of the output list to the index of the current input value and pop the stack.

The following little Python program illustrates:

def ind(a):
  b = [-1] * len(a)
  stack = []
  for i in range(len(a)):
    v = a[i]
    while stack and a[stack[-1]] > v:
      j = stack.pop()
      b[j] = i
    stack.append(i)
  return b

Proof that it is O(n): The for loop is clearly executed n times. The body of the while loop executes (in total) at most n times, since it can only happen once for each element. Or, to put it another way, every element is pushed and popped at most once.

edited Apr 15, 2013 at 18:03

answered Apr 15, 2013 at 17:57

rici

243k30 gold badges263 silver badges364 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Daniel Over a year ago

You did not misunderstood, everything is right, thank you! I totally forgot that I can use stack

Collectives™ on Stack Overflow

Find nearest by index numbers in array less than number at given index

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related