[Solved] Replace every element with the next greatest? [closed]

by

[ad_1]

Following is a way to do it in O(nlogn) :-

int newarr[];   
MinHeap heap; 
heap.push(0);  
for(int i=1;i<n;i++) { 
  while(arr[heap.top()]<arr[i]) {    
      k = heap.pop();
      newarr[k] = arr[i];
  }    
  heap.push(arr[i]);

} 

// No larger elements

while(!heap.isEmpty) {
  k = heap.pop();
  newarr[k] = -1;

}

Time Complexity : There are only n inserts and n deletes possible in the heap from the above code hence it is O(nlogn) where it take O(logn) for insert and delete in heap

[ad_2]

solved Replace every element with the next greatest? [closed]