013 — Rotate Array

Problem link ও উৎস

• Original source: Classic in-place rotation exercise
• Platform: LeetCode — https://leetcode.com/problems/rotate-array/
• Topic: array
• Difficulty: Medium
• Pattern: triple reversal (তিনবার reverse করে O(1) space rotation)
• Basic idea inherited from: in-place reversal (problem 1) — দুই প্রান্ত থেকে swap করে একটা অংশ উল্টানো

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

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

একটা array nums আর একটা সংখ্যা k দেওয়া। array-কে ডানে k ঘর rotate করতে হবে, অর্থাৎ শেষের k-টা element সামনে চলে আসবে আর বাকিরা পিছিয়ে যাবে। শর্ত: কাজটা in place করো, O(1) extra space-এ।

উদাহরণ

nums = [1, 2, 3, 4, 5, 6, 7], k = 3
শেষের 3-টা (5,6,7) সামনে আসবে
ফল: [5, 6, 7, 1, 2, 3, 4]

Input ও output

উদাহরণ

Input : [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]
Input : [-1,-100,3,99], k=2  -> [3,99,-1,-100]

Edge case 1 (k > n): [1,2], k=3 -> [2,1]   (k%n = 1, ডানে 1 ঘর)
Edge case 2 (খালি):  [], k=2    -> []

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

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

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

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

ভিত in-place reversal (problem 1)। reverse-এ যেমন দুই প্রান্ত থেকে swap করে একটা অংশ উল্টানো হয়, এখানে সেই reverse-কেই building block বানিয়ে তিনবার ডাকা হয়। কোনো temporary array লাগে না — শুধু দুই-প্রান্ত swap-এর পুনর্ব্যবহার। chapter-এর ../patterns.md-এর "Pattern 4 — In-Place Reversal and Rotation" দেখো।

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

লুকানো logic: পুরো array reverse করলে শেষের k-টা element সামনে চলে আসে, কিন্তু উল্টো order-এ; আবার মাঝখানে দুই block-এর ভেতরের order-ও উল্টে যায়। তাই (1) পুরোটা reverse, (2) প্রথম k-টা reverse করে তাদের order ঠিক, (3) বাকি n-k-টা reverse করে তাদের order ঠিক — সব মিলিয়ে block দুটো জায়গা বদলায় কিন্তু ভেতরের order forward থাকে। আর k %= n, কারণ n ঘর rotate মানে কিছুই না বদলানো।

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

কোনো extra data structure লাগে না — array-টা already আছে, আর reverse-এর জন্য দুটো integer pointer। O(1) extra space।

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

Array mutable আর O(1) random access — তাই যেকোনো sub-range-এর দুই প্রান্ত সরাসরি ছুঁয়ে swap করা যায়। তিনটা reverse মিলিয়ে rotation হয়ে যায় কোনো নতুন array না বানিয়ে, যা problem-এর O(1) space দাবি মেটায়।

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

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

প্রথম সরল চিন্তা: একটা নতুন array নাও, প্রতিটা element-কে তার নতুন জায়গায় ((i + k) % n) বসাও, তারপর copy করে ফেরত দাও।

উদাহরণ

res = new array size n
for i in range(n):
    res[(i + k) % n] = nums[i]
copy res back into nums

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

এটা ঠিক উত্তর দেয়, কিন্তু O(n) extra space (নতুন array) নেয়, অথচ problem চায় O(1)। আরেকটা সরল উপায় — একবারে এক ঘর করে k বার rotate — সেটা O(n*k) time, k বড় হলে ভয়ংকর ধীর।

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

মূল observation: reversal দিয়ে rotation করা যায়। পুরো array reverse করলে দুই block জায়গা বদলায় (কিন্তু ভেতরে উল্টো); তারপর দুই block আলাদা করে reverse করলে ভেতরের order ঠিক হয়ে যায়। অর্থাৎ rotation = তিনটা reversal, কোনো temp array ছাড়াই।

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

আগে k %= n করো (k বড় হলেও সামলায়, আর n ঘর rotate = identity)। তারপর তিনটা reverse: পুরোটা [0, n-1], এরপর [0, k-1], এরপর [k, n-1]। প্রতিটা reverse দুই-প্রান্ত swap, সব মিলিয়ে O(n) time, O(1) space।

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

মোচড়: "rotate করতে নিশ্চয়ই temporary array লাগবে" ভাবার বদলে মনে করো "দুইবার reverse করলে একটা block আবার সোজা হয়, কিন্তু জায়গা বদলে ফেলে।" তখন শুধু in-place reverse-ই যথেষ্ট।

ছবিতে বোঝা

nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

উদাহরণ

reverse all:        [7, 6, 5, 4, 3, 2, 1]
reverse first k=3:  [5, 6, 7, 4, 3, 2, 1]
reverse last n-k=4: [5, 6, 7, 1, 2, 3, 4]   <- done
শেষের 3-টা সামনে এসে গেছে, প্রতিটা গুচ্ছ আবার forward order-এ

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

Input [-1, -100, 3, 99], k = 2 (n = 4, k % n = 2):

1. reverse পুরোটা [0,3]: [99, 3, -100, -1]।
2. reverse প্রথম k=2 [0,1]: [3, 99, -100, -1]।
3. reverse বাকি [2,3]: [3, 99, -1, -100]।
4. ফল: [3, 99, -1, -100]।

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

Python

Python

def rotate(nums, k):
    n = len(nums)
    if n == 0:
        return nums
    k %= n                              # k > n হলেও ঠিক; n ঘর rotate = কিছু না
    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1
    reverse(0, n - 1)                   # পুরোটা উল্টাও
    reverse(0, k - 1)                   # প্রথম k উল্টাও
    reverse(k, n - 1)                   # বাকিটা উল্টাও
    return nums

# ---- tests ----
assert rotate([1, 2, 3, 4, 5, 6, 7], 3) == [5, 6, 7, 1, 2, 3, 4]
assert rotate([-1, -100, 3, 99], 2) == [3, 99, -1, -100]
assert rotate([1, 2], 3) == [2, 1]      # k > n
assert rotate([1], 0) == [1]            # k = 0
assert rotate([], 2) == []              # খালি
print("সব test pass!")

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

• if n == 0: return nums — খালি array-তে কিছু করার নেই (k %= 0 crash এড়াতেও জরুরি)।
• k %= n — k বড় হলে wrap করে; n ঘর rotate মানে অপরিবর্তিত, তাই modulo।
• def reverse(lo, hi) — দুই-প্রান্ত swap করে [lo, hi] অংশ উল্টায় (problem 1-এর সেই reverse)।
• reverse(0, n-1) — পুরো array উল্টানো।
• reverse(0, k-1) — সামনে আসা block-এর order ঠিক করা।
• reverse(k, n-1) — পিছনে যাওয়া block-এর order ঠিক করা।

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

[1..7], k=3 → তিনটা reverse-এর পর [5,6,7,1,2,3,4], assert pass। [-1,-100,3,99], k=2 → [3,99,-1,-100]; [1,2], k=3 → k%2=1, ডানে 1 ঘর [2,1]; [1], k=0 → k%1=0, সব reverse no-op [1]; [] → early return []। শেষে print: সব test pass!।

JavaScript ও test cases

তিনটা in-place reverse দিয়ে rotation — array equality test-এ JSON.stringify।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// rotate right by k, in place (triple reversal)
function rotate(nums, k) {
  const n = nums.length;
  if (n === 0) return nums;
  k %= n;                              // k > n হলেও ঠিক; n ঘর rotate = কিছু না
  const reverse = (lo, hi) => {
    while (lo < hi) {
      [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
      lo++; hi--;
    }
  };
  reverse(0, n - 1);                   // পুরোটা উল্টাও
  reverse(0, k - 1);                   // প্রথম k উল্টাও
  reverse(k, n - 1);                   // বাকিটা উল্টাও
  return nums;
}
// ---- test cases (example + edge) ----
assert(eq(rotate([1, 2, 3, 4, 5, 6, 7], 3), [5, 6, 7, 1, 2, 3, 4]), "k=3");
assert(eq(rotate([-1, -100, 3, 99], 2), [3, 99, -1, -100]), "negatives");
assert(eq(rotate([1, 2], 3), [2, 1]), "k>n");                  // edge
assert(eq(rotate([1], 0), [1]), "k=0");
assert(eq(rotate([], 2), []), "empty");                        // edge
console.log("সব JS test pass!");

JS টীকা: array সমান কিনা === দিয়ে যাচাই হয় না (reference compare), তাই JSON.stringify(a) === JSON.stringify(b)। swap-এ destructuring [a, b] = [b, a] idiomatic। n === 0 guard আগে রাখো, নইলে k %= 0 দিলে NaN।

TypeScript ও test cases

TypeScript

function rotate(nums: number[], k: number): number[] {
  const n = nums.length;
  if (n === 0) return nums;
  k %= n;
  const reverse = (lo: number, hi: number): void => {
    while (lo < hi) {
      [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
      lo++; hi--;
    }
  };
  reverse(0, n - 1);
  reverse(0, k - 1);
  reverse(k, n - 1);
  return nums;
}
function expectArr(actual: number[], exp: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(exp))
    throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(rotate([1, 2, 3, 4, 5, 6, 7], 3), [5, 6, 7, 1, 2, 3, 4], "k=3");
expectArr(rotate([1, 2], 3), [2, 1], "k>n");
expectArr(rotate([], 2), [], "empty");
console.log("সব TS test pass!");

TS টীকা: nums: number[] আর return number[] declare করায় helper expectArr শুধু সঠিক type-এর array গ্রহণ করে; nested reverse closure-এ lo/hi-ও number বলে index ভুল হওয়ার সুযোগ নেই।

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

সময়

O(n) — তিনটা reverse মিলিয়ে প্রতিটা element ধ্রুবসংখ্যকবার swap হয়।

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

O(1) — শুধু reverse-এর দুটো pointer; কোনো extra array নয়।

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

• k %= n ভুলে যাওয়া — k >= n হলে reverse(0, k-1) index out of range বা ভুল ফল দেবে।
• খালি array-তে k %= n করা — n = 0 হলে ZeroDivisionError; আগে n == 0 check করো।
• reverse-এর order বা সীমানা গুলিয়ে ফেলা — মনে রাখো: পুরোটা, তারপর প্রথম k, তারপর বাকি n-k।

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

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

ভিত্তি: in-place two-pointer reversal (Reverse String #1)। সেই reverse-ই এখানে তিনবার ডাকা হয়। chapter-এর ../patterns.md-এর "Pattern 4 — In-Place Reversal and Rotation" দেখো।

পরের অনুশীলন

• Reverse String (একটাই reverse) — https://leetcode.com/problems/reverse-string/ (#1)
• Reverse Words in a String — https://leetcode.com/problems/reverse-words-in-a-string/
• Rotate List (linked list rotation) — https://leetcode.com/problems/rotate-list/

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

Triple reversal: "rotate by k, O(1) space" দেখলে temp array নয় — পুরোটা reverse, প্রথম k reverse, বাকি reverse। দুইবার reverse করলে একটা block forward order-এ ফিরে আসে কিন্তু জায়গা বদলায়।

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

ভবিষ্যতের আমাকে: "rotate ডানে k = reverse all → reverse first k → reverse rest; আগে k %= n।" "in-place rotate, O(1) space" দেখলেই triple-reversal মনে করবে — O(n) time, O(1) space।

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

• Circular buffer / ring buffer: স্থির আকারের buffer-এ data shift করা ছাড়াই logical rotation।
• Carousel / image slider UI: slide গুলো ডানে/বাঁয়ে rotate করে দেখানো, extra array না বানিয়ে।
• Round-robin scheduling: task queue-কে k ধাপ ঘুরিয়ে পরবর্তী cycle শুরু করা।
• Cryptography: rotation cipher (Caesar-জাতীয়) ও bit-rotation primitive।
• Audio/video loop: sample buffer phase-shift করে playback offset দেওয়া।
• Game boards: tile/row cyclic shift (যেমন 2048-এর row rotate) in place।

মূল pattern: temp array না বানিয়ে তিন reverse-এ rotation — "rotate by k, O(1) space" দেখলেই triple-reversal।

---

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