013 — Rotate Array¶

Source¶

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 করে একটা অংশ উল্টানো

1. Problem in simple words¶

একটা 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]

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

লুকানো 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 মানে কিছুই না বদলানো।

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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-এ

8. Example input and 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    -> []

9. Brute force thinking¶

প্রথম সরল চিন্তা: একটা নতুন 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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

15. Python solution¶

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

16. Line-by-line code explanation¶

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 ঠিক করা।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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।

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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/

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "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।

25. JavaScript solution (with test cases)¶

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

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।

26. TypeScript solution (with test cases)¶

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 ভুল হওয়ার সুযোগ নেই।

27. কোথায় কাজে লাগে (real-world use)¶

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।