CODEWITHSUNDEEP
algorithmsorting
pranay
pranay

Reputation: 2369

for each element finding the closest greater element

given an array of integers how can we get the closest greater element for each of its elment ? E.g if the array is A[] = {1,2,3,4,5} then the closest greater to A[0] is 2, for A[1] its 3 , for A[2] its 4..and so on. Is there is a way to do it efficiently than O(N^2) ? I thought of building two auxillary arrays wherein one would have all elements left of current element and less than it while another would have all elements right of current element and greater than it..but can't proceed further..Is the idea correct ? Thanks.

Upvotes: 1

Views: 2695

Answers (4)

Niklas B.
Niklas B.

Reputation: 95288

For another question I described how to find for every element the leftmost larger element to its right. This can be done using a stack in O(n).

You can modify the algorithm slightly so that in every iteration you know how close the first element to the right is.

Then you just apply it twice, once with the array and once with its reverse and take the element with the minimum distance as your result.

Runtime: O(n)

Upvotes: 3

MBo
MBo

Reputation: 80167

Linear-time two-pass algorithm (in Delphi)

var
  A, B: TArray<Integer>;
  Stack: TStack<Integer>;
  i, candidate: Integer;
begin
  //source array
  A := TArray<Integer>.Create(4, 2, 5, 2, 1, 6, 3, 2);

  //array for positions of closest greater elements
  B := TArray<Integer>.Create(-1, -1, -1, -1, -1, -1, -1, -1);

  //elements that pretend to be greater
  Stack := TStack<Integer>.Create;

  for i := 0 to High(A) do begin
    while (Stack.Count > 0) and (A[Stack.Peek] < A[i]) do
      B[Stack.Pop] := i;
    Stack.Push(i);
  end;
  //now B contains positions of greater elements to the right
  // {2,2,5,5,5,-1,-1,-1} 
  //-1 for elements without greater right neighbour

  //now walk right to left, find greater right neighbour, but use it
  //if it is CLOSER than right one
  for i := High(A) downto 0 do begin
    while (Stack.Count > 0) and (A[Stack.Peek] < A[i]) do begin
      candidate := Stack.Pop;
      if (B[candidate] = -1) or (B[candidate] - candidate > candidate - i) then
        B[candidate] := i;
    end;
    Stack.Push(i);
  end;
// Result positions: {2,2,5,2,5,-1,5,6}

Upvotes: 0

olegarch
olegarch

Reputation: 3891

a) If perform retrieval many times:

  1. Sort your array: O(n*log(N)); add UNDEF to right end of array
  2. Find i: position of your element O(log(N))
  3. return arr[i+1];

time: O(n*log(N)) for prepare, O(log(N)) for retrieval;

b) If perform single retrieval:

int rc = MAXINT;
foreach x (array) 
  if(x > input_val && x < rc)
    rc = x;

time: O(N)

Upvotes: 0

Guntram Blohm
Guntram Blohm

Reputation: 9819

Sort the array in O(n log n) time. For each element in your input array (N of them), do a binary search (O(log n)) in the sorted array. So the total complexity is O(n log n)+O(n log n) = O(n log n). Optimize as needed depending on what exactly you need; for example, if you know the input array is sorted in some way, finding the corresponding closest greater elements might be doable faster than with binary search.

Upvotes: 0

Related Questions