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

Approach:

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)




You might attempt to sort the array
{9(2), 8(1), 5(3), 4(0), 3(6), 2(5), 1(4)}

Now you can iterate over the array and keep track of the index encountered so far, if it is greater than the encountered so far, then it is maximum among all the elements among its right.Overall complexity is now O(nlogn + n) = O(nlogn)

Can we do better? In fact there is seemingly easy solution, just iterate over the array from n - 1 to 0. If the element is the largest encountered so far, then it is a part of the result.

The below snippet code should suffice

void findMaxOnRight(int * a, int n) {
    int max = a[n-1] - 1;
    for(int i = n-1; i >= 0; i--) {
        if (a[i] > max) {
            max = a[i]; 
            cout << a[i] << endl;
        }
    }
}

2 comments :

  1. int max = -10000;
    for(int i = n-1; i >= 0; i--){
    if(input[i] > max){
    max = input[i];
    print(input[i]);
    }
    }

    ReplyDelete
  2. int max = input[n-1] -1; is a better option :)

    ReplyDelete