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.

Answer 3

I've seen this problem on InterviewBit and I guess I've the solution right, captured the logic I followed to find the 'k'th smallest element in array below..

• Find the smallest element in the array, this is the last smallest.
• In a loop, for 'k' times, find the element that is next biggest to the smallest found in the last iteration of the loop(the last smallest found in first step will be used in the first iteration of the loop)
• Return the last found next biggest element from the loop Copied the code below..

int getSmallest(const int* A, int nSize){
        int nSmallestElemIndex = -1;
        int i;
        for(i=0; i < nSize; i++){
            if (-1 == nSmallestElemIndex){
                nSmallestElemIndex = i;
                continue;
            }
            if (A[i] < A[nSmallestElemIndex]){
                nSmallestElemIndex = i;
            }
        }
        return nSmallestElemIndex;
    }

    int nextBig(const int* A, int nSize, int nCurrentSmallest){
        int nNextBig = -1;
        int i;
        for(i=0; i < nSize; i++){
            if (i == nCurrentSmallest || A[i] < A[nCurrentSmallest]){
                continue;
            }
            if (A[i] == A[nCurrentSmallest] && 
                i <= nCurrentSmallest){
                continue;
            }

            if (nNextBig == -1){
                nNextBig = i;
                continue;
            }
            if (A[i] >= A[nCurrentSmallest] && A[i] < A[nNextBig]){
                nNextBig = i;
            }
        }
        return nNextBig;
    }

    int kthsmallest(const int* A, int n1, int B) {
        int nSmallestElem = getSmallest(A, n1);
        int nCount = 1;
        int nRes = nSmallestElem;
        while(nCount < B){
            nRes = nextBig(A, n1, nRes);
            nCount++;
        }
        return nRes;
    }

I executed and validated it for the test cases on my machine but it's not accepted at Interviewbit.

I'll be glad if the solution passes your validation. Let me know your comments.