Visit Our Website: interviewpen.com/?...
Join Our Discord (24/7 help): / discord
Join Our Newsletter - The Blueprint: theblueprint.dev/subscribe
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.org/wiki/Cartesi...) 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.org/wiki/Euclide...) → 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.com/?...