Problem link ও উৎস
- **Original source:** LeetCode K-diff Pairs in an Array
- **Platform:** LeetCode —
- **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-এ মোচড়)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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 জোড়া একবারই গোনা।
### Input ও output {#6-example-input-and-output}
```text
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)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা দৌড়ের ট্র্যাকে দুজন দৌড়বিদ — দুজনেই একই দিকে দৌড়ায়, কেউ পেছনে ফেরে না। তুমি চাও তাদের মাঝের ফারাক ঠিক `k` মিটার হোক।
- ফারাক `k`-এর কম? → সামনের জন আরেকটু এগোক (ফারাক বাড়বে) → `j++`
- ফারাক `k`-এর বেশি? → পেছনের জন এগিয়ে আসুক (ফারাক কমবে) → `i++`
দুজনেই শুধু সামনে যায়, কেউ পেছায় না — তাই মোট দৌড় সীমিত। এই "কেউ পিছায় না" বৈশিষ্ট্যই O(n)-এর গ্যারান্টি।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 পাশাপাশি পড়লে এই দিকনির্ণয়ের শিক্ষাটা গেঁথে যায়।
### ভেতরের অঙ্ক {#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 ধরা যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — সব জোড়া দেখে 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 না হলেও চলে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
বাইরের আর ভেতরের loop মিলিয়ে প্রায় n²/2 জোড়া। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।
```text
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 গোনার চাবি।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 3, 5, 9]`, `k = 4` — দুই pointer একই দিকে চলছে:
```text
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 কখনো ক্রস করে না, দুজনেই বাঁ থেকে ডানে:
```text
diff ছোট হলে: i .. j → i ..... j (j ডানে, ফারাক বাড়ে)
diff বড় হলে : i .. j → i .. j (i ডানে, ফারাক কমে)
diff == k : জোড়া গোনো, তারপর দুজনকেই duplicate পেরিয়ে নাও
```
### ছোট input-এ ধাপে ধাপে {#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-এর কাজ এটাই।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
a = sorted(a)
i, j = 0, 1
```
আগে sort (difference-এর monotonicity-র জন্য আবশ্যক)। দুই pointer পাশাপাশি শুরু — দুজনেই একই দিকে যাবে।
```text
if i == j: j += 1; continue
```
দুটো pointer এক জায়গায় এলে `j`-কে এগিয়ে দাও — index আলাদা রাখা (নিজের সাথে নিজের জোড়া এড়াতে)।
```text
d = a[j] - a[i]
```
sorted বলে `a[j] >= a[i]`, তাই এটাই absolute difference।
```text
if d == k:
count += 1
... while a[i]==vi: i++ ; while a[j]==vj: j++
```
মিলে গেলে গুনলাম, তারপর দুই pointer-কে সমান-মান পেরিয়ে নিলাম — যাতে একই মান-জোড়া আবার না গোনা হয় (unique-এর চাবি)।
```text
elif d < k: j += 1
else: i += 1
```
ফারাক ছোট হলে সামনেরটা এগোক (বাড়াও), বড় হলে পেছনেরটা এগোক (কমাও)। দুজনেই শুধু ডানে।
`k_diff_brute` test যাচাইয়ের reference; random case-গুলো দুই পথের উত্তর মিলিয়ে দেখে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 পথ শুধু একটা রূপ।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode K-diff Pairs in an Array** (