DSA Series: Quick Select and Finding Closest Points

This week, I’ll be showing you how to use Quick Select! It’s an extremely powerful algorithm that you’ll definitely want to remember. Then, I’ll use it to solve this problem — K Closest Points to Origin.

Quick Select

What is it

Quick Select is a divide-and-conquer algorithm used to find the kth element(s) of a list of elements. The algorithm is done by partitioning around a pivot points until the pivot ends at the k+1 index. It is at that point when we know we have our k elements to the left of the pivot.

The algorithm has time and space advantages over other kth selection algorithms such as using a heap or sorting. Like quick sort, it has very good average case performance that is actually linear which makes it extremely powerful. In addition, quick sort is done in-place which saves space over using a data structure like a heap.

Read more here!

How to implement it

Here’s the general process:

1. Pick a pivot point.
2. Move all elements that are smaller than or equal to the pivot to the left and vice versa.
3. If the pivot value ends at the index k, then you have found the kth element(s) in the positions before k.
4. If not, perform quick select on the left partition or right partition depending on if you need to select more or less elements.

Check it out: Quickselect Algorithm — GeeksforGeeks

When to use

• Finding any kth element or top k elements

K Closest Points to Origin

Problem Summary

Given an unordered list of points — points — where each point is a list of its x and y coordinates, find the k closest points to the origin ( [0,0] ).

Problem Exploration

There’s actually not much to explore here since this problem is a pretty explicit use of the quick select algorithm but here I go:

1. I know I will need to some distance_from_origin function to compare the elements to each other.
2. I need to use one of the common kth selection algorithms.

#1 — I can write a method calculating the distance from origin using (x²+y²) — skip taking the square root to save the need to use the Math package.

#2 — Given no additional constraints, I’ll pick the algorithms with the best time complexity which is using quick select. Not much to it besides knowing this algorithm exists — but now you do too :).

Time and Space Complexity

Time: O( n ) — average case

Each partition is linear — O( n ) — so on average, if good pivots are chosen, we ignore the constant amount of partitions needed.

Space: O( n )

Space for original list of points.

Code

Conclusion

Now you’ve added another extremely powerful algorithm into your arsenal! Be sure to think about using Quick Sort any time you need to find some kth element in a list.