K Closest Points to the Origin | Brute Force, Sorting, Heaps, & Reduction

Visit Our Website: interviewpen.c...
Join Our Discord (24/7 help): / discord
Join Our Newsletter - The Blueprint: theblueprint.d...
Like & Subscribe: / @interviewpen
This is an example of a full video available on interviewpen.com. Check out our website to find more premium content like this!
Problem Statement:
Given an array of points `points` where points[i] = [xᵢ, yᵢ] represents a point on a [Cartesian plane](en.wikipedia.o...) and an integer `k`, return the `k` closest points to the origin (0, 0).
Point Distance: The distance between any two points A (point 1) & B (point 2) is given by the [Euclidean distance](en.wikipedia.o...) → sqrt((x₁ - x₂)² + (y₁ - y₂)²)
You may return the `k` closest points in any order.
Table of Contents:
0:00 - Problem Introduction
0:44 - Point-to-Point Distance
3:00 - Visit interviewpen.com
3:19 - Initial Thoughts
04:55 - Reducing to “Find K Smallest Items”
05:41 - Continuing On
06:02 - Picking the K Smallest Distances
06:33 - Implementation: Picking w/ Scans
09:02 - Complexities
09:54 - Implementation: Sorting → Plucking 1st k Items
10:47 - Complexities
11:01 - Using a Special Structure
11:53 - Using a Min Heap
12:43 - Using a Max Heap
13:44 - Implementation: Max Heap → Retain k Items
15:11 - Complexities
16:17 - Wrap Up
Erratum:
0:00 - The point written (0, 5) is (5, 0). This is verbally corrected at 2:41.
Socials:
Twitter: / interviewpen
Twitter (The Blueprint): / theblueprintdev
LinkedIn: / interviewpen
Website: interviewpen.c...

[@interviewpen]

Thanks for watching! (see our description for an Erratum) Visit interviewpen.com/? for more great Data Structures & Algorithms + System Design content 🧎

[@ericmargolis1852]

Really good explanation and walkthrough, thank you!

[@interviewpen]

Thanks!

[@mav31415]

nit: you can skip the square root and you'd get the same ordering.

[@interviewpen]

makes sense, as we're just interested in a raw comparable magnitude vs. the actual distance -> if both line up then we solve the same problem indeed