Quick Select Pattern

Introduction:

Problems Following Quick Select Pattern

1. Find Kth Smallest Element in Unsorted Array

Problem:

Given a list of elements in unsorted arr, find the kth smallest element.

Examples:
Input: [7, 10, 4, 3, 20, 15] and k = 3
Output: 7

Input: [10, 4, 5, 8, 6, 11, 26] and k = 3
Output: 6
Approach-1: Use Sorting
Approach-2: Use Max-Heap of Size K
Approach-3: Use Randomized QuickSelect
Implementation

Code:

import random


def find_kth_smallest(arr, low, high, k):
    if (low <= high):
        p_index = partition(arr, low, high)
        if (p_index == k - 1):
            return arr[p_index]
        elif (p_index > k - 1):
            return find_kth_smallest(arr, low, p_index-1, k)
        else:
            return find_kth_smallest(arr, p_index + 1, high, k)

    return - 1


def partition(arr, low, high):
    rand_index = random.randint(low, high)
    arr[rand_index], arr[high] = arr[high], arr[rand_index]

    pivot = arr[high]

    for i in range(low, high):
        if (arr[i] < pivot):
            arr[low], arr[i] = arr[i], arr[low]
            low += 1

    arr[low], arr[high] = arr[high], arr[low]

    return low


print(find_kth_smallest([7, 10, 4, 3, 20, 15], 0, 5, 3))
print(find_kth_smallest([10, 4, 5, 8, 6, 11, 26], 0, 6, 3))
print(find_kth_smallest([10, 4, 5, 8, 6, 11, 26], 0, 6, 9))
print(find_kth_smallest([5], 0, 0, 1))

Output:

7
6
-1
5

Complexity:



2. Find Kth Largest Element in Unsorted Array

Problem:

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

# Examples:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Approach: Use Randomized QuickSelect
Implementation:

Code:

from typing import List
import random


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.find_kth_smallest_element(nums, 0, len(nums) - 1, len(nums) - k + 1)

    def find_kth_smallest_element(self, arr, low, high, k):
        if (low <= high):
            pat_index = self.partition(arr, low, high)
            if (pat_index == k - 1):
                return arr[k - 1]
            elif (pat_index > k - 1):
                return self.find_kth_smallest_element(arr, low, pat_index - 1, k)
            else:
                return self.find_kth_smallest_element(arr, pat_index + 1, high, k)

    def partition(self, arr, low, high):
        rand_index = random.randint(low, high)
        arr[high], arr[rand_index] = arr[rand_index], arr[high]

        pivot = arr[high]

        for i in range(low, high):
            if arr[i] < pivot:
                arr[i], arr[low] = arr[low], arr[i]
                low += 1

        arr[low], arr[high] = arr[high], arr[low]
        return low


s = Solution()
assert s.findKthLargest([1, 2, 3, 4, 5], 1) == 5
assert s.findKthLargest([1, 2, 3, 4, 5], 1) == 5
assert s.findKthLargest([1, 2, 3, 4, 5], 5) == 1
assert s.findKthLargest([2, 2, 2, 2, 2], 2) == 2
assert s.findKthLargest([3, 2, 1, 5, 6, 4], 2) == 5
assert s.findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4

Complexity:



3. Find K Closest Points to Origin

Problem:

Given list of points on the plane. Find the k closest points to the origin. You may return the answer in any order.

Examples:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)
Approach-1: Use Sorting
Approach-2: Use Randomized QuickSelect
Implementation:

Code:

from typing import List
import random


class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        return self._kClosestUtil(points, 0, len(points)-1, K)

    def _kClosestUtil(self, points, low, high, K):
        if low <= high:
            partition_index = self._partition(points, low, high)
            if (partition_index == K - 1):
                return points[:K]
            elif (partition_index > K - 1):
                return self._kClosestUtil(points, low, partition_index - 1, K)
            else:
                return self._kClosestUtil(points, partition_index + 1, high, K)

    def _dist_from_origin(self, point):
        return point[0]*point[0] + point[1]*point[1]

    def _partition(self, points, low, high):
        rand_index = random.randint(low, high)
        points[rand_index], points[high] = points[high], points[rand_index]

        pivot = points[high]
        pivot_dist_origin = self._dist_from_origin(pivot)
        for i in range(low, high):
            if (self._dist_from_origin(points[i]) < pivot_dist_origin):
                points[low], points[i] = points[i], points[low]
                low += 1

        points[low], points[high] = points[high], points[low]
        return low


s = Solution()
print(s.kClosest([[1, 3], [-2, 2]], 1))
print(s.kClosest([[3, 3], [5, -1], [-2, 4]], 2))
print(s.kClosest([[3, 3], [5, -1], [-2, 4]], 3))

Output:

[[-2, 2]]
[[3, 3], [-2, 4]]
[[3, 3], [-2, 4], [5, -1]]

Complexity: