Top Interview 150

Rotating an array is a fundamental problem that tests your ability to optimize space and time usage. Let's tackle LeetCode 189: Rotate Array, understand its nuances, and implement an efficient solution.

🚀 Problem Description

Given an integer array nums, rotate the array to the right by k steps.

• Key Constraints:
  • Perform the rotation in-place, meaning no extra array for storage.
  • 1 ≤ nums.length ≤ 10*5

💡 Examples

Example 1

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

Example 2

Input: nums = [-1,-100,3,99], k = 2  
Output: [3,99,-1,-100]

🧠 Key Insights

• Circular Rotation: Rotating by k steps is equivalent to slicing and concatenating, but achieving this in-place is tricky.
• Modular Arithmetic: Since rotating by k steps is the same as rotating by k % nums.length, unnecessary full rotations can be avoided.

🏆 JavaScript Solution

This solution uses a reverse strategy for optimal in-place rotation.

Reverse Strategy

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining elements.

var rotate = function(nums, k) {
    k = k % nums.length;
    if (k === 0) return;

    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
};

function reverse(arr, start, end) {
    while (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]];        
        start++;
        end--;
    }
}

🔍 How It Works

• Reverse the array:
  Turns [1,2,3,4,5,6,7] into [7,6,5,4,3,2,1].

• Reverse the first k elements:
  Turns [7,6,5] into [5,6,7].

• Reverse the rest:
  Turns [4,3,2,1] into [1,2,3,4].
  Final Output: [5,6,7,1,2,3,4].

🔑 Complexity Analysis

• > Time Complexity: O(n), as each reverse operation takes O(n), and there are three operations.
• > Space Complexity:O(1), as no extra memory is used.

📋 Dry Run

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

Output: [5,6,7,1,2,3,4]

✨ Pro Tips for Interviews

1. Understand modular arithmetic: Reducing k to k % nums.length is crucial for efficiency.
2. Edge cases: Consider arrays with one element or when k = 0.
3. Explain the reverse strategy: It’s optimal and clean for in-place array rotation.

📚 Learn More

For a detailed walkthrough and explanation, check out my Dev.to post:
👉 Majority Element - JavaScript Solution

Let me know your thoughts! How would you approach this problem? 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving