কনটেন্টে যান

011 — Asteroid Collision

Problem link ও উৎস

  • 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-এর সংঘর্ষ-রূপ)

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

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

তোমাকে কিছু 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]  (কেউ মুখোমুখি নয়)

Input ও 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]

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

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

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

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

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

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

লুকানো 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 সামলানো যায়।

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

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

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

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

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

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

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

উদাহরণ
[10, 2, -5] -> (2,-5) ধাক্কা -> [10, -5] -> (10,-5) ধাক্কা -> [10] -> থামো

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

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

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

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

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

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 করো।

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

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

ছবিতে বোঝা

[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                                                    []

ছোট input-এ ধাপে ধাপে

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]

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

Python

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

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

  • 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-এ যোগ।

Output মিলিয়ে দেখা

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

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

সময়

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

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

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

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

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

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

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

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

পরের অনুশীলন

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

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

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

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

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