Problem link ও উৎস
- **Original source:** Classic heap + greedy warm-up
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Easy
- **Pattern:** Heap + greedy (smash two largest)
- **Basic idea inherited from:** `08` heapq basics — push/pop আর negate-for-max trick
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো পাথর দেওয়া আছে, প্রতিটার একটা ওজন। প্রতি round-এ তুমি **সবচেয়ে ভারী দুটো** পাথর নাও আর smash করো। দুটোর ওজন **সমান** হলে দুটোই গুঁড়ো হয়ে যায়। অসমান হলে হালকাটা শেষ, আর ভারীটার গায়ে শুধু **পার্থক্য**টুকু থেকে যায়। যতক্ষণ একটার বেশি পাথর আছে এটা চলতে থাকে। শেষে যে একটা পাথর বাকি থাকে তার ওজন return করো — কিছু না থাকলে 0।
```text
[2, 7, 4, 1, 8, 1] -> শেষে বাকি একটা পাথর, ওজন 1
```
### Input ও output {#8-example-input-and-output}
```text
Input : stones = [2, 7, 4, 1, 8, 1] -> Output: 1
Input : stones = [1] -> Output: 1 (একটাই পাথর)
Input : stones = [2, 2] -> Output: 0 (সমান, দুটোই শেষ)
Input : stones = [] -> Output: 0 (খালি)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুটো সবচেয়ে ভারী লোহার বল নিয়ে দুজন কামার ঠোকাঠুকি করছে ভাবো। সমান হলে দুটোই চুরমার; নাহলে বড় বলটা ছোট হয়ে যায় ঠিক পার্থক্যটুকুতে। প্রতিবার তারা শুধু এই মুহূর্তের সবচেয়ে ভারী দুটো খোঁজে — পুরো গুদাম সাজিয়ে রাখে না। সেই "সবচেয়ে ভারী দুটো চট করে দাও" যন্ত্রটাই heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো **heap-এর push/pop** আর **negate-for-max trick**। তোমাকে বারবার একটাই প্রশ্ন করতে হচ্ছে — "এখন সবচেয়ে ভারী কে?" — আর সেই উত্তরটা দ্রুত পেতে heap-ই সেরা যন্ত্র। Python-এর `heapq` min-heap, তাই max চাইলে সব value-কে negate করে ঢালো; সবচেয়ে ছোট negative-ই সবচেয়ে বড় original।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **greedy invariant**: প্রতি step-এ "এখনকার দুই ভারীতম smash করা" কখনো ভুল সিদ্ধান্ত না, কারণ পাথরগুলো শুধু একে অপরকে কমাতে পারে — কখনো বাড়াতে পারে না। তাই কোন order-এ ভারীগুলো জোড়া লাগে সেটা চূড়ান্ত একটা পাথরের সম্ভাবনা নষ্ট করে না; locally-best choice গুলোই মিলে globally ঠিক উত্তর দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **max-heap** (priority queue)। heapq min-heap বলে আমরা ওজনগুলোকে negate করে একটা list-এ রাখি, তারপর `heapify` করি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতি round-এ তোমার দরকার শুধু **দুই extreme** — সবচেয়ে ভারী আর তার পরেরটা — পুরো sorted order না। Heap ঠিক এই promise সস্তায় রাখে: top-এ সবসময় extreme, peek O(1), pop ও push O(log n)। প্রতিবার পুরো array re-sort করার দরকারই পড়ে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতি round-এ পুরো list `sort` করো, শেষ দুটো (সবচেয়ে ভারী) নাও, smash করো, পার্থক্য থাকলে আবার list-এ ঢোকাও — এবং আবার sort করো।
```text
[2,7,4,1,8,1] -> sort -> [1,1,2,4,7,8] -> 8,7 নাও -> 1 ঢোকাও
[1,1,1,2,4] -> 4,2 নাও -> 2 ফেরত -> [1,1,1,2]
[1,1,1,2] -> 2,1 নাও -> 1 ফেরত -> [1,1,1]
[1,1,1] -> 1,1 নাও -> সমান বলে দুটোই বাদ -> [1]
শেষ ওজন: 1
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি round-এ একটা full `sort` মানে O(n log n), আর round হতে পারে O(n)-টা — মোট **O(n² log n)**। অথচ আমাদের প্রতিবার পুরো order লাগেই না, শুধু দুই ভারীতম লাগে। পুরো list বারবার সাজানো নিখাদ অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: তোমার কখনো **সম্পূর্ণ sorted list দরকার নেই** — প্রতি round-এ শুধু দুটো প্রশ্ন: "সবচেয়ে ভারী কে?" আর "তার পরেরটা কে?"। আর smash-এর ফল (পার্থক্য) আবার heap-এ ফেরত গেলেও সেটা O(log n)-এ ঠিক জায়গায় বসে যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
সব পাথর একবার heap-এ ঢালো (negate করে max-heap)। তারপর loop: দুবার pop করো (দুই ভারীতম), পার্থক্য বের করো, শূন্য না হলে আবার push করো। heap-এ একটার কম পাথর থাকলে থামো। প্রতিটা pop/push O(log n), পুরো কাজ O(n log n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পাথর smash করা" না ভেবে ভাবো "একটা evolving multiset থেকে বারবার max টেনে বের করা।" যখনই কোনো problem বলে "বারবার দুই extreme নিয়ে আবার কিছু ফেরত দাও", তোমার মাথায় heap-এর আলো জ্বলে ওঠা উচিত — এটাই heap + greedy pattern-এর সিগনেচার।
### ছবিতে বোঝা {#7-visual-explanation}
`[2, 7, 4, 1, 8, 1]` দিয়ে দেখি (max-heap-এ top = সবচেয়ে ভারী):
```text
পাথর: [2, 7, 4, 1, 8, 1] -> max-heap top = 8
round 1: 8 আর 7 নাও -> 8 != 7, ফেরত 1 বাকি: [4, 2, 1, 1, 1]
round 2: 4 আর 2 নাও -> 4 != 2, ফেরত 2 বাকি: [2, 1, 1, 1]
round 3: 2 আর 1 নাও -> 2 != 1, ফেরত 1 বাকি: [1, 1, 1]
round 4: 1 আর 1 নাও -> 1 == 1, দুটোই শেষ বাকি: [1]
1টা পাথর বাকি -> উত্তর 1
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `stones = [2, 7, 4, 1, 8, 1]`:
1. negate + heapify → max-heap top = 8, পাথর {8,7,4,2,1,1}
2. pop 8, pop 7 → 8 ≠ 7 → push (8−7)=1 → {4,2,1,1,1}
3. pop 4, pop 2 → 4 ≠ 2 → push (4−2)=2 → {2,1,1,1}
4. pop 2, pop 1 → 2 ≠ 1 → push (2−1)=1 → {1,1,1}
5. pop 1, pop 1 → 1 = 1 → কিছু push না → {1}
6. heap-এ একটা পাথর → loop শেষ → return 1
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def last_stone_weight(stones):
h = [-s for s in stones] # negate: max-heap বানানোর trick
heapq.heapify(h) # O(n)-এ heap বানাও, top-এ সবচেয়ে ভারী
while len(h) > 1: # অন্তত দুটো পাথর লাগবে
a = -heapq.heappop(h) # সবচেয়ে ভারী
b = -heapq.heappop(h) # দ্বিতীয় ভারী
if a != b: # সমান না হলে পার্থক্যটা থেকে যায়
heapq.heappush(h, -(a - b))
return -h[0] if h else 0 # বাকি থাকলে তার ওজন, নাহলে 0
# ---- tests ----
assert last_stone_weight([2, 7, 4, 1, 8, 1]) == 1
assert last_stone_weight([1]) == 1 # একটাই পাথর
assert last_stone_weight([2, 2]) == 0 # সমান, দুটোই শেষ
assert last_stone_weight([]) == 0 # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `h = [-s for s in stones]` — প্রতিটা ওজন negate; min-heap-কে max-heap-এর মতো কাজ করাতে।
- `heapq.heapify(h)` — list-টাকে O(n)-এ valid heap বানায়; `h[0]` হয় সবচেয়ে বড় ওজনের negative।
- `while len(h) > 1:` — দুটো smash করতে অন্তত দুটো পাথর দরকার।
- `a = -heapq.heappop(h)` / `b = ...` — top দুটো pop করে negate ফেরালে আসল দুই ভারীতম ওজন।
- `if a != b:` — সমান হলে দুটোই vanish (কিছু push না); নাহলে পার্থক্যটা negate করে push।
- `return -h[0] if h else 0` — একটা পাথর বাকি থাকলে তার ওজন, খালি হলে 0।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`last_stone_weight([2,7,4,1,8,1])` section 14-এর dry run মেনে 1 দেয় — assert pass। `[1]` সরাসরি 1; `[2,2]` দুটো সমান smash হয়ে 0; `[]` খালি বলে loop চলেই না, return 0। চারটে assert pass করার পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — `heapify` O(n), তারপর প্রতি round-এ বড়জোর constant-সংখ্যক pop/push (প্রতিটা O(log n)), আর round হয় O(n)-টা।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — negate করা ওজনগুলোর heap। In-place চাইলে input list-কেই negate করে ব্যবহার করা যায়, কিন্তু আলাদা list রাখা পরিষ্কার।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- max-heap না বানিয়ে সরাসরি heapq ব্যবহার করা — তখন তুমি দুই *হালকা* পাথর smash করছ, ভুল উত্তর।
- pop-এর পরে negate করতে ভুলে যাওয়া (`a = heapq.heappop(h)` লেখা) — তখন `a` থাকে negative।
- শেষে খালি heap-এ `h[0]` করা — `if h else 0` দিয়ে guard না দিলে IndexError।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `08`-এর `concept.md`-র heapq basics (push/pop) আর negate-for-max trick। আর `patterns.md`-র Pattern 6 (Heap + greedy combos) — "বারবার দুই extreme নাও, compute করো, হয়তো একটা push করে ফেরত দাও" — সেই skeleton-এরই সরলতম রূপ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Reorganize String —