หา Index ของเอลีเมนต์ซ้ำตัวแรก - JavaScript

หา Index แรกของเอลีเมนต์ที่ปรากฏมากกว่า 1 ครั้ง ในอาร์เรย์ (First Duplicate Index) โดยไม่ใช้ Extra Space

ตัวอย่าง

[0, 1, 1, 2, 3, 4, 4, 5] → Index 1 (ค่า 1 ซ้ำครั้งแรก)

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

const firstRedundant = arr => {
  for (let i = 0; i < arr.length; i++) {
    if (arr.lastIndexOf(arr[i]) !== i) {
      return i;
    }
  }
  return -1;
};

console.log(firstRedundant([0, 1, 1, 2, 3, 4, 4, 5]));

ผลลัพธ์

1

Complexity

• Time: O(n²) - lastIndexOf เป็น O(n) เรียก n ครั้ง
• Space: O(1) - ไม่ใช้ Extra Space

เวอร์ชัน O(n) Time / O(n) Space (เร็วกว่า)

const firstRedundant = arr => {
  const seen = new Set();
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(arr[i])) return i;
    seen.add(arr[i]);
  }
  return -1;
};

แลก Space 換 Time ใช้ Set ตรวจสอบ O(1)