Shortest Distance to Target Color ใน C++ : หาระยะทางสั้นที่สุดไปยังสีเป้าหมาย

ให้ Array colors มีค่า 1, 2, 3 (แทน 3 สี) และ Queries หลายคำถาม แต่ละ Query เป็น [index, targetColor] หา **ระยะทางสั้นที่สุด** จาก index ไปยังตำแหน่งที่มี targetColor ถ้าไม่มีสีนั้นเลย คืน -1

ตัวอย่าง

colors = [1,1,2,1,3,2,2,3,3]
queries = [[1,3], [2,2], [6,1]]

Query [1,3]: Index 1 (ค่า 1) -> 3 ใกล้สุดอยู่ Index 4 (ค่า 3) ระยะ 3
Query [2,2]: Index 2 (ค่า 2) -> 2 ใกล้สุดอยู่ Index 2 เอง ระยะ 0
Query [6,1]: Index 6 (ค่า 2) -> 1 ใกล้สุดอยู่ Index 3 (ค่า 1) ระยะ 3

Output: [3, 0, 3]

แนวทาง: Preprocess Index Positions + Binary Search

1. สร้าง Array of Vectors idx[4] เก็บ Index ของแต่ละสี (1,2,3)
2. แต่ละ Query:
   • Binary Search (lower_bound) ใน idx[c] หาตำแหน่งแรกที่ ≥ x
   • เปรียบเทียบระยะทางกับ ตำแหน่งที่เจอ (it) และ ตำแหน่งก่อนหน้า (it-1) (ถ้ามี)
   • เลือก Min Distance

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        // 1. Preprocess: เก็บ Index ของแต่ละสี
        vector<vector<int>> idx(4); // 1,2,3
        for (int i = 0; i < colors.size(); i++) {
            idx[colors[i]].push_back(i);
        }

        vector<int> ret;
        for (auto& q : queries) {
            int x = q[0];      // Query index
            int c = q[1];      // Target color

            if (idx[c].empty()) { // ไม่มีสีนี้เลย
                ret.push_back(-1);
                continue;
            }

            // 2. Binary Search หาตำแหน่งแรกที่ >= x
            auto it = lower_bound(idx[c].begin(), idx[c].end(), x);
            int pos = it - idx[c].begin();

            int op1 = INT_MAX, op2 = INT_MAX;

            if (pos == idx[c].size()) { // x มากกว่าทุก Index ของสี c -> เอาตัวสุดท้าย
                op1 = abs(x - idx[c].back());
            } else if (pos == 0) {      // x น้อยกว่าทุก Index -> เอาตัวแรก
                op1 = abs(x - idx[c][0]);
            } else {                    // x อยู่กลาง -> เปรียบเทียบ pos และ pos-1
                op1 = abs(x - idx[c][pos]);
                op2 = abs(x - idx[c][pos - 1]);
            }
            ret.push_back(min(op1, op2));
        }
        return ret;
    }
};

Input / Output

Input:  [1,1,2,1,3,2,2,3,3] [[1,3],[2,2],[6,1]]
Output: [3,0,3]

ความซับซ้อน (Complexity)

• Preprocess: O(N)
• Per Query: O(log M) — M = จำนวน Index ของสีนั้น (Binary Search)
• Total: O(N + Q log M) — เหมาะสำหรับ Queries เยอะ
• Space: O(N)

เทคนิค Offline Preprocessing + Binary Search คลาสสิกสำหรับโจทย์ Nearest Element Queries ครับ