Skip to content

011 — Asteroid Collision

Source

  • Original source: Classic stack-simulation exercise
  • Platform: LeetCode — https://leetcode.com/problems/asteroid-collision/
  • Topic: stack (simulation)
  • Difficulty: Medium
  • Pattern: stack simulation — monotonic flavor
  • Basic idea inherited from: নতুন element এসে dominated-দের ধ্বংস করে (monotonic stack-এর সংঘর্ষ-রূপ)

1. Problem in simple words

তোমাকে কিছু asteroid-এর একটা সারি দেওয়া আছে। প্রতিটা সংখ্যার মান হলো size, আর চিহ্ন হলো দিক — ধনাত্মক মানে ডানে ছুটছে, ঋণাত্মক মানে বামে ছুটছে। সবাই একই গতিতে চলছে।

সংঘর্ষ তখনই হয় যখন একটা ডানগামী asteroid-এর ঠিক পরে একটা বামগামী asteroid থাকে (...+ , -...)। ছোটটা ধ্বংস হয়; সমান হলে দুজনেই ধ্বংস হয়; বড়টা টিকে যায়। যারা একই দিকে ছোটে বা মুখোমুখি নয়, তারা কখনো ধাক্কা খায় না। শেষে কোন asteroid গুলো বেঁচে থাকে বলো।

[5, 10, -5]  -> [5, 10]     (-5 ছোট, 10-এর সাথে ধাক্কায় মরে)
[8, -8]      -> []          (সমান size, দুজনেই মরে)
[10, 2, -5]  -> [10]        (-5, 2-কে মারে, তারপর 10-এর কাছে মরে)
[-2, -1, 1, 2] -> [-2, -1, 1, 2]  (কেউ মুখোমুখি নয়)

2. Which basic idea does this inherit from?

এটা একটা stack simulation, কিন্তু গায়ে monotonic-stack-এর গন্ধ। Problem 9-এর মতোই — একটা নতুন element এসে stack-এ অপেক্ষায় থাকা দুর্বলদের "হারিয়ে" দেয়। পার্থক্য: এখানে হারানো মানে answer deliver করা নয়, বরং literal ধ্বংস — pop করে ফেলে দেওয়া। আর সংঘর্ষ শুধু একটা নির্দিষ্ট দিকে (+ তারপর -) ঘটে।

3. What is the hidden math or logic?

লুকানো logic: stack ধরে রাখে এ পর্যন্ত টিকে থাকা asteroid গুলো, বাঁ থেকে ডানে যেভাবে আছে। একটা নতুন asteroid a যখন আসে:

  • যদি a ডানগামী (a > 0) — সে কখনো বাঁয়ের কারো সাথে মুখোমুখি হয় না, তাই সরাসরি stack-এ যোগ দেয়।
  • যদি a বামগামী (a < 0) — সে stack-এর top-এর ডানগামী asteroid গুলোর সাথে একে একে ধাক্কা খায়। প্রতিটা ধাক্কায় তিনটার একটা ঘটে: top ছোট হলে top মরে (a এগিয়ে যায়), সমান হলে দুজনেই মরে, top বড় হলে a মরে।

এই decision-গুলো শুধু top আর a-এর তুলনায় নির্ভর করে — তাই একটা local rule দিয়েই পুরো chain সামলানো যায়।

4. Which data structure is needed?

একটা stack (Python-এ সাধারণ list) যেখানে টিকে থাকা asteroid গুলো জমে। নতুন বামগামী asteroid-এর সাথে শুধু stack-এর top বারবার তুলনা করতে হয়, তাই অন্য কোনো structure লাগে না।

5. Why this data structure fits

সংঘর্ষ সবসময় ঘটে "সবচেয়ে recently টিকে থাকা ডানগামী"-র সাথে — যেটা ঠিক stack-এর top। একটা বামগামী asteroid top-কে হারিয়ে দিলে, ঠিক তার নিচেরটা নতুন top হয়ে আবার মুখোমুখি হয়। এই "top-এর সাথে লড়ো, মরলে নিচেরটার সাথে আবার লড়ো" pattern হুবহু LIFO, আর প্রতিটা asteroid বড়জোর একবার push, একবার pop → amortized O(1)।

6. Real-life analogy

ভাবো একটা সরু রাস্তায় ডান দিকে ছুটে যাওয়া কিছু গাড়ি পরপর দাঁড়িয়ে আছে, আর বাঁ দিক থেকে একটা বড় ট্রাক উল্টো দিকে এসে ঢুকল। ট্রাকটা প্রথমে সবচেয়ে কাছের (সবচেয়ে recently দাঁড়ানো) গাড়িটাকে ধাক্কা দেয়; সেটা ছোট হলে গুঁড়িয়ে এগিয়ে যায় পরেরটার দিকে। ট্রাক নিজের চেয়ে বড় কিছুতে ধাক্কা খেলে নিজেই থেমে/ধ্বংস হয়ে যায়। সবচেয়ে কাছের প্রতিপক্ষ আগে — মানেই stack।

7. Visual explanation

[10, 2, -5]-এ stack কীভাবে বদলায় (top ডানে):

a    action                                            stack
10   a>0 -> সরাসরি push                                [10]
2    a>0 -> সরাসরি push                                [10, 2]
-5   a<0, top=2>0 -> ধাক্কা; |a|=5 > 2 -> 2 মরে, pop   [10]
     a<0, top=10>0 -> ধাক্কা; |a|=5 < 10 -> a মরে      [10]
end  বেঁচে আছে                                          [10]

আর [8, -8] — সমান size:

8    a>0 -> push                                       [8]
-8   a<0, top=8>0 -> ধাক্কা; 8 == |−8| -> দুজনেই মরে   []
end                                                    []

8. Example input and output

Input : [5, 10, -5]   -> Output: [5, 10]
Input : [8, -8]       -> Output: []
Input : [10, 2, -5]   -> Output: [10]

Edge case 1 (কেউ মুখোমুখি নয়): [-2, -1, 1, 2] -> [-2, -1, 1, 2]
Edge case 2 (সমান, পরস্পর ধ্বংস): [5, -5]      -> []
Edge case 3 (সব এক দিকে)       : [1, 2, 3]     -> [1, 2, 3]

9. Brute force thinking

সরল চিন্তা: পুরো list বারবার scan করো; যেখানেই পাশাপাশি + তারপর - (asteroids[i] > 0 আর asteroids[i+1] < 0) পাও, সেই জোড়ার সংঘর্ষ মিটিয়ে list থেকে মৃতদের সরাও; কোনো পরিবর্তন না হওয়া পর্যন্ত repeat করো।

[10, 2, -5] -> (2,-5) ধাক্কা -> [10, -5] -> (10,-5) ধাক্কা -> [10] -> থামো

10. Why brute force is slow

প্রতিবার একটা সংঘর্ষের পর list ছোট হয় আর আবার গোড়া থেকে scan লাগে, কারণ একটা ধ্বংস নতুন একটা পাশাপাশি-জোড়া তৈরি করতে পারে। সবচেয়ে খারাপ ক্ষেত্রে এটা O(n^2), আর মাঝখান থেকে element মোছার খরচও আছে। stack দিয়ে একবার hাঁটাতেই O(n)-তে হয়।

11. Key observation

মূল observation: একটা নতুন বামগামী asteroid-এর ভাগ্য শুধু stack-এর top-এর উপর নির্ভর করে — তার নিচে কী আছে, সেটা পরে দেখা যাবে যদি top মরে যায়। তাই "সবচেয়ে কাছের প্রতিপক্ষ আগে" — এই local rule বারবার প্রয়োগ করলেই পুরো chain ঠিকঠাক মিটে যায়।

12. Optimized intuition

list-এ একবার hাঁটো, একটা stack রেখে। প্রতিটা asteroid a-র জন্য একটা alive flag ধরো। যতক্ষণ a বামগামী আর top ডানগামী, ততক্ষণ ধাক্কা: top ছোট হলে top pop করে এগোও; সমান হলে top pop করে a-ও মরল (alive = False); top বড় হলে a মরল (alive = False)। loop শেষে a যদি এখনো alive, তাকে push করো।

13. Thinking tweak

মোচড়: এটাকে "একটা গোটা list-এর সংঘর্ষ সিমুলেশন" না ভেবে ভাবো "প্রতিটা নতুন বামগামী asteroid শুধু একটা ছোট যুদ্ধ লড়ছে — top-এর সাথে, একবারে একজন"। বড় সমস্যাটা তখন একগুচ্ছ ছোট, local, top-only সিদ্ধান্তে ভেঙে যায়।

14. Step-by-step dry run

Input [5, 10, -5]:

  1. a = 5 — ডানগামী, কোনো ধাক্কা নেই, push → stack = [5]
  2. a = 10 — ডানগামী, push → stack = [5, 10]
  3. a = -5 — বামগামী, top 10 > 0 ধাক্কা; |−5| = 5 < 10 → a মরল, alive = False; while থামে
  4. a মৃত, push হয় না → stack = [5, 10]
  5. list শেষ → return [5, 10]

15. Python solution

def asteroid_collision(asteroids):
    stack = []                                   # টিকে থাকা asteroid
    for a in asteroids:
        alive = True
        # বামগামী a, top ডানগামী হলেই মুখোমুখি সংঘর্ষ
        while alive and a < 0 and stack and stack[-1] > 0:
            top = stack[-1]
            if top < -a:
                stack.pop()                      # top ছোট -> মরে, a এগোয়
            elif top == -a:
                stack.pop()                      # সমান -> দুজনেই মরে
                alive = False
            else:
                alive = False                    # top বড় -> a মরে
        if alive:
            stack.append(a)                      # টিকে গেলে যোগ দাও
    return stack

# ---- tests ----
assert asteroid_collision([5, 10, -5]) == [5, 10]
assert asteroid_collision([8, -8]) == []
assert asteroid_collision([10, 2, -5]) == [10]
assert asteroid_collision([-2, -1, 1, 2]) == [-2, -1, 1, 2]   # কেউ মুখোমুখি নয়
assert asteroid_collision([5, -5]) == []                      # সমান, পরস্পর ধ্বংস
assert asteroid_collision([1, 2, 3]) == [1, 2, 3]             # সব এক দিকে
print("সব test pass!")

16. Line-by-line code explanation

  • stack = [] — এ পর্যন্ত টিকে থাকা asteroid বাঁ-থেকে-ডান order-এ।
  • alive = True — ধরে নিই নতুন a বাঁচবে, যতক্ষণ না কোনো ধাক্কায় মরে।
  • while alive and a < 0 and stack and stack[-1] > 0: — সংঘর্ষের একমাত্র শর্ত: a বামগামী আর top ডানগামী।
  • if top < -a: — top-এর size ছোট (-a মানে a-এর size), তাই top pop, a এগিয়ে পরের top-এর সাথে লড়বে।
  • elif top == -a: — সমান size, top pop আর a-ও মরল।
  • else: alive = False — top বড়, a মরল, top টিকে থাকল।
  • if alive: stack.append(a) — সব ধাক্কা পেরিয়ে বেঁচে থাকলে stack-এ যোগ।

17. Output walkthrough

asteroid_collision([10, 2, -5]) → -5 প্রথমে 2-কে মারে, তারপর 10-এর কাছে নিজে মরে, ফল [10]। asteroid_collision([-2, -1, 1, 2]) → কোনো + তারপর - জোড়া নেই, তাই while কখনো চলে না, সবাই বাঁচে। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity

O(n) — প্রতিটা asteroid বড়জোর একবার push আর একবার pop হয়; while nested দেখালেও মোট pop সংখ্যা n ছাড়ায় না।

19. Space complexity

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (কোনো সংঘর্ষ নেই, যেমন [1,2,3] বা [-1,-2,-3]) সব asteroid stack-এ জমে।

20. Common mistakes

  • -a (size) আর a (signed value) গুলিয়ে ফেলা — তুলনা করতে হয় size নিয়ে, তাই বামগামী-র জন্য -a ব্যবহার করো।
  • alive flag ভুলে যাওয়া — a মরে গেলেও পরে ভুল করে push করে ফেলা একটা সাধারণ bug।
  • ভুল দিকে সংঘর্ষ ধরা — শুধু top > 0 and a < 0 সংঘর্ষ; + +, - -, বা - + কখনো মুখোমুখি নয়।

21. Which basic problem this inherits from

ভিত্তি: stack simulation + monotonic-stack-এর "নতুন এসে দুর্বলদের সরায়" idea (Problem 9-এর আত্মীয়)। chapter-এর ../patterns.md-এর Pattern 4-এর domination-চিন্তা এখানে সংঘর্ষ রূপে ফিরে আসে — শুধু resolve মানে answer নয়, ধ্বংস।

22. Similar harder problems

23. Pattern learned

Stack simulation with domination: "collision", "survive", "destroy", "knock out" দেখলে stack-এ টিকে থাকা element রাখো; নতুন element top-এর সাথে লড়ে — হয় top সরায়, নয় নিজে মরে, নয় দুজনেই; তারপর বেঁচে থাকলে যোগ দেয়।

24. Final summary

ভবিষ্যতের আমাকে: সংঘর্ষ শুধু + তারপর -। নতুন বামগামী asteroid top-এর সাথে একে একে লড়ে; size তুলনায় ছোট মরে, সমান হলে দুজনেই, বড় হলে আক্রমণকারী মরে। alive flag মনে রেখো। "asteroid", "collision", "survive" দেখলে stack simulation ভাববে।

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