การหา Element ที่ n ที่น้อยที่สุดใน 2D Sorted Array ใน JavaScript

ปัญหา

หา k-th smallest element ใน matrix ที่แต่ละ row และ column เรียงเพิ่ม

ตัวอย่าง

matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 5 -> 11

ตัวอย่างโค้ด

const arr = [
  [1, 5, 9],
  [10, 11, 13],
  [12, 13, 15]
];
const num = 5;

const kthSmallest = (arr = [], num = 1) => {
  let low = arr[0][0];
  let high = arr[arr.length-1][arr[0].length-1] + 1;
  while (low < high) {
    let mid = low + Math.floor((high-low)/2);
    let count = 0;
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < arr.length; j++) {
        if (arr[i][j] <= mid) count++;
        else break;
      }
    }
    if (count < num) low = mid + 1;
    else high = mid;
  }
  return low;
};

console.log(kthSmallest(arr, num));

คำอธิบาย

Binary search on value range: low = min element, high = max element + 1

นับจำนวน elements <= mid โดยใช้ property sorted row/col (break early)

ปรับ low/high ตาม count เทียบกับ k

Time: O(n log(max-min)) สำหรับ n x n matrix

Optimization: นับได้ O(n) เริ่มจากมุมบนขวา/ล่างซ้าย

ผลลัพธ์

11