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

by


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

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