কনটেন্টে যান

006 — Move Zeroes

Problem link ও উৎস

  • Original source: Classic two-pointer (slow/fast) exercise
  • Platform: LeetCode — https://leetcode.com/problems/move-zeroes/
  • Topic: array
  • Difficulty: Easy
  • Pattern: two pointers (slow/fast, same direction)
  • Basic idea inherited from: remove-duplicates-এর skeleton — slow write-pointer + fast read-pointer

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

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

একটা integer array nums দেওয়া। সব 0 কে array-র শেষে পাঠাও, আর non-zero গুলোর relative order ঠিক রেখে। কাজটা in place — নতুন array না বানিয়ে।

উদাহরণ
nums = [0, 1, 0, 3, 12]  ->  [1, 3, 12, 0, 0]
(1, 3, 12 আগের order-এই; zero গুলো শেষে)

Input ও output

উদাহরণ
Input : [0, 1, 0, 3, 12]  -> [1, 3, 12, 0, 0]

Edge case 1 (সব zero):   [0, 0, 0] -> [0, 0, 0]
Edge case 2 (zero নেই):  [1, 2, 3] -> [1, 2, 3]
Edge case 3 (একটা):      [0]       -> [0]

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

একটা ট্রে-তে কিছু পূর্ণ গ্লাস আর কিছু খালি গ্লাস এলোমেলো। তুমি চাও পূর্ণ গ্লাসগুলো (একই order-এ) সামনে চলে আসুক, খালিগুলো পেছনে জমুক। বাঁ থেকে হাঁটতে হাঁটতে পূর্ণ গ্লাস পেলেই সামনের পরের ফাঁকা জায়গায় এনে রাখো; খালি গ্লাস পেলে এড়িয়ে যাও।

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

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

হুবহু problem 4 (remove duplicates)-এর slow/fast skeleton। সেখানে শর্ত ছিল "নতুন value কিনা"; এখানে শর্ত "non-zero কিনা"। slow বলে পরের non-zero কোথায় বসবে, fast পুরো array scan করে। একই কঙ্কাল, শুধু শর্ত বদল।

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

লুকানো logic একটা invariant: nums[0..slow-1] সবসময় এ পর্যন্ত পাওয়া সব non-zero, order ঠিক রেখে। fast যখন non-zero পায়, সেটাকে slow-এ এনে slow এক বাড়াই। শেষে slow থেকে array-র শেষ পর্যন্ত সব আপনাআপনি zero (swap version-এ zero গুলো পিছনে চলে যায়)।

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

কোনো extra structure লাগে না — array আছে, আর দুটো integer pointer (slow, fast)। O(1) extra space।

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

array O(1) index access/swap দেয়, তাই non-zero element-কে সরাসরি সামনের সঠিক ঘরে swap করা যায়। order রক্ষা পায় কারণ আমরা বাঁ-থেকে-ডান একই ক্রমে non-zero গুলো বসাই — কোনো structure-এ আলাদা করে জমা রাখার দরকার নেই।

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

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

প্রথম সরল চিন্তা: সব non-zero নতুন list-এ তুলে নাও, পেছনে যত zero দরকার ততগুলো জুড়ে দাও, তারপর nums-এ copy করো।

উদাহরণ
out = [x for x in nums if x != 0]
out += [0] * (len(nums) - len(out))
nums[:] = out

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

এটা ঠিক কাজ করে কিন্তু O(n) extra space নেয় (নতুন list)। problem in place, O(1) space চায়। আলাদা list-এর দরকার নেই — একটা write-pointer দিয়ে array-র ভেতরেই non-zero সামনে আনা যায়।

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

মূল observation: zero "সরানোর" দরকার নেই; শুধু non-zero গুলো order ঠিক রেখে সামনে packing করলেই zero গুলো এমনিতেই পেছনে চলে যায়। (swap করলে zero নিজে থেকে slow-এর ঘরে গিয়ে বসে।)

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

slow=0। fast পুরো array-তে হাঁটে। nums[fast] non-zero হলে nums[slow]-এর সাথে swap করো আর slow এক বাড়াও। zero হলে কিছু না করে এগিয়ে যাও। শেষে non-zero গুলো সামনে (order সহ), zero গুলো পেছনে।

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

মোচড়: "zero গুলো শেষে ঠেলব" ভাবার বদলে ভাবো "non-zero গুলো সামনে টানব।" তখন remove-duplicates-এর সেই একই slow/fast packing কাজে লেগে যায় — শুধু শর্ত != 0।

ছবিতে বোঝা

nums = [0, 1, 0, 3, 12] (swap version, slow = পরের non-zero যেখানে বসবে):

উদাহরণ
slow=0
f=0: nums[0]=0  -> skip
f=1: nums[1]=1  -> swap(0,1)  [1,0,0,3,12]  slow=1
f=2: nums[2]=0  -> skip
f=3: nums[3]=3  -> swap(1,3)  [1,3,0,0,12]  slow=2
f=4: nums[4]=12 -> swap(2,4)  [1,3,12,0,0]  slow=3

ফল: [1,3,12,0,0]

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

Input [0, 1, 0, 3, 12]:

  1. slow=0। fast=0: nums[0]=0 → skip।
  2. fast=1: nums[1]=1 non-zero → swap nums[0],nums[1] → [1,0,0,3,12]; slow=1।
  3. fast=2: nums[2]=0 → skip।
  4. fast=3: nums[3]=3 non-zero → swap nums[1],nums[3] → [1,3,0,0,12]; slow=2।
  5. fast=4: nums[4]=12 non-zero → swap nums[2],nums[4] → [1,3,12,0,0]; slow=3। ফল [1,3,12,0,0]।

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

Python

Python
def move_zeroes(nums):
    slow = 0                              # পরের non-zero যেখানে বসবে
    for fast in range(len(nums)):
        if nums[fast] != 0:               # non-zero পেলাম
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
    return nums

# ---- tests ----
a = [0, 1, 0, 3, 12]
move_zeroes(a)
assert a == [1, 3, 12, 0, 0]

b = [0, 0, 0]
move_zeroes(b)
assert b == [0, 0, 0]                     # সব zero

c = [1, 2, 3]
move_zeroes(c)
assert c == [1, 2, 3]                     # zero নেই
print("সব test pass!")

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

  • slow = 0 — পরের non-zero কোন ঘরে বসবে তার write-pointer।
  • for fast in range(len(nums)) — পুরো array একবার scan।
  • if nums[fast] != 0 — শুধু non-zero হলেই কাজ।
  • nums[slow], nums[fast] = nums[fast], nums[slow] — non-zero-কে সামনে আনি; zero (থাকলে) পেছনে চলে যায়।
  • slow += 1 — পরের non-zero-র জন্য জায়গা এক ঘর এগোলো।

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

[0,1,0,3,12]: 1, 3, 12 ক্রমে সামনে swap হয়ে [1,3,12,0,0] — assert pass। সব-zero array swap-এ অপরিবর্তিত; zero-নেই array-তে প্রতিটা element নিজের সাথে swap হয়ে অপরিবর্তিত। শেষে print: সব test pass!।

JavaScript ও test cases

slow/fast same-direction two pointers — non-zero পেলে slow-এ swap করে slow এগোই; zero এড়িয়ে যাই।

JavaScript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function moveZeroes(nums) {
  let slow = 0;                                   // পরের non-zero যেখানে বসবে
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];  // non-zero সামনে
      slow++;
    }
  }
  return nums;
}

// ---- test cases (file-এর example + edge case) ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(moveZeroes([0, 1, 0, 3, 12]), [1, 3, 12, 0, 0]), "basic");
assert(eq(moveZeroes([0, 0, 0]), [0, 0, 0]), "সব zero");
assert(eq(moveZeroes([1, 2, 3]), [1, 2, 3]), "zero নেই");
assert(eq(moveZeroes([0]), [0]), "একটা");
assert(eq(moveZeroes([1, 0, 2, 0, 3]), [1, 2, 3, 0, 0]), "mixed, order রক্ষা");
console.log("সব JS test pass!");

JS টীকা: swap [a, b] = [b, a] (destructuring) — temp লাগে না, in-place থাকে, তাই O(1) extra space। zero-element-এ slow বাড়িও না (তখন zero "valid" ধরা পড়ে packing ভাঙবে)। non-zero গুলো বাঁ-থেকে-ডান একই ক্রমে বসে বলে relative order অটুট।

TypeScript ও test cases

TypeScript
function moveZeroes(nums: number[]): number[] {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
  return nums;
}

function expectArr(actual: number[], expected: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(expected)) {
    throw new Error(`FAIL ${msg}: [${actual}]`);
  }
}

expectArr(moveZeroes([0, 1, 0, 3, 12]), [1, 3, 12, 0, 0], "basic");
expectArr(moveZeroes([0, 0, 0]), [0, 0, 0], "all zero");
expectArr(moveZeroes([1, 2, 3]), [1, 2, 3], "no zero");
console.log("সব TS test pass!");

TS টীকা: nums: number[] declare করায় in-place mutation-এর target স্পষ্ট; ভুলে readonly tuple বা অন্য টাইপ পাঠালে compile-time-এ ধরা পড়ে।

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

সময়

O(n) — fast array-তে একবার হাঁটে; প্রতিটা step O(1)।

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

O(1) — শুধু দুটো pointer; swap array-র ভেতরেই।

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

  • order ভেঙে ফেলা — non-zero গুলো sort/অদলবদল করা; problem relative order রাখতে বলে।
  • শুধু non-zero সামনে লিখে বাকি ঘর zero করতে ভুলে যাওয়া (write-only version-এ) — swap version-এ এই সমস্যা নেই।
  • zero-element-এও slow বাড়িয়ে দেওয়া — তখন zero-ও "valid" ধরা পড়ে, packing ভুল হয়।

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

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

ভিত্তি: problem 4 (remove duplicates)-এর slow/fast packing; শর্ত বদলে "non-zero কিনা"। দুটোই Pattern 1-এর same-direction two pointers-এর রূপ। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" দেখো।

পরের অনুশীলন

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

Slow/fast partition (stable compaction): একটা শর্ত মানা element গুলো order ঠিক রেখে সামনে packing, বাকিরা পেছনে — এক pass, O(1) space।

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

ভবিষ্যতের আমাকে: "move zeroes = non-zero সামনে pack করা (slow/fast), zero নিজে থেকে পেছনে।" "keep order, push some to the end" দেখলেই এই slow/fast partition মনে করবে।

কোথায় কাজে লাগে

  • Stable filtering/compaction: কিছু element order রেখে সামনে, বাকি পেছনে — UI list-এ active item আগে, archived পরে।
  • Garbage/null packing: array থেকে null/empty slot পেছনে ঠেলে valid data সামনে compact করা (memory pool, free-list)।
  • Partition step: quicksort partition, Dutch national flag (Sort Colors) — same-direction two-pointer-এর জ্ঞাতি।
  • Stream cleanup: invalid/zero রেকর্ড সরিয়ে valid গুলো এক pass-এ সাজানো। মূল pattern — "শর্ত-মানা element order রেখে সামনে pack করা (slow write + fast read, O(1) space)" — filter-in-place, partition, remove-duplicates জুড়ে বড় ছবিতে ফেরে।

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