Finding the predecessor of every element in a sequence

Question

Given a sequence a[1], a[2], a[3] .... a[n], I have to find for every a[i], an element a[j] where a[j] is the first element in the sequence a[i - 1], a[i - 2], a[i - 3].... such that a[j] < a[i].

In other words, I have to find a[j] where a[j] < a[i] and 1<=j<i. But if there are multiple such elements, I have to choose the one which is closest to a[i].

For example, in the following sequence:

2 6 5 8

I have to output 2 for both 6 and 5, and 5 for 8.

I know this can be done easily in O(n^2), but is there any more efficient way of doing this?

Answer 1

Can be done in O(n) using a stack.

a = your array
d = a stack
d.push(a[1])
for i = 2 to n do
  while d.top > a[i] do
    d.pop()

  print d.top if it exists, else -1
  d.push(a[i])

Basically, we keep d sorted and make sure its last element is always smaller than a[i]. This way, the last element in d will always be what we are looking for.

The linear complexity may not be immediately obvious due to the nested loops, but observe that each element will leave and enter the stack at most once, so a constant number of times.