082 — Pair with Difference K¶

081-এ দুই আঙুল দুই প্রান্ত থেকে ভেতরে এসেছিল। এখানে মোচড়টা ছোট কিন্তু গুরুত্বপূর্ণ — এবার দুই আঙুল একই দিকে ছুটবে, একজন আরেকজনকে তাড়া করে। কেন difference খুঁজতে opposite pointers চলে না, আর same-direction কেন স্বাভাবিক — সেটাই এখানে শিখবে। ধীরে পড়ো, পার্থক্যটা অনুভব করো।

Problem link ও উৎস

Original source: LeetCode K-diff Pairs in an Array
Platform: LeetCode — https://leetcode.com/problems/k-diff-pairs-in-an-array/
Topic: Two pointers → same-direction scan on sorted array
Difficulty: Medium
Pattern: same-direction pointers (পেছনেরটা সামনেরটাকে তাড়া করে)
Basic idea inherited from: 081 — Two Sum Sorted (opposite থেকে same-direction-এ মোচড়)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

একটা array আর একটা সংখ্যা k (≥ 0) দেওয়া। গুনতে হবে কতগুলো আলাদা (unique) জোড়া (a, b) আছে যাদের |a - b| == k। জোড়া মানে মানের জোড়া, index-এর নয় — (1, 3) আর (3, 1) একই জোড়া, একবারই গুনবে।

দুটো ক্ষেত্রে সাবধান: k == 0 হলে জোড়া মানে "একই সংখ্যা অন্তত দুবার আছে" এমন distinct মান; আর duplicate value থাকলেও প্রতিটা unique জোড়া একবারই গোনা।

Input ও output¶

উদাহরণ

a                     k   ->  count   (কোন জোড়া)
------------------------------------------------
[3, 1, 4, 1, 5]       2   ->  2       (1,3) ও (3,5)
[1, 2, 3, 4, 5]       1   ->  4       (1,2)(2,3)(3,4)(4,5)
[1, 3, 1, 5, 4]       0   ->  1       (1,1) — 1 দুবার আছে
[1, 2, 4, 4, 3, 3]    2   ->  2       (1,3) ও (2,4)
[1, 2, 3, 4]          3   ->  1       (1,4)
[1, 1, 1, 1]          0   ->  1       শুধু (1,1)

Edge case: k == 0 মানে একই মানের জোড়া (duplicate আছে কিনা); k < 0 হয় না (difference-এর absolute value)।

চেনা উদাহরণে বোঝা¶

ভাবো একটা দৌড়ের ট্র্যাকে দুজন দৌড়বিদ — দুজনেই একই দিকে দৌড়ায়, কেউ পেছনে ফেরে না। তুমি চাও তাদের মাঝের ফারাক ঠিক k মিটার হোক।

ফারাক k-এর কম? → সামনের জন আরেকটু এগোক (ফারাক বাড়বে) → j++
ফারাক k-এর বেশি? → পেছনের জন এগিয়ে আসুক (ফারাক কমবে) → i++

দুজনেই শুধু সামনে যায়, কেউ পেছায় না — তাই মোট দৌড় সীমিত। এই "কেউ পিছায় না" বৈশিষ্ট্যই O(n)-এর গ্যারান্টি।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা সরাসরি 081 — Two Sum Sorted-এর কাঁধে। 081-এ আমরা sum ধরেছিলাম, এখানে difference। কিন্তু মোচড়টা মৌলিক:

Sum খুঁজতে: এক প্রান্ত বড় + আরেক প্রান্ত ছোট ভালো জোটে → তাই opposite pointers
Difference খুঁজতে: দুটো কাছাকাছি সংখ্যার ফারাক — দুই প্রান্ত থেকে চাপলে সম্পর্কটা গোলমেলে → তাই same-direction pointers

একই pointer-হাতিয়ার, কিন্তু "কোন দিকে চাপলে target-এর দিকে যাব" সেই বিচার বদলে গেল। 081 আর 082 পাশাপাশি পড়লে এই দিকনির্ণয়ের শিক্ষাটা গেঁথে যায়।

ভেতরের অঙ্ক¶

মূল idea আবারো monotonicity — কিন্তু difference-এর জন্য। Array sorted হলে দুটো pointer i < j-এ a[j] - a[i] কীভাবে বদলায়:

j ডানে সরালে (a[j] বড় হয়) → difference বাড়ে
i ডানে সরালে (a[i] বড় হয়) → difference কমে

তাই difference-ও একটা "নব" — দুই pointer একই দিকে এগিয়েই target difference ধরা যায়।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

সরল পথ — সব জোড়া দেখে set-এ unique জোড়া জমানো:

Python

def k_diff_brute(a, k):
    n = len(a)
    seen = set()
    for i in range(n):
        for j in range(i + 1, n):
            if abs(a[i] - a[j]) == k:
                seen.add((min(a[i], a[j]), max(a[i], a[j])))
    return len(seen)

set ব্যবহার করছি যাতে একই জোড়া বারবার গোনা না হয়। ঠিক উত্তর দেয়, sorted না হলেও চলে।

কোথায় বেশি কাজ হতে পারে¶

বাইরের আর ভেতরের loop মিলিয়ে প্রায় n²/2 জোড়া। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।

উদাহরণ

n = 100000 হলে:
  brute force  : ~5,000,000,000 জোড়া যাচাই   (O(n²))
  two pointers : sort O(n log n) + scan O(n)   (অনেক দ্রুত)

মূল অপচয়: difference-ও sorted-এ predictable, তবু brute force সব জোড়া ঘাঁটছে।

আরও ভালোভাবে ভাবা¶

মূল insight: sort করে নাও, তারপর দুটো pointer একই দিকে চালাও। sorted-এ a[j] - a[i] monotonic, তাই:

ফারাক k-এর চেয়ে ছোট → j++ (ফারাক বাড়াও)
ফারাক k-এর চেয়ে বড় → i++ (ফারাক কমাও)
সমান → একটা জোড়া গুনে দুজনকেই duplicate পেরিয়ে এগোও

i == j হয়ে গেলে j-কে এক ধাপ এগিয়ে দাও (একই element-এর সাথে নিজের ফারাক ০, যা সাধারণত target নয়; আর index আলাদা রাখাই নিরাপদ)।

ভাবনার পরিবর্তন¶

আসল "আহা!": difference খুঁজতে দুই প্রান্ত থেকে চাপা লাগে না — দুজন একই দিকে দৌড়ালেই হয়, আর কেউ পিছায় না বলে এক pass-এই শেষ।

i আর j দুজনেই জীবনে বড়জোর n বার এগোয়, কেউ ফেরে না → মোট move ≤ 2n → O(n) (sort বাদে)। আর duplicate জোড়া এড়াতে match-এর পরে দুজনকেই সমান-মান পেরিয়ে নেওয়া — এটাই unique গোনার চাবি।

ছবিতে বোঝা¶

a = [1, 3, 5, 9], k = 4 — দুই pointer একই দিকে চলছে:

উদাহরণ

a = [ 1 ,  3 ,  5 ,  9 ]
      i    j                 a[j]-a[i] = 3-1 = 2 < 4  → j++ (সামনেরটা এগোয়)

a = [ 1 ,  3 ,  5 ,  9 ]
      i         j            a[j]-a[i] = 5-1 = 4 == 4 → জোড়া (1, 5)! তারপর এগোই

দুই pointer কখনো ক্রস করে না, দুজনেই বাঁ থেকে ডানে:

উদাহরণ

diff ছোট হলে:  i .. j     →   i ..... j      (j ডানে, ফারাক বাড়ে)
diff বড় হলে :  i .. j     →      i .. j      (i ডানে, ফারাক কমে)
diff == k    :  জোড়া গোনো, তারপর দুজনকেই duplicate পেরিয়ে নাও

ছোট input-এ ধাপে ধাপে¶

a = [3, 1, 4, 1, 5], k = 2। আগে sort → [1, 1, 3, 4, 5]। i, j = 0, 1:

step	i	j	a[i]	a[j]	diff	তুলনা	action
1	0	1	1	1	0	0 < 2	j++
2	0	2	1	3	2	== 2	জোড়া (1,3); i,j duplicate skip → i=2, j=3
3	2	3	3	4	1	1 < 2	j++
4	2	4	3	5	2	== 2	জোড়া (3,5); skip → i=3, j=5(শেষ)

j array পেরিয়ে গেল → থামো। মোট unique জোড়া = 2 → (1,3) ও (3,5)। লক্ষ করো শুরুর duplicate 1 দুটো একই জোড়ায় গোনা হয়নি — skip-এর কাজ এটাই।

কোড ও ব্যাখ্যা¶

Python¶

Python

def k_diff_pairs(a, k):
    """|a-b|==k এমন unique মান-জোড়ার সংখ্যা ফেরত দেয় (k >= 0)।"""
    a = sorted(a)
    n = len(a)
    i, j = 0, 1
    count = 0
    while j < n:
        if i == j:
            j += 1
            continue
        d = a[j] - a[i]
        if d == k:
            count += 1
            # এই মান-জোড়াটা আর গোনা যাবে না — দুই pointer-কে duplicate পার করাই
            vi, vj = a[i], a[j]
            while i < n and a[i] == vi:
                i += 1
            while j < n and a[j] == vj:
                j += 1
            if i >= j:
                j = i + 1
        elif d < k:
            j += 1            # ফারাক ছোট → সামনেরটা এগোক
        else:
            i += 1            # ফারাক বড় → পেছনেরটা এগিয়ে আসুক
    return count


def k_diff_brute(a, k):
    """ধীর reference — সব জোড়া + set দিয়ে unique গোনা।"""
    seen = set()
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if abs(a[i] - a[j]) == k:
                seen.add((min(a[i], a[j]), max(a[i], a[j])))
    return len(seen)


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert k_diff_pairs([3, 1, 4, 1, 5], 2) == 2
assert k_diff_pairs([1, 2, 3, 4, 5], 1) == 4
assert k_diff_pairs([1, 3, 1, 5, 4], 0) == 1
assert k_diff_pairs([1, 2, 4, 4, 3, 3], 2) == 2
assert k_diff_pairs([1, 2, 3, 4], 3) == 1
assert k_diff_pairs([1, 1, 1, 1], 0) == 1
assert k_diff_pairs([1, 2, 3], 5) == 0       # এত বড় ফারাক নেই

# brute force-এর সাথে মিলিয়ে দেখা (random-মতো নানা case)
import itertools, random
random.seed(7)
for _ in range(200):
    arr = [random.randint(0, 8) for _ in range(random.randint(0, 9))]
    for kk in range(0, 6):
        assert k_diff_pairs(arr, kk) == k_diff_brute(arr, kk), (arr, kk)

print(k_diff_pairs([3, 1, 4, 1, 5], 2))   # 2
print(k_diff_pairs([1, 2, 3, 4, 5], 1))   # 4
print(k_diff_pairs([1, 3, 1, 5, 4], 0))   # 1
print("সব test pass!")

কোডের প্রতিটি অংশ¶

উদাহরণ

a = sorted(a)
i, j = 0, 1

আগে sort (difference-এর monotonicity-র জন্য আবশ্যক)। দুই pointer পাশাপাশি শুরু — দুজনেই একই দিকে যাবে।

উদাহরণ

if i == j: j += 1; continue

দুটো pointer এক জায়গায় এলে j-কে এগিয়ে দাও — index আলাদা রাখা (নিজের সাথে নিজের জোড়া এড়াতে)।

উদাহরণ

d = a[j] - a[i]

sorted বলে a[j] >= a[i], তাই এটাই absolute difference।

উদাহরণ

if d == k:
    count += 1
    ... while a[i]==vi: i++ ; while a[j]==vj: j++

মিলে গেলে গুনলাম, তারপর দুই pointer-কে সমান-মান পেরিয়ে নিলাম — যাতে একই মান-জোড়া আবার না গোনা হয় (unique-এর চাবি)।

উদাহরণ

elif d < k: j += 1
else:       i += 1

ফারাক ছোট হলে সামনেরটা এগোক (বাড়াও), বড় হলে পেছনেরটা এগোক (কমাও)। দুজনেই শুধু ডানে।

k_diff_brute test যাচাইয়ের reference; random case-গুলো দুই পথের উত্তর মিলিয়ে দেখে।

Output মিলিয়ে দেখা¶

চালালে ছাপবে:

উদাহরণ

2
4
1
সব test pass!

তিনটা সংখ্যা তিনটা print থেকে: [3,1,4,1,5] k=2 → 2 জোড়া; [1..5] k=1 → 4 জোড়া; [1,3,1,5,4] k=0 → 1 জোড়া (1 দুবার)। তার আগে 200×6 = 1200 random case brute-force-এর সাথে মিলেছে, তাই সব test pass!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n log n) — sort-এর জন্য; এরপর scan O(n) (দুই pointer কেউ পিছায় না, মোট move ≤ 2n)। তাই মোট খরচে sort-ই প্রধান।

অতিরিক্ত জায়গা¶

O(n) যদি sorted(a) নতুন list বানায় (in-place a.sort() করলে O(1) extra, কিন্তু input বদলে যায়)। Scan নিজে O(1) — শুধু i, j, count।

যে ভুলগুলো এড়াতে হবে¶

Sort না করে same-direction চালানো — difference-এর monotonicity sorted ছাড়া থাকে না; ভুল উত্তর আসবে।
Duplicate জোড়া বারবার গোনা — match-এর পরে দুই pointer-কে সমান মান পেরিয়ে না নিলে [1,1,3]-এ (1,3) দুবার গোনা হয়।
k == 0 ভুল সামলানো — তখন জোড়া মানে একই মান অন্তত দুবার; alternative হিসেবে Counter দিয়ে value: count >= 2 গোনা সহজ।
i == j ঘটতে দেওয়া — তখন d == 0, আর k == 0 হলে ভুল করে নিজের সাথে নিজের জোড়া গোনা হয়ে যায়; index আলাদা রাখো।
Hash map পথ ভুলে যাওয়া — k-diff Counter দিয়েও সমাধান হয় (x + k আছে কিনা); two-pointer পথ শুধু একটা রূপ।

শেখা ও পরের অনুশীলন¶

এই ধারণার পরের অনুশীলন¶

LeetCode K-diff Pairs in an Array (https://leetcode.com/problems/k-diff-pairs-in-an-array/) — এই problem-এরই মূল রূপ, edge case সমেত।
LeetCode 3Sum (https://leetcode.com/problems/3sum/) — একই pointer-পরিবার, তবে fix + opposite (083)।
LeetCode Two Sum II (https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) — opposite version, পাশাপাশি পড়লে দিকনির্ণয়ের শিক্ষা পাকা হয় (081)।

কৌশলটি মনে রাখুন¶

Same-direction two pointers on a sorted array — দুই pointer পাশাপাশি, ফারাক ছোট হলে j++, বড় হলে i++, কেউ পিছায় না। বড় শিক্ষা: sum খুঁজতে opposite, difference খুঁজতে same-direction — target-এর সাথে প্রান্তের সম্পর্ক দেখে দিক বাছো।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে এক লাইনে: "difference = k খোঁজা = sort + দুই pointer একই দিকে; ফারাক ছোট → j++, বড় → i++; unique রাখতে match-এর পরে duplicate পেরিয়ে নাও। Signal: 'unique জোড়া' আর 'difference' একসাথে দেখলে same-direction pointers মনে পড়ুক।"

পরের ধাপ → 083 — Three Sum (এবার একজনকে বসিয়ে বাকি দুজনে opposite খেলা)। তুলনা করো → 081 — Two Sum Sorted (opposite vs same-direction)।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

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