007 — K Closest Points to Origin¶

Source¶

Original source: Classic top-K by distance
Platform: LeetCode — https://leetcode.com/problems/k-closest-points-to-origin/
Topic: heap / priority queue
Difficulty: Medium
Pattern: Top-K (max-heap of size k)
Basic idea inherited from: 08 top-K pattern — k smallest চাইলে size-k max-heap

1. Problem in simple words¶

সমতলে কতগুলো বিন্দু (x, y) দেওয়া আছে আর একটা সংখ্যা k। তোমাকে origin (0, 0)-এর সবচেয়ে কাছের k-টা বিন্দু বের করতে হবে। দূরত্ব মাপা হয় সাধারণ Euclidean নিয়মে (sqrt(x² + y²))। উত্তরের order matter করে না — শুধু সঠিক k-টা বিন্দু চাই।

points = [[1, 3], [-2, 2]],  k = 1  ->  [[-2, 2]]   ( (-2,2) origin-এর কাছে)

2. Which basic idea does this inherit from?¶

ভিত হলো top-K pattern, কিন্তু "smallest" দিকে। #5/#6-এ k largest চাইতাম, তাই size-k min-heap। এখানে k smallest (নিকটতম) চাই, তাই size-k max-heap — top-এ থাকে "club-এর সবচেয়ে দূরের member", আর নতুন বিন্দু তাকে হারালেই ঢোকে। এটাই 08-এর top-K-র আয়না-রূপ।

3. What is the hidden math or logic?¶

দুটো ছোট logic। (1) distance compare-এ sqrt লাগে না — যেহেতু sqrt monotonic, x²+y² দিয়ে compare করলেই order একই থাকে, তাই squared distance যথেষ্ট (faster, কোনো floating error নেই)। (2) k nearest = সবচেয়ে ছোট k-টা distance, যা একটা top-K problem distance-কে key ধরে।

4. Which data structure is needed?¶

একটা size-k max-heap যেখানে entry হয় (squared_distance, point)। heapq min-heap, তাই max-heap বানাতে distance negate করি — তখন top-এ থাকে "club-এর সবচেয়ে দূরের member" (সবচেয়ে বড় distance)।

5. Why this data structure fits¶

size-k max-heap-এর top সবসময় club-এর দূরতম বিন্দু। নতুন বিন্দু শুধু এই দূরতমের সাথে লড়ে — কাছে হলে দূরতম pop, নতুন push। প্রতিটা op O(log k), মোট O(n log k); memory O(k)। n বিশাল কিন্তু k ছোট হলে full sort (O(n log n))-এর চেয়ে অনেক সস্তা, আর stream-এও চলে।

6. Real-life analogy¶

ভাবো একটা food-delivery app origin (তোমার বাসা)-র কাছের k-টা রেস্তোরাঁ দেখাতে চায়। সে একটা ছোট তালিকা রাখে যার "সবচেয়ে দূরের" রেস্তোরাঁটা সামনে দাঁড়ানো (max-heap top)। নতুন কোনো রেস্তোরাঁ যদি ওই দূরতমের চেয়ে কাছে হয়, সে ঢোকে, দূরতমটা বাদ। সেই "সবচেয়ে দূরেরটা চট করে বাদ দাও" যন্ত্রটাই size-k max-heap।

7. Visual explanation¶

points = [[1,3],[-2,2],[2,-2],[5,5]], k = 2। squared distance = x²+y²। size-2 max-heap (top = দূরতম):

points & dist²:  [1,3]->10   [-2,2]->8   [2,-2]->8   [5,5]->50

push [1,3] (10)     -> heap top dist² = 10        (size < k)
push [-2,2] (8)     -> heap {10, 8}, top = 10     (size == k)
[2,-2] (8): 8 < 10? হ্যাঁ -> pop 10, push 8 -> heap {8, 8}, top = 8
[5,5] (50): 50 < 8? না   -> reject

heap-এ বিন্দু: [-2,2], [2,-2]  ->  উত্তর (order free)

8. Example input and output¶

Input : points = [[1,3],[-2,2]], k = 1            -> Output: [[-2,2]]
Input : points = [[3,3],[5,-1],[-2,4]], k = 2     -> Output: [[3,3],[-2,4]]
Input : points = [[0,1],[1,0]], k = 2             -> Output: [[0,1],[1,0]]
Input : points = [[1,1]], k = 1                    -> Output: [[1,1]]

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা বিন্দুর distance বের করো, পুরো list distance দিয়ে ascending sort করো, প্রথম k-টা নাও।

[[1,3],[-2,2],[5,5]] -> dist² [10,8,50] -> sort -> [-2,2],[1,3],[5,5] -> প্রথম k

10. Why brute force is slow¶

পুরো list sort মানে O(n log n), অথচ শুধু নিকটতম k-টা লাগছে — পুরো order না। k যখন ছোট (k=5, n=10⁶), full sort বিশাল অপচয়। size-k heap সেই অপ্রয়োজনীয় কাজ এড়িয়ে O(n log k)-তে নামায়। (তবে brute force সঠিক উত্তর দেয়।)

11. Key observation¶

মূল observation দুটো: (1) compare-এ squared distance যথেষ্ট, sqrt বাদ; (2) নিকটতম k জানতে শুধু সবচেয়ে কাছের k-টা track করলেই চলে — তাদের মধ্যে সবচেয়ে দূরেরটা একটা size-k max-heap-এর top-এ বসে দারোয়ানি করে।

12. Optimized intuition¶

প্রতিটা বিন্দুর জন্য (-dist², point) (negate করে max-heap) push করো; size k ছাড়ালে top (negated মানে সবচেয়ে বড় dist²) pop করো। শেষে heap-এ নিকটতম k-টা বিন্দু। প্রতিটা op O(log k), মোট O(n log k)।

13. Thinking tweak¶

মোচড়: "k nearest খুঁজছি" শুনে ভাবো "একটা size-k club রাখছি, দরজায় দাঁড়ানো দূরতম member, আর নতুন কেউ তাকে হারালে ঢোকে।" মনে রেখো আয়না-নিয়ম: k smallest চাইলে max-heap, k largest চাইলে min-heap — top-এ সবসময় থাকে "যাকে সবার আগে বের করে দিতে পারি"।

14. Step-by-step dry run¶

Input points = [[1,3],[-2,2],[2,-2],[5,5]], k = 2 (max-heap, key = −dist²):

[1,3] dist² 10 → push (−10, [1,3]) → heap {[1,3]} (size 1 < 2)
[-2,2] dist² 8 → push (−8, [-2,2]) → heap {1,3, -2,2}, top dist² = 10
[2,-2] dist² 8 → 8 < top 10? হ্যাঁ → pop [1,3], push [2,-2] → heap {-2,2, 2,-2}, top = 8
[5,5] dist² 50 → 50 < 8? না → reject
heap = {[-2,2], [2,-2]} → return (order free)

15. Python solution¶

import heapq

def k_closest(points, k):
    club = []                              # size-k max-heap of (-dist2, x, y)
    for x, y in points:
        dist2 = x * x + y * y              # squared distance: sqrt লাগে না
        heapq.heappush(club, (-dist2, x, y))   # negate: max-heap, top = দূরতম
        if len(club) > k:                  # k ছাড়ালে দূরতম বাদ
            heapq.heappop(club)
    return [[x, y] for _, x, y in club]    # নিকটতম k-টা বিন্দু

# ---- tests ----
def norm(pts):
    return sorted([p[0] * p[0] + p[1] * p[1] for p in pts])   # order-free check

assert norm(k_closest([[1, 3], [-2, 2]], 1)) == norm([[-2, 2]])
assert norm(k_closest([[3, 3], [5, -1], [-2, 4]], 2)) == norm([[3, 3], [-2, 4]])
assert norm(k_closest([[0, 1], [1, 0]], 2)) == norm([[0, 1], [1, 0]])
assert norm(k_closest([[1, 1]], 1)) == norm([[1, 1]])
print("সব test pass!")

16. Line-by-line code explanation¶

dist2 = x * x + y * y — squared distance; sqrt বাদ দিলেও order একই, faster আর exact।
heapq.heappush(club, (-dist2, x, y)) — distance negate করে max-heap; top-এ সবচেয়ে বড় dist² (দূরতম)।
if len(club) > k: — size k ছাড়ালেই দূরতমকে বের করার সময়।
heapq.heappop(club) — top (negated সবচেয়ে বড় dist²) pop — club-এ সবসময় নিকটতম k।
return [[x, y] for _, x, y in club] — heap-এ বাকি k-টা থেকে শুধু বিন্দুগুলো।
test-এর norm — order matter করে না, তাই dist² sort করে তুলনা (একই বিন্দু-সেট হলে dist²-গুলোও মিলবে)।

17. Output walkthrough¶

k_closest([[1,3],[-2,2],[2,-2],[5,5]],2) section 14 মেনে {[-2,2],[2,-2]} দেয়। test-এ order-free তুলনা করি norm দিয়ে: [[1,3],[-2,2]],1 → নিকটতম [-2,2] (dist² 8 < 10)। [[3,3],[5,-1],[-2,4]],2 → dist² 18,26,20 → নিকটতম [3,3],[-2,4]। বাকি দুটোও সরাসরি। চারটে assert pass করার পরে print হয়: সব test pass!।

18. Time complexity¶

O(n log k) — প্রতিটা বিন্দুতে বড়জোর একটা O(log k) push আর একটা pop। full sort (O(n log n))-এর চেয়ে সস্তা যখন k ≪ n।

19. Space complexity¶

O(k) — heap-এ কখনো k-টার বেশি বিন্দু থাকে না (output বাদ দিলে)। n বিশাল হলেও memory শুধু k-তে বাঁধা — stream-friendly।

20. Common mistakes¶

distance-এ sqrt ব্যবহার করা — অপ্রয়োজনীয় slow আর floating-point error ডেকে আনে; squared distance-ই যথেষ্ট।
min-heap ব্যবহার করা (negate না করে) — তখন তুমি নিকটতমকে বের করে দিচ্ছ, দূরতমকে রাখছ — উল্টো উত্তর।
tuple-এ শুধু (-dist2, point_list) রাখা — দুই বিন্দুর dist² সমান হলে Python list compare করতে গিয়ে error দিতে পারে; তাই (-dist2, x, y) রাখা নিরাপদ।

21. Which basic problem this inherits from¶

ভিত্তি 08 top-K pattern (patterns.md Pattern 1), আর #5/#6-এর top-K কঙ্কাল — পার্থক্য শুধু এখানে "smallest" দিকে, তাই max-heap, আর key হলো computed distance। compare-এ squared-distance trick-টা একটা ছোট math observation।

22. Similar harder problems¶

Kth Largest Element in an Array — https://leetcode.com/problems/kth-largest-element-in-an-array/ (এই tracker-এর #5)
Top K Frequent Elements — https://leetcode.com/problems/top-k-frequent-elements/ (#6)
Kth Smallest Element in a Sorted Matrix — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/ (#12)

23. Pattern learned¶

Top-K smallest via size-k max-heap: k nearest/smallest চাইলে size-k max-heap রাখো (key negate করে); top = দূরতম/সবচেয়ে বড়, নতুন entry তাকে হারালেই ঢোকে। compare-এ squared distance যথেষ্ট। আয়না-নিয়ম মনে রেখো: smallest↔max-heap, largest↔min-heap।

24. Final summary¶

ভবিষ্যতের আমাকে: "k closest / k smallest by some score" = size-k max-heap of (-score, …)। top = দূরতম, হারলে বাদ। distance হলে sqrt বাদ দিয়ে x²+y² দিয়েই compare করো। মনে রেখো — largest আর smallest-এর জন্য heap-এর দিক উল্টো, কিন্তু কঙ্কাল হুবহু এক।

25. JavaScript solution (with test cases)¶

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

// Node-এ built-in heap নেই। key দিয়ে compare করা একটা minimal MaxHeap
// (top = সবচেয়ে বড় key); এখানে item = [x, y], key = squared distance
class MaxHeap {
  constructor(keyFn) { this.a = []; this.key = keyFn; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(item) {
    const a = this.a, k = this.key; a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (k(a[p]) >= k(a[i])) break;        // parent বড় হলে থামো (max-heap)
      [a[p], a[i]] = [a[i], a[p]]; i = p;
    }
  }
  pop() {
    const a = this.a, k = this.key, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2; let big = i;
        if (l < a.length && k(a[l]) > k(a[big])) big = l;
        if (r < a.length && k(a[r]) > k(a[big])) big = r;
        if (big === i) break;
        [a[big], a[i]] = [a[i], a[big]]; i = big;
      }
    }
    return top;
  }
}

function kClosest(points, k) {
  const dist2 = ([x, y]) => x * x + y * y;     // squared distance: sqrt লাগে না
  const club = new MaxHeap(dist2);             // top = club-এর দূরতম বিন্দু
  for (const p of points) {
    club.push(p);
    if (club.size > k) club.pop();             // k ছাড়ালে দূরতম বাদ
  }
  return club.a.slice();                        // নিকটতম k-টা বিন্দু (order free)
}

// order matter করে না, তাই dist²-গুলো sort করে তুলনা
const norm = (pts) => pts.map(([x, y]) => x * x + y * y).sort((a, b) => a - b);
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);

// ---- test cases ----
assert(eq(norm(kClosest([[1, 3], [-2, 2]], 1)), norm([[-2, 2]])), "k=1");
assert(eq(norm(kClosest([[3, 3], [5, -1], [-2, 4]], 2)), norm([[3, 3], [-2, 4]])), "k=2");
assert(eq(norm(kClosest([[0, 1], [1, 0]], 2)), norm([[0, 1], [1, 0]])), "both");
assert(eq(norm(kClosest([[1, 1]], 1)), norm([[1, 1]])), "একক");
console.log("সব JS test pass!");

JS টীকা: JS/Node-এ built-in priority queue নেই, তাই এখানে একটা key-ভিত্তিক MaxHeap লিখলাম — keyFn দিয়ে যেকোনো item-কে তার তুলনা-key (এখানে squared distance) দেওয়া যায়, Python-এ যেমন tuple-এ (-dist2, x, y) রেখে min-heap ব্যবহার করা হতো তার পরিচ্ছন্ন বিকল্প। sqrt বাদ দিয়ে x*x + y*y দিয়েই compare করি — order একই, faster, floating error নেই। order matter না করায় test-এ norm দিয়ে order-free তুলনা।

26. TypeScript solution (with test cases)¶

type Point = [number, number];

class MaxHeap<T> {
  private a: T[] = [];
  constructor(private key: (x: T) => number) {}
  get size(): number { return this.a.length; }
  toArray(): T[] { return this.a.slice(); }
  push(item: T): void {
    const a = this.a, k = this.key; a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (k(a[p]) >= k(a[i])) break;
      [a[p], a[i]] = [a[i], a[p]]; i = p;
    }
  }
  pop(): T {
    const a = this.a, k = this.key, top = a[0], last = a.pop() as T;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2; let big = i;
        if (l < a.length && k(a[l]) > k(a[big])) big = l;
        if (r < a.length && k(a[r]) > k(a[big])) big = r;
        if (big === i) break;
        [a[big], a[i]] = [a[i], a[big]]; i = big;
      }
    }
    return top;
  }
}

function kClosest(points: Point[], k: number): Point[] {
  const dist2 = ([x, y]: Point): number => x * x + y * y;
  const club = new MaxHeap<Point>(dist2);
  for (const p of points) {
    club.push(p);
    if (club.size > k) club.pop();
  }
  return club.toArray();
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const norm = (pts: Point[]): number[] => pts.map(([x, y]) => x * x + y * y).sort((a, b) => a - b);
const eq = (a: number[], b: number[]): boolean => a.length === b.length && a.every((v, i) => v === b[i]);

expect(eq(norm(kClosest([[1, 3], [-2, 2]], 1)), norm([[-2, 2]])), "1");
expect(eq(norm(kClosest([[3, 3], [5, -1], [-2, 4]], 2)), norm([[3, 3], [-2, 4]])), "2");
expect(eq(norm(kClosest([[0, 1], [1, 0]], 2)), norm([[0, 1], [1, 0]])), "both");
expect(eq(norm(kClosest([[1, 1]], 1)), norm([[1, 1]])), "একক");
console.log("সব TS test pass!");

TS টীকা: MaxHeap<T> generic — যেকোনো type-এর item রাখতে পারে, শুধু একটা key: (x: T) => number দিলেই হয়। এখানে T = Point ([number, number] tuple type), তাই compiler নিশ্চিত করে heap-এ শুধু সঠিক আকারের বিন্দুই ঢোকে আর dist2-এ destructuring নিরাপদ। generic heap একবার লিখে পরের অনেক top-K problem-এ পুনর্ব্যবহার করা যায়।

27. কোথায় কাজে লাগে (real-world use)¶

Location-based services: ব্যবহারকারীর অবস্থান থেকে নিকটতম k-টা দোকান/ATM/driver খুঁজে দেখানো — ride-hailing, delivery, maps।
Recommendation / similarity: একটা item-এর সবচেয়ে "কাছের" (similar) k-টা item বের করা, যেখানে distance = feature-space দূরত্ব।
k-Nearest Neighbors (ML): classification/regression-এ একটা point-এর nearest k প্রতিবেশী খোঁজা — এই heap-চাল তার মূল।
Spatial indexing / clustering: বড় point-set থেকে একটা কেন্দ্রের আশেপাশের k-টা বিন্দু বের করা, পুরো set sort না করেই।
Anomaly / outlier triage: একটা reference থেকে সবচেয়ে দূরের বা সবচেয়ে কাছের k-টা data point বেছে নেওয়া।

মূল সুর: "একটা score/distance অনুযায়ী top বা bottom-k" দরকার হলে size-k heap (smallest চাইলে max-heap, largest চাইলে min-heap) — আর distance-এ sqrt বাদ দিয়ে squared দিয়েই compare করো।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।