Problem link ও উৎস
- **Original source:** LeetCode Search Insert Position
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Easy
- **Pattern:** lower bound apply (092-এর সরাসরি প্রয়োগ)
- **Basic idea inherited from:** 092 — Lower Bound
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **sorted** array `a` (সব element আলাদা ধরে নাও) আর একটা target `x` দেওয়া। যদি `x` array-তে থাকে, তার index দাও। আর না থাকলে — sorted ক্রম রক্ষা করতে x-কে যেখানে **ঢোকাতে হবে**, সেই index দাও।
মানে দুই ক্ষেত্রেই একটা index ফেরত: আছে হলে তার জায়গা, নেই হলে যেখানে বসত। উত্তর 0 থেকে `len(a)` পর্যন্ত যেকোনো কিছু হতে পারে (x সবার চেয়ে বড় হলে `len(a)`)।
### Input ও output {#6-example-input-and-output}
```text
a (sorted, distinct) x -> output (ব্যাখ্যা)
-------------------------------------------------
[1, 3, 5, 6] 5 -> 2 (5 আছে index 2-তে)
[1, 3, 5, 6] 2 -> 1 (2 নেই; 1 আর 3-এর মাঝে)
[1, 3, 5, 6] 7 -> 4 (সবার চেয়ে বড়; শেষে)
[1, 3, 5, 6] 0 -> 0 (সবার চেয়ে ছোট; শুরুতে)
[1, 3, 5, 6] 1 -> 0 (1 আছে index 0-তে)
[] 5 -> 0 (খালি array)
```
LeetCode-এর classic চারটে কেস (5, 2, 7, 0) — প্রতিটাই উপরের সিঁড়ির সরাসরি ফল।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো পরীক্ষার খাতাগুলো roll number-এ sorted করে একটা স্তূপে সাজানো। তোমার হাতে একটা নতুন খাতা, roll `x`।
- যদি সেই roll-এর খাতা স্তূপে আগে থেকেই থাকে — তুমি জানো ঠিক কোন জায়গায় (সেটার index)।
- না থাকলে — তুমি স্তূপে সেই প্রথম খাতাটা খোঁজো যার roll x-এর সমান বা বড়, আর ঠিক তার আগে তোমার খাতাটা গুঁজে দাও।
দুই ক্ষেত্রেই তুমি খুঁজছ "প্রথম roll ≥ x" — সেই এক জায়গাই দুই প্রশ্নের উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
092 (Lower Bound) থেকে — আক্ষরিক অর্থে এটা lower bound-এর প্রয়োগ। 092-এ আমরা "প্রথম ≥ x"-এর সাধারণ ধারণা গড়েছিলাম; এখানে সেই function-টা ডাকলেই উত্তর।
পার্থক্য শুধু গল্পে: 092 বলত "কোথায় বসবে", আর এখানে LeetCode বলছে "আছে হলে index, নেই হলে বসার জায়গা" — কিন্তু lower bound দুটোকেই একই উত্তরে মিলিয়ে দেয়। এই "চেনা জিনিস নতুন মোড়কে" চিনতে পারাটাই এখানে আসল দক্ষতা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — এই দুটো প্রশ্ন ("কোথায় আছে" আর "কোথায় বসবে") আসলে **একটাই** প্রশ্ন: **প্রথম index যেখানে `a[i] >= x`।**
- x থাকলে: প্রথম `a[i] >= x` মানে ঠিক x-এর index (সব আলাদা বলে)।
- x না থাকলে: প্রথম `a[i] >= x` মানে যে element-টা x-এর চেয়ে সবে বড়, তার জায়গাই x-এর বসার জায়গা।
অর্থাৎ এটা পুরোপুরি **lower bound**। নতুন math নেই — 092-এর সেই monotonic F F F T T T সিঁড়িই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
বাঁ থেকে এক এক করে দেখো, প্রথম যেখানে `a[i] >= x` সেখানেই x বসবে:
```python
def search_insert_brute(a, x):
for i in range(len(a)):
if a[i] >= x:
return i
return len(a) # x সবার চেয়ে বড় — শেষে বসবে
```
এটা আসলে hu-bahu lower bound-এর brute force (092-এর সাথে এক)। `a[i] >= x` প্রথম যেখানে সত্যি, সেটাই উত্তর — আছে হলে x-এর জায়গা, নেই হলে বসার জায়গা।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সেই চিরচেনা সমস্যা — সবচেয়ে খারাপ ক্ষেত্রে পুরো array, **O(n)**। array sorted, কিন্তু এক এক করে দেখলে সেই সুবিধা নষ্ট।
```text
n = 1,000,000 হলে:
linear scan : ~1,000,000 তুলনা (O(n))
binary search : ~20 তুলনা (O(log n))
```
LeetCode এই problem-এ স্পষ্ট চায় O(log n) — মানে binary search-ই প্রত্যাশিত সমাধান।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: এটা lower bound, তাই 092-এর binary search হুবহু বসিয়ে দাও:
```python
def search_insert(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1 # mid এখনো ছোট — বাঁ অর্ধেক বাদ
else:
hi = mid # mid হয়তো প্রথম ≥ x — রেখে দাও
return lo
```
প্রতি ধাপে অর্ধেক → O(log n)। কোড আর 092-এর `lower_bound`-এ একটুও পার্থক্য নেই।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **"আছে হলে index, নেই হলে বসার জায়গা" — এই দুই-মুখো প্রশ্ন আসলে একটাই: প্রথম `a[i] >= x`।** আলাদা করে "আছে কিনা" চেক করার দরকারই নেই।
এই tweak-টা শুধু এই problem-এর না — এটা একটা চিন্তার অভ্যাস: নতুন problem দেখে জিজ্ঞেস করো "এটা কি আমার চেনা কোনো bound/template-এর ছদ্মবেশ?" বহু "নতুন" problem আসলে পুরনো একটা pattern নতুন গল্পে মোড়া। চিনে ফেলতে পারাই অর্ধেক সমাধান।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 3, 5, 6]`। চারটে ভিন্ন x-এর জন্য "প্রথম `a[i] >= x`" দেখো:
```text
a = [ 1 3 5 6 ]
index = 0 1 2 3 4 (শেষের পরে)
x = 5: a[i]>=5 = F F T T প্রথম T = index 2 (5 আছে এখানে)
x = 2: a[i]>=2 = F T T T প্রথম T = index 1 (2 নেই; 3-এর আগে বসবে)
x = 7: a[i]>=7 = F F F F কেউ T না = index 4 (সবার পরে)
x = 0: a[i]>=0 = T T T T প্রথম T = index 0 (সবার আগে)
```
প্রতিবার একই সিঁড়ি (F...T...), একই "প্রথম T" নিয়ম — শুধু x বদলে যাচ্ছে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 3, 5, 6], x = 2` চালাই (`hi = 4`):
| step | lo | hi | mid | a[mid] | a[mid] < 2? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 0 | 4 | 2 | 5 | না | hi = mid = 2 |
| 2 | 0 | 2 | 1 | 3 | না | hi = mid = 1 |
| 3 | 0 | 1 | 0 | 1 | হ্যাঁ | lo = mid + 1 = 1 |
| — | 1 | 1 | — | — | — | lo == hi → return 1 |
উত্তর 1 — 2 বসবে 1 আর 3-এর মাঝে (index 1)। ঠিক lower bound-এর আচরণ।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def search_insert(a, x):
"""x-এর index (থাকলে) বা যেখানে বসবে (নেই হলে); = lower bound।"""
lo, hi = 0, len(a) # উত্তর len(a)-ও হতে পারে
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1 # mid এখনো ছোট — বাঁ অর্ধেক বাদ
else:
hi = mid # mid হয়তো প্রথম ≥ x — রেখে দাও
return lo
from bisect import bisect_left
def search_insert_brute(a, x):
for i in range(len(a)):
if a[i] >= x:
return i
return len(a)
# --- ছোট test গুলো (সব pass করা উচিত) ---
a = [1, 3, 5, 6]
assert search_insert(a, 5) == 2 # আছে
assert search_insert(a, 2) == 1 # নেই, মাঝে
assert search_insert(a, 7) == 4 # সবার চেয়ে বড় → len
assert search_insert(a, 0) == 0 # সবার চেয়ে ছোট
assert search_insert(a, 1) == 0 # আছে, শুরুতে
assert search_insert([], 5) == 0 # খালি array
# lower bound (bisect_left) আর brute force-এর সাথে cross-check
big = [1, 4, 7, 10, 13, 16, 19]
for x in range(0, 21):
assert search_insert(big, x) == bisect_left(big, x)
assert search_insert(big, x) == search_insert_brute(big, x)
print(search_insert(a, 5)) # 2
print(search_insert(a, 2)) # 1
print(search_insert(a, 7)) # 4
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
lo, hi = 0, len(a)
```
range `[0, len(a)]` — কারণ x সবার চেয়ে বড় হলে উত্তর `len(a)` (একদম শেষে বসবে)।
```text
if a[mid] < x: lo = mid + 1
```
`a[mid]` এখনো x-এর ছোট — তাই এই index-এ বা তার বাঁয়ে x বসবে না। mid সহ বাঁ অর্ধেক বাদ।
```text
else: hi = mid
```
`a[mid] >= x` — mid নিজেই হয়তো সেই প্রথম জায়গা যেখানে x বসবে। তাই রেখে দিই (`hi = mid`)।
```text
return lo
```
loop শেষে `lo == hi` — সেই প্রথম index যেখানে `a[i] >= x`, অর্থাৎ x-এর জায়গা বা বসার জায়গা।
cross-check-এ `bisect_left` (যা আক্ষরিক lower bound) আর brute force দুটোর সাথেই প্রতিটা x-এ মিলিয়ে দেখছি — এটাই প্রমাণ যে এটা সত্যিই lower bound। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
2
1
4
সব test pass!
```
প্রথম: `search_insert(a, 5)` = 2 (5 আছে index 2-তে)। দ্বিতীয়: `search_insert(a, 2)` = 1 (2 নেই, 1-3-এর মাঝে)। তৃতীয়: `search_insert(a, 7)` = 4 (7 সবার চেয়ে বড়, শেষে = len)। আগের সব `assert` (bisect_left + brute force cross-check সহ) চুপচাপ pass। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log n)** — হুবহু binary search, প্রতি ধাপে অর্ধেক। LeetCode-এর চাওয়া complexity-ও এটাই।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `lo`, `hi`, `mid`; বাড়তি জায়গা লাগে না। (test-এর `big` list আলাদা।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **"আছে কিনা" আলাদা চেক করা** — দরকার নেই; lower bound দুই ক্ষেত্রকেই একসাথে সামলায়। বাড়তি if লিখলে শুধু জটিলতা।
2. **`hi = len(a) - 1` দিয়ে শুরু** — x সবার চেয়ে বড় হলে উত্তর `len(a)` মিস হয়; range `[0, len(a)]`।
3. **`hi = mid - 1` লেখা** — যে mid নিজেই বসার জায়গা, তাকে বাদ দাও → উত্তর ভুল। `hi = mid` রাখো।
4. **duplicate ধরে নেওয়া** — এই problem distinct ধরে; কিন্তু duplicate থাকলেও lower bound প্রথম occurrence-এ বসবে (নিরাপদ আচরণ)।
5. **`while lo <= hi` লেখা** — `hi = mid` থাকায় infinite loop; এই template-এ `while lo < hi`।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Find Smallest Letter Greater Than Target** (