The notes are misleading - it can't be done in linear time, constant space and without modifying the array


#1

The notes say:
(1) You are not allowed to modify the array ( The array is read only ).
(2) Try to do it using constant extra space.

The “best” solution to this problem does require modifying or copying the array.
Which means if we follow note (1) we can’t follow note (2) because we need to copy the array, which means o(n) space complexity.


#2

Agreed. The best suggestion here is to use quick-select (from quick-sort). That means we either need to modify the array in place or copy over the elements to a new array to process elements there.
Does make me wonder if another solution exists since someone went to the trouble of specifically adding those notes.


#3

Both quicksort and median of medians and the hybrids require extra space (some don’t if you may modify the array).

But there are solutions who can comply with the notes, for example the naive, O(n^2), solution:

def kthsmallest(A, B):
    for itema in A:
        a_k = 1
        equal_to_a = -1
        for itemb in A:
            if itema > itemb:
                a_k += 1
            elif itema == itemb:
                equal_to_a += 1
        if B >= a_k and B <= equal_to_a + a_k:
            return itema