094 — Search Insert Position¶
এই problem-টা একটা মজার চমক: নতুন কিছু শিখতে হবে না! তুমি 092-এ যে lower bound শিখলে, এই problem আসলে সেটারই অন্য পোশাক। LeetCode এটাকে আলাদা নাম দিয়েছে, কিন্তু ভেতরে হুবহু "প্রথম ≥ x"। তাই এই note-টা একটা confidence booster — দেখো, একটা চেনা pattern কীভাবে নতুন প্রশ্নের ছদ্মবেশে আসে। চিনতে পারলেই অর্ধেক interview জেতা।
Source¶
- Original source: LeetCode Search Insert Position
- Platform: LeetCode — https://leetcode.com/problems/search-insert-position/
- 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
1. Problem in simple words¶
একটা sorted array a (সব element আলাদা ধরে নাও) আর একটা target x দেওয়া। যদি x array-তে থাকে, তার index দাও। আর না থাকলে — sorted ক্রম রক্ষা করতে x-কে যেখানে ঢোকাতে হবে, সেই index দাও।
মানে দুই ক্ষেত্রেই একটা index ফেরত: আছে হলে তার জায়গা, নেই হলে যেখানে বসত। উত্তর 0 থেকে len(a) পর্যন্ত যেকোনো কিছু হতে পারে (x সবার চেয়ে বড় হলে len(a))।
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 সিঁড়িই।
3. Which basic idea does this inherit from?¶
092 (Lower Bound) থেকে — আক্ষরিক অর্থে এটা lower bound-এর প্রয়োগ। 092-এ আমরা "প্রথম ≥ x"-এর সাধারণ ধারণা গড়েছিলাম; এখানে সেই function-টা ডাকলেই উত্তর।
পার্থক্য শুধু গল্পে: 092 বলত "কোথায় বসবে", আর এখানে LeetCode বলছে "আছে হলে index, নেই হলে বসার জায়গা" — কিন্তু lower bound দুটোকেই একই উত্তরে মিলিয়ে দেয়। এই "চেনা জিনিস নতুন মোড়কে" চিনতে পারাটাই এখানে আসল দক্ষতা।
4. Real-life analogy¶
ভাবো পরীক্ষার খাতাগুলো roll number-এ sorted করে একটা স্তূপে সাজানো। তোমার হাতে একটা নতুন খাতা, roll x।
- যদি সেই roll-এর খাতা স্তূপে আগে থেকেই থাকে — তুমি জানো ঠিক কোন জায়গায় (সেটার index)।
- না থাকলে — তুমি স্তূপে সেই প্রথম খাতাটা খোঁজো যার roll x-এর সমান বা বড়, আর ঠিক তার আগে তোমার খাতাটা গুঁজে দাও।
দুই ক্ষেত্রেই তুমি খুঁজছ "প্রথম roll ≥ x" — সেই এক জায়গাই দুই প্রশ্নের উত্তর।
5. Visual explanation¶
a = [1, 3, 5, 6]। চারটে ভিন্ন x-এর জন্য "প্রথম a[i] >= x" দেখো:
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 বদলে যাচ্ছে।
6. Example input and output¶
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) — প্রতিটাই উপরের সিঁড়ির সরাসরি ফল।
7. Brute force thinking¶
বাঁ থেকে এক এক করে দেখো, প্রথম যেখানে a[i] >= x সেখানেই x বসবে:
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, কিন্তু এক এক করে দেখলে সেই সুবিধা নষ্ট।
LeetCode এই problem-এ স্পষ্ট চায় O(log n) — মানে binary search-ই প্রত্যাশিত সমাধান।
9. Better thinking¶
মূল insight: এটা lower bound, তাই 092-এর binary search হুবহু বসিয়ে দাও:
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 নতুন গল্পে মোড়া। চিনে ফেলতে পারাই অর্ধেক সমাধান।
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-এর আচরণ।
12. Python solution¶
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¶
range [0, len(a)] — কারণ x সবার চেয়ে বড় হলে উত্তর len(a) (একদম শেষে বসবে)।
a[mid] এখনো x-এর ছোট — তাই এই index-এ বা তার বাঁয়ে x বসবে না। mid সহ বাঁ অর্ধেক বাদ।
a[mid] >= x — mid নিজেই হয়তো সেই প্রথম জায়গা যেখানে x বসবে। তাই রেখে দিই (hi = mid)।
loop শেষে lo == hi — সেই প্রথম index যেখানে a[i] >= x, অর্থাৎ x-এর জায়গা বা বসার জায়গা।
cross-check-এ bisect_left (যা আক্ষরিক lower bound) আর brute force দুটোর সাথেই প্রতিটা x-এ মিলিয়ে দেখছি — এটাই প্রমাণ যে এটা সত্যিই lower bound। সব মিললে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম: 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!।
15. Time complexity¶
O(log n) — হুবহু binary search, প্রতি ধাপে অর্ধেক। LeetCode-এর চাওয়া complexity-ও এটাই।
16. Space complexity¶
O(1) — শুধু lo, hi, mid; বাড়তি জায়গা লাগে না। (test-এর big list আলাদা।)
17. Common mistakes¶
- "আছে কিনা" আলাদা চেক করা — দরকার নেই; lower bound দুই ক্ষেত্রকেই একসাথে সামলায়। বাড়তি if লিখলে শুধু জটিলতা।
hi = len(a) - 1দিয়ে শুরু — x সবার চেয়ে বড় হলে উত্তরlen(a)মিস হয়; range[0, len(a)]।hi = mid - 1লেখা — যে mid নিজেই বসার জায়গা, তাকে বাদ দাও → উত্তর ভুল।hi = midরাখো।- duplicate ধরে নেওয়া — এই problem distinct ধরে; কিন্তু duplicate থাকলেও lower bound প্রথম occurrence-এ বসবে (নিরাপদ আচরণ)।
while lo <= hiলেখা —hi = midথাকায় infinite loop; এই template-এwhile lo < hi।
18. Harder problems that inherit this idea¶
- LeetCode — Find Smallest Letter Greater Than Target (https://leetcode.com/problems/find-smallest-letter-greater-than-target/) — প্রায় একই, শুধু upper bound আর wrap-around।
- LeetCode — Time Based Key-Value Store (https://leetcode.com/problems/time-based-key-value-store/) — timestamp-এর উপর lower/upper bound-এর বাস্তব প্রয়োগ।
- 101 (Median of Two Sorted Arrays) — এই repo-রই পরের কঠিন ধাপ; সেখানেও "কোথায় কাটা পড়বে"-র boundary খোঁজা এই lower bound-চিন্তার আত্মীয়।
19. Pattern learned¶
Recognizing lower bound in disguise — "আছে হলে index, নেই হলে বসার জায়গা" = প্রথম a[i] >= x = lower bound। বড় শিক্ষা: অনেক 'নতুন' problem আসলে চেনা একটা template-এর গল্প-বদল; pattern চিনে ফেলাই অর্ধেক সমাধান। নতুন problem-এ সবসময় জিজ্ঞেস করো — "এটা কি আমার চেনা কোনো bound/search-এর ছদ্মবেশ?"
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "Search Insert Position = lower bound, হুবহু bisect_left। 'আছে হলে index, নেই হলে বসার জায়গা' আলাদা কেস না — একটাই 'প্রথম ≥ x'। নতুন problem-এ চেনা pattern খোঁজার চোখ রাখি।"
পরের ধাপ → 095 — Square Root using Binary Search (এবার array উধাও — উত্তরের উপরেই binary search, প্রথম BSoA!)। সম্পর্কিত → 092 — Lower Bound।
ফিরে দেখা: এই 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" লেখো।