082 — Pair with Difference K¶

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

Source¶

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-এ মোচড়)

1. Problem in simple words¶

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

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

2. What is the math idea?¶

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

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

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

3. Which basic idea does this inherit from?¶

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

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

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

4. Real-life analogy¶

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

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

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

5. Visual explanation¶

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 পেরিয়ে নাও

6. Example input and 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)।

7. Brute force thinking¶

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

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 না হলেও চলে।

8. Why brute force may be slow¶

বাইরের আর ভেতরের 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 সব জোড়া ঘাঁটছে।

9. Better thinking¶

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

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

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

10. Thinking tweak¶

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

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

11. Step-by-step dry run¶

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-এর কাজ এটাই।

12. Python solution¶

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!")

13. Line-by-line explanation¶

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-গুলো দুই পথের উত্তর মিলিয়ে দেখে।

14. Output walkthrough¶

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

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!।

15. Time complexity¶

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

16. Space complexity¶

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

17. Common mistakes¶

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 পথ শুধু একটা রূপ।

18. Harder problems that inherit this idea¶

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)।

19. Pattern learned¶

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

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "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" লেখো।