কনটেন্টে যান

001 — Last Stone Weight

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Classic heap + greedy warm-up
  • Platform: LeetCode — https://leetcode.com/problems/last-stone-weight/
  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

কতগুলো পাথর দেওয়া আছে, প্রতিটার একটা ওজন। প্রতি round-এ তুমি সবচেয়ে ভারী দুটো পাথর নাও আর smash করো। দুটোর ওজন সমান হলে দুটোই গুঁড়ো হয়ে যায়। অসমান হলে হালকাটা শেষ, আর ভারীটার গায়ে শুধু পার্থক্যটুকু থেকে যায়। যতক্ষণ একটার বেশি পাথর আছে এটা চলতে থাকে। শেষে যে একটা পাথর বাকি থাকে তার ওজন return করো — কিছু না থাকলে 0।

উদাহরণ
[2, 7, 4, 1, 8, 1]  ->  শেষে বাকি একটা পাথর, ওজন 1

Input ও output

উদাহরণ
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   (খালি)

চেনা উদাহরণে বোঝা

দুটো সবচেয়ে ভারী লোহার বল নিয়ে দুজন কামার ঠোকাঠুকি করছে ভাবো। সমান হলে দুটোই চুরমার; নাহলে বড় বলটা ছোট হয়ে যায় ঠিক পার্থক্যটুকুতে। প্রতিবার তারা শুধু এই মুহূর্তের সবচেয়ে ভারী দুটো খোঁজে — পুরো গুদাম সাজিয়ে রাখে না। সেই "সবচেয়ে ভারী দুটো চট করে দাও" যন্ত্রটাই heap।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত হলো heap-এর push/pop আর negate-for-max trick। তোমাকে বারবার একটাই প্রশ্ন করতে হচ্ছে — "এখন সবচেয়ে ভারী কে?" — আর সেই উত্তরটা দ্রুত পেতে heap-ই সেরা যন্ত্র। Python-এর heapq min-heap, তাই max চাইলে সব value-কে negate করে ঢালো; সবচেয়ে ছোট negative-ই সবচেয়ে বড় original।

ভেতরের যুক্তি

লুকানো logic একটা greedy invariant: প্রতি step-এ "এখনকার দুই ভারীতম smash করা" কখনো ভুল সিদ্ধান্ত না, কারণ পাথরগুলো শুধু একে অপরকে কমাতে পারে — কখনো বাড়াতে পারে না। তাই কোন order-এ ভারীগুলো জোড়া লাগে সেটা চূড়ান্ত একটা পাথরের সম্ভাবনা নষ্ট করে না; locally-best choice গুলোই মিলে globally ঠিক উত্তর দেয়।

কী দিয়ে তথ্য রাখব

একটা max-heap (priority queue)। heapq min-heap বলে আমরা ওজনগুলোকে negate করে একটা list-এ রাখি, তারপর heapify করি।

এটি কেন উপযুক্ত

প্রতি round-এ তোমার দরকার শুধু দুই extreme — সবচেয়ে ভারী আর তার পরেরটা — পুরো sorted order না। Heap ঠিক এই promise সস্তায় রাখে: top-এ সবসময় extreme, peek O(1), pop ও push O(log n)। প্রতিবার পুরো array re-sort করার দরকারই পড়ে না।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতি round-এ পুরো list sort করো, শেষ দুটো (সবচেয়ে ভারী) নাও, smash করো, পার্থক্য থাকলে আবার list-এ ঢোকাও — এবং আবার sort করো।

উদাহরণ
[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

কোথায় বেশি কাজ হচ্ছে

প্রতি round-এ একটা full sort মানে O(n log n), আর round হতে পারে O(n)-টা — মোট O(n² log n)। অথচ আমাদের প্রতিবার পুরো order লাগেই না, শুধু দুই ভারীতম লাগে। পুরো list বারবার সাজানো নিখাদ অপচয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: তোমার কখনো সম্পূর্ণ sorted list দরকার নেই — প্রতি round-এ শুধু দুটো প্রশ্ন: "সবচেয়ে ভারী কে?" আর "তার পরেরটা কে?"। আর smash-এর ফল (পার্থক্য) আবার heap-এ ফেরত গেলেও সেটা O(log n)-এ ঠিক জায়গায় বসে যায়।

আরও কম কাজে সমাধান

সব পাথর একবার heap-এ ঢালো (negate করে max-heap)। তারপর loop: দুবার pop করো (দুই ভারীতম), পার্থক্য বের করো, শূন্য না হলে আবার push করো। heap-এ একটার কম পাথর থাকলে থামো। প্রতিটা pop/push O(log n), পুরো কাজ O(n log n)।

ভাবনার পরিবর্তন

মোচড়: "পাথর smash করা" না ভেবে ভাবো "একটা evolving multiset থেকে বারবার max টেনে বের করা।" যখনই কোনো problem বলে "বারবার দুই extreme নিয়ে আবার কিছু ফেরত দাও", তোমার মাথায় heap-এর আলো জ্বলে ওঠা উচিত — এটাই heap + greedy pattern-এর সিগনেচার।

ছবিতে বোঝা

[2, 7, 4, 1, 8, 1] দিয়ে দেখি (max-heap-এ top = সবচেয়ে ভারী):

উদাহরণ
পাথর:  [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-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

O(n log n) — heapify O(n), তারপর প্রতি round-এ বড়জোর constant-সংখ্যক pop/push (প্রতিটা O(log n)), আর round হয় O(n)-টা।

অতিরিক্ত জায়গা

O(n) — negate করা ওজনগুলোর heap। In-place চাইলে input list-কেই negate করে ব্যবহার করা যায়, কিন্তু আলাদা list রাখা পরিষ্কার।

যে ভুলগুলো এড়াতে হবে

  • max-heap না বানিয়ে সরাসরি heapq ব্যবহার করা — তখন তুমি দুই হালকা পাথর smash করছ, ভুল উত্তর।
  • pop-এর পরে negate করতে ভুলে যাওয়া (a = heapq.heappop(h) লেখা) — তখন a থাকে negative।
  • শেষে খালি heap-এ h[0] করা — if h else 0 দিয়ে guard না দিলে IndexError।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি 08-এর concept.md-র heapq basics (push/pop) আর negate-for-max trick। আর patterns.md-র Pattern 6 (Heap + greedy combos) — "বারবার দুই extreme নাও, compute করো, হয়তো একটা push করে ফেরত দাও" — সেই skeleton-এরই সরলতম রূপ।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Heap + greedy: একটা evolving multiset থেকে বারবার extreme টেনে নাও, কিছু compute করো, ফল আবার ফেরত দাও। greedy ঠিক করে কী নেবে, heap সেটা O(log n)-এ দেয়। এই pattern-ই পরে graphs-এ Dijkstra হয়ে ফিরে আসবে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "বারবার দুই ভারীতম নিয়ে কাজ" = max-heap (negate করা) + একটা loop। যখনই শুনবে "repeatedly take the two largest/smallest and recombine", এই smash-loop মনে করবে — এটা heap + greedy-র hello-world, এবং প্রায় চোখ বন্ধ করে লেখা চাই।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।