How To Sort An Array With N Elements In Which K Elements Are Out Of Place In O(n + K Log K)?

I was asked this in an interview today, and am starting to believe it is not solvable. Given a sorted array of size n, select k elements in the array, and reshuffle them back into

Solution 1:

Note: This is a conceptual solution. It is coded in Python, but because of the way Python implements List, does not actually run in the required complexity. See soyuzzzz's answer to see an actual solution in Python in the complexity requirement.

Accepted @soyuzzzz's answer over this one.

Original answer (works, but the complexity is only correct assuming Linked list implementation for Python's List, which is not the case):

This sorts a nk-unsorted array in O(n + klogk), assuming the array should be ascending.

1. Find elements which are not sorted by traversing the array.
2. If such an element was found (it is larger then the following one), then either it or the following one are out of order (or both).
3. Keep both of them aside, and remove them from the array
4. continue traversing on the newly obtained array (after removal), form the index which comes before the found element.
5. This will put aside 2k elements in O(n) time.
6. Sort 2k elements O(klogk)
7. Merge two sorted lists which have total n elements, O(n)
8. Total O(n + klogk)

Code:

defmerge_sorted_lists(la, lb):
    if la isNoneor la == []:
        return lb
    if lb isNoneor lb == []:
        return la
    a_ind = b_ind = 0
    a_len = len(la)
    b_len = len(lb)

    merged = []
    while a_ind < a_len and b_ind < b_len:
        a_value = la[a_ind]
        b_value = lb[b_ind]

        if a_value < b_value:
            merged.append(la[a_ind])
            a_ind += 1else:
            merged.append(lb[b_ind])
            b_ind += 1# get the leftovers into mergedwhile a_ind < a_len:
        merged.append(la[a_ind])
        a_ind += 1while b_ind < b_len:
        merged.append(lb[b_ind])
        b_ind += 1return merged

and

defsort_nk_unsorted_list(nk_unsorted_list):
    working_copy = nk_unsorted_list.copy()  # just for ease of testing

    requires_resorting = []

    current_list_length = len(working_copy)
    i = 0while i < current_list_length - 1and1 < current_list_length:
        if i == -1:
            i = 0

        first = working_copy[i]
        second = working_copy[i + 1]

        if second < first:
            requires_resorting.append(first)
            requires_resorting.append(second)

            del working_copy[i + 1]
            del working_copy[i]
            i -= 2
            current_list_length -= 2
        i += 1

    sorted_2k_elements = sorted(requires_resorting)
    sorted_nk_list = merge_sorted_lists(sorted_2k_elements, working_copy)
    return sorted_nk_list

Solution 2:

Even though @Gulzar's solution is correct, it doesn't actually give us O(n + k * log k). The problem is in the sort_nk_unsorted_list function. Unfortunately, deleting an arbitrary item from a Python list is not constant time. It's actually O(n). That gives the overall algorithm a complexity of O(n + nk + k * log k)

What we can do to address this is use a different data structure. If you use a doubly-linked list, removing an item from that list is actually O(1). Unfortunately, Python does not come with one by default.

Here's my solution that achieves O(n + k * log k).

The entry-point function to solve the problem:

defsort(my_list):
    in_order, out_of_order = separate_in_order_from_out_of_order(my_list)

    out_of_order.sort()

    return merge(in_order, out_of_order)

The function that separates the in-order elements from the out-of-order elements:

defseparate_in_order_from_out_of_order(my_list):
    list_dll = DoublyLinkedList.from_list(my_list)
    out_of_order = []
    
    current = list_dll.head

    while current.nextisnotNone:
        if current.value > current.next.value:
            out_of_order.append(current.value)
            out_of_order.append(current.next.value)

            previous = current.prev

            current.next.remove()
            current.remove()

            current = previous
        else:
            current = current.next

    in_order = list_dll.to_list()

    return in_order, out_of_order

The function to merge the two separated lists:

defmerge(first, second):
    """
    Merges two [sorted] lists into a sorted list.

    Runtime complexity: O(n)
    Space complexity: O(n)
    """
    i, j = 0, 0

    result = []
    
    while i < len(first) and j < len(second):
        if first[i] < second[j]:
            result.append(first[i])
            i += 1else:
            result.append(second[j])
            j += 1            

    result.extend(first[i:len(first)])
    result.extend(second[j:len(second)])

    return result

And last, this is the DoublyLinkedList implementation (I used a sentinel node to make things easier):

classDoublyLinkedNode:
    def__init__(self, value):
        self.value = value
        self.next = None
        self.prev = Nonedefremove(self):
        if self.prev:
            self.prev.next = self.nextif self.next:
            self.next.prev = self.prev
        

classDoublyLinkedList:
    def__init__(self, head):
        self.head = head

    @staticmethoddeffrom_list(lst):
        sentinel = DoublyLinkedNode(-math.inf)
        previous = sentinel

        for item in lst:
            node = DoublyLinkedNode(item)
            node.prev = previous
            previous.next = node

            previous = node
        
        return DoublyLinkedList(sentinel)

    defto_list(self):
        result = []
        current = self.head.nextwhile current isnotNone:
            result.append(current.value)
            current = current.nextreturn result

And these are the unit tests I used to validate the code:

import unittest


classTestSort(unittest.TestCase):
    deftest_sort(self):
        test_cases = [
            # ( input, expected result)
            ([1, 2, 3, 4, 10, 5, 6], [1, 2, 3, 4, 5, 6, 10]),
            
            ([1, 2, 5, 4, 10, 6, 0], [0, 1, 2, 4, 5, 6, 10]),

            ([1], [1]),

            ([1, 3, 2], [1, 2, 3]),
            ([], [])
        ]

        for (test_input, expected) in test_cases:
            result = sort(test_input)
        
            self.assertEqual(expected, result)