การนับจำนวนตัวเลขที่น้อยกว่าด้านขวาในอาร์เรย์ด้วย JavaScript

ปัญหา

สร้างอาร์เรย์ที่แต่ละ index i เก็บจำนวน elements ทางขวา (j > i) ที่มีค่าน้อยกว่า arr[i]

ตัวอย่าง

arr = [4, 7, 1, 4, 7, 5, 3, 8, 9]
output: [2, 4, 0, 1, 2, 1, 0, 0, 0]

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

const arr = [4, 7, 1, 4, 7, 5, 3, 8, 9];

const countSmaller = (array = [], num) => array.reduce((acc, val) => {
  if (val < num) {
    acc++;
  }
  return acc;
}, 0);

const smallerArray = (arr = []) => {
  const res = [];
  for (let i = 0; i < arr.length; i++) {
    const el = arr[i];
    res[i] = countSmaller(arr.slice(i, arr.length), el);
  }
  return res;
};

console.log(smallerArray(arr));

ผลลัพธ์

[2, 4, 0, 1, 2, 1, 0, 0, 0]

คำอธิบาย

Naive approach: สำหรับแต่ละ i slice อาร์เรย์ด้านขวา และ count ค่าน้อยกว่า arr[i]

Time: O(n²), Space: O(n)

Optimization: ใช้ Binary Indexed Tree (Fenwick Tree) หรือ Merge Sort แบบนับ inversions -> O(n log n)

LeetCode 315 Count of Smaller Numbers After Self