Algorithm involving partition and selection

Question

I understand that this question can be solved most efficiently by utilizing selection and partition, both of which can be completed in linear time. My idea was to select the nth smallest element in the array O(n), which in the example given would be 34, so j = 3 in this case. Then from i = 1 to j - 1, if the sequence is decreasing, set B[i] = j, the moment the sequence increases, set B[i] = i + 1 and stop. Recursively call the procedure on the array A[j ... n]. I don't think this is efficient at all and not sure if it is even correct or what the final complexity of my algorithm is.

Summary

(1) select nth smallest (index j) using deterministic select algorithm o(n)

(2)

function:
    for i = 1 to n do
      for j = i + 1 to n do
         if A[j] > A[i] then B[i] = j , B[j] = n + 1
         for k = i + 1 to j - 1 do
            if A[k] < A[k + 1]
               B[k] = j
            else
               B[k] = k + 1
               recursive function(A[j + 1, ... n]) // recursively perform procedure on portion of array starting from j + 1 (after max) to n.

Maybe you can use Merge Sort (O(nlogn)), which you can divide both of the arrays into n sublists, each containing 1 element. Then repeat the merge sublists to have new sorted sublists until there is only 1 sublist remaining. — Victor Luna
– Victor Luna, Commented Oct 17, 2015 at 18:33
@VictorLuna I think that's a correct solution but not the most efficient. I believe this problem can be done in O(n) — Mutating Algorithm
– Mutating Algorithm, Commented Oct 17, 2015 at 19:01
Actually merge sort it is not O(nlogn), it is O(n+m). Because the lists are like queues, they point to the next element to be used in each array. When it compares the values before inserting them, there are exactly n+m comparisons, making it O(n) at runtime. — Victor Luna
– Victor Luna, Commented Oct 17, 2015 at 19:13
@VictorLuna Can you please describe your algorithm as an answer to this question? — Mutating Algorithm
– Mutating Algorithm, Commented Oct 18, 2015 at 18:04
@VictorLuna Can you show how merge sort actually works to solve the problem using the given sample array provided in the question ? — Mutating Algorithm
– Mutating Algorithm, Commented Oct 18, 2015 at 21:36

Peter de Rivaz · Accepted Answer · 2015-10-17 19:26:50Z

3

There is a standard stack-based solution to this problem which is O(n). There is a good explanation at http://www.geeksforgeeks.org/next-greater-element/.

Here is an example Python implementation of the algorithm:

def next_greater_element(A):
    """Return an array of 1-based indices to the next strictly greater element, n+1 if none exists"""
    i=0
    n = len(A)
    NGE=[n+1]*len(A)
    stack=[]
    while i<len(A)-1:
        stack.append(i)
        while stack and A[stack[-1]]<A[i+1]:
            x=stack.pop()
            NGE[x]=i+2
        i+=1
    return NGE

A = [8,3,34,13,1,2,21,5]
B = next_greater_element(A)
print B

This prints

[3, 3, 9, 7, 6, 7, 9, 9]

The main point is that each element is pushed onto the stack once, and can be popped off the stack once, so the inner while loop can execute at most n times.

answered Oct 17, 2015 at 19:26

Peter de Rivaz

33.6k4 gold badges51 silver badges80 bronze badges

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

Comments

Gene · Accepted Answer · 2015-10-22 03:02:10Z

Just for fun, here is the stack-based solution in C, which turns out to be particularly concise:

#include <stdio.h>

void find_next_largest(int *a, int *b, int n) {
  int s[n], p = -1;
  for (int i = 0; i < n; i++) {
    while (p >= 0 && a[i] > a[s[p]]) b[s[p--]] = i;
    s[++p] = i;
  }
  while (p >= 0) b[s[p--]] = n;
}

int main(void) {
  int a[] = { 8, 3, 34, 13, 1, 2, 21, 5, }, b[100];
  int n = sizeof a / sizeof a[0];
  find_next_largest(a, b, n);
  for (int i = 0; i < n; i++) printf("%d ", b[i] + 1);
  printf("\n");
  return 0;
}

The key idea of the algorithm is that each new "next" element of a is either adding on to a non-increasing tail (it is less than or equal to the last element), or it is increasing. In the latter case, we want to go backward through the non-increasing tail, recording that the new element is its next largest, stopping when an equal or larger element is found, then pushing the new element. A stack is the perfect data structure for searching backward through previously encountered data. The array s is the stack. It stores indices into a of elements waiting for their next largest to be found.

Note that if the new a element is no larger than the previous, the condition "stop popping when an equal or larger element is found, then push the new element" naturally does the right thing when the new element isn't larger than the previous. It pops zero elements and pushes the new one.

Also note it's invariant that the a elements referenced by s are always sorted ascending from the head.

Collectives™ on Stack Overflow

Algorithm involving partition and selection

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related