How to find the Kth smallest integer in an unsorted read only array?

Question

This is a standard question which has been answered many a times in several sites but in this version there are additional constraints:

1. The array is read only (we cannot modify the array).
2. Do it in O(1) space.

Can someone please explain to me the approach to this in best possible time complexity.

Answer 1

There is actually one way of solving this problem in O(n log d) time complexity & O(1) space complexity, without modifying the array. Here n stands for the length of the array, while d is the length of the range of numbers contained in it.

The idea is to perform a binary search for the kth smallest element. Start with lo = minimum element, and hi = maximum element. In each step check how many elements are smaller than mid and update it accordingly. Here is the Java code for my solution:

    public int kthsmallest(final List<Integer> a, int k) {
        if(a == null || a.size() == 0)
             throw new IllegalArgumentException("Empty or null list.");
        int lo = Collections.min(a);
        int hi = Collections.max(a);

        while(lo <= hi) {
            int mid = lo + (hi - lo)/2;
            int countLess = 0, countEqual = 0;

            for(int i = 0; i < a.size(); i++) {
                if(a.get(i) < mid) {
                    countLess++;
                }else if(a.get(i) == mid) {
                    countEqual++;
                }
                if(countLess >= k) break;
            }

            if(countLess < k && countLess + countEqual >= k){
                return mid;
            }else if(countLess >= k) {
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }
        }


        assert false : "k cannot be larger than the size of the list.";
        return -1;
    }

Note that this solution also works for arrays with duplicates and/or negative numbers.

Answer 2

I am going to assume read-only array is a strong requirement, and try to find tradeoffs that do not violate it in this answer (So, using selection algorithm is not an option, since it modifies the array)

As a side note, from wikipedia, it cannot be done in O(1) space without modifying the array:

The required space complexity of selection is easily seen to be k + O(1) (or n − k if k > n/2), and in-place algorithms can select with only O(1) additional storage .... The space complexity can be reduced at the cost of only obtaining an approximate answer, or correct answer with certain probability

It can be done in O(k) space with O(nlogk) time. In case k is constant, it is O(1) solution

The idea is to keep a max heap of size k. First populate it with the first k elements, and then keep iterating the array. If some element x is smaller than the top of the heap, pop the old head, and insert x instead.

When you are done, the head of the heap is the kth smallest element.

---

In terms of big O notation, it can be done in O(n) with O(k) space by using a new array of size 2k, load elements in chunks to the array, and use selection algorithm on this auxillary array to find the kth element. Discard all elements bigger than the k'th element, and repeat for next chunk (load more k elements). Complexity is O(k*n/k) = O(n)

This is however seldom used and has significantly worse constants than the heap solution, which is used quite often.

---

If you really want to use O(1) space, a brute force solution can be used by finding a minimum k times. You only need to remember the old minimum, which is constant space. This solution is O(nk) time with O(1) space, which is significantly less efficient than the alternatives, in terms of time.