Skip to content

001 — Last Stone Weight

Source

  • 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

1. Problem in simple words

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

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

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 করার দরকারই পড়ে না।

6. Real-life analogy

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

7. Visual explanation

[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

8. Example input and 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   (খালি)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতি 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]   -> sort -> ... -> বারবার

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-এর সিগনেচার।

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

15. Python solution

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।

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

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।

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

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "বারবার দুই ভারীতম নিয়ে কাজ" = 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।