Geek asks and answers

Search for the predecessor of each element in a sequence

Given the sequence a[1], a[2], a[3] .... a[n], I must find for each a[i]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 several such elements, I must choose the one that is closest to a[i].

For example, in the following sequence:

2 6 5 8

I need to print 2 for 6 and 5 and 5 for 8.

I know this can easily be done in O(n^2), but is there a more efficient way to do this?

+5
source share
1 answer

O(n) 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])

d , a[i]. , d , .

- , , , .

+3

More articles:


All Articles