Monday, April 12, 2010

Find the largest element in an interval

Given an array of n integers, find the k-th largest element in the interval [i, j]. Note that i, j, k are input parameters. What is the complexity.

3 comments:

  1. I guess I would try something similar to the QuickSort algo. Take a pivot, reorder the elements, if it's the k-th element in the reordered array then return that element, else go do the same step on the side which should contain the k-th elem. There might be a better approach.

    complexity is log(N) I think

    ReplyDelete
  2. so not linked to the size of the interval? you could make it better

    ReplyDelete
  3. You can sort the elements in the [i, j] interval and take the k-th element in costant time. So the complexity is t log t where t=j-i.

    ReplyDelete