Friday, April 1, 2011

Largest elements in the array to its right

Given an array of n elements find all the elements in the array such that it is greater than all the elements to its right. For e.g
array is {4,8,9,5,1,2,3}, numbers are 9,5 and 3


The trivial implementation would scan the integers from index 0 to n - 1 and for each index x we can compute if it is maximum among all the elements with index > x.

This implementation is pretty slow, with overall complexity O(n^2)