Rotate Array
Problem Description
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
What’s the first thought that naturally comes to mind?Checking every possibility, right? When faced with a problem like this, our way is to think, "Can we simply move elements one by one to achieve the desired result?" This is where the brute force approach steps in!
Brute Force Approach
Intuition
Let’s break it down - Imagine your array is like a line of people holding cards with numbers. When you say, "Move three steps to the right," each person needs to move—but where do they go? Well, we can solve this puzzle by making a new line and placing everyone in their correct spot based on the new positions!
The idea is simple:
- Take a new array of the same size.
- Place each element of the original array into its new position in the new array.
- Once the new array is filled, copy everything back to the original array.
But wait—how do we decide the new position for each element?Let’s say the array size is n, and we’re rotating by k steps. The new position for an element at index i can be calculated as:
new_index = (i + k) % n
How this '%' help us?
Okay fine, Let’s understand how this “%” help us by having one example,
Array: [A, B, C, D, E] (n = 5)Start at i = 3 (D), move k = 4 steps:
- New index = i + k = 3 + 4 = 7.
- Issue: Index 7 is out of bounds.But, as per we want index 2 right!
Same array, start at i = 3 (D), move k = 4 steps:
- New index = (i + k) % n = (3 + 4) % 5 = 2.
- Wraps around to index 2 (C). This is the actual index we want.
So,this formula ensures the indices wrap around, making the rotation cyclic.
Let’s make it understandable with same previous scenario in which every person in the queue holding one integer as shown below:
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Step-by-Step Execution:
- Prepare the new array:Think of this as a blank slate where we’ll rearrange everything.New array: [_, _, _, _, _, _, _]
- Position each element:For each element in the original array, calculate its new position and place it in the new array.
i = 0: Element 1 → New index = (0 + 3) % 7 = 3New array: [_, _, _, 1, _, _, _]
i = 1: Element 2 → New index = (1 + 3) % 7 = 4New array: [_, _, _, 1, 2, _, _]
.
.
.
.
i = 5: Element 6 → New index = (5 + 3) % 7 = 1New array: [5, 6, _, 1, 2, 3, 4]
i = 6: Element 7 → New index = (6 + 3) % 7 = 2New array: [5, 6, 7, 1, 2, 3, 4]
- Copy the new array back to the original array:Now, take all the elements from the new array and overwrite the original array.Final array: [5, 6, 7, 1, 2, 3, 4]
We literally just "picked up" every number and placed it exactly where it needed to be. It’s like arranging books on a shelf, ensuring each one is in the correct spot. We didn’t skip any possibilities—we checked every element and ensured it landed exactly where it belonged.
Approach
Step 1: Initialize a New Array - Create a new array of the same size as the original array to store the rearranged elements.
Step 2: Calculate New Positions - For every element in the original array, calculate its new position using the formula for every position by iterating through each index using for loop:
- new_index = (current_index + k) % nHere, n is the size of the array, and % ensures the indices wrap around, keeping the rotation cyclic.
Step 3: Place Elements in the New Array - For each element in the original array, determine its new_index and place it in the corresponding position in the new array.
Step 4: Copy Back to the Original Array - Once all elements
Dry Run
Input:
nums = [10, 20, 30, 40, 50, 60], k = 4
Output:nums = [40, 50, 60, 10, 20, 30]
Explanation:After the rotations the array becomes [40, 50, 60, 10, 20, 30]
Step-by-Step Execution:
Initialize New Array:Create a new array of the same size as the original array:new_array = [_, _, _, _, _, _]
Calculate New Positions:For each element in nums, calculate the new index using the formula, new_index = (current_index + k) % n, where n is the length of the array (6 in this case).
For i = 0 (Element 10):New index = (0 + 4) % 6 = 4Place 10 at index 4 in new_array:new_array = [_, _, _, _, 10, _]
- For i = 1 (Element 20):New index = (1 + 4) % 6 = 5Place 20 at index 5 in new_array:new_array = [_, _, _, _, 10, 20]
- For i = 2 (Element 30):New index = (2 + 4) % 6 = 0Place 30 at index 0 in new_array:new_array = [30, _, _, _, 10, 20]
- For i = 3 (Element 40):New index = (3 + 4) % 6 = 1Place 40 at index 1 in new_array:new_array = [30, 40, _, _, 10, 20]
- For i = 4 (Element 50):New index = (4 + 4) % 6 = 2Place 50 at index 2 in new_array:new_array = [30, 40, 50, _, 10, 20]
- For i = 5 (Element 60):New index = (5 + 4) % 6 = 3Place 60 at index 3 in new_array:new_array = [30, 40, 50, 60, 10, 20]
Copy Back to the Original Array:Now, copy all elements from new_array back into nums:nums = [30, 40, 50, 60, 10, 20]
Final Output:
The rotated array is:[30, 40, 50, 60, 10, 20]
Brute Force Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
// Function to rotate the array using brute force approach
void rotate(vector<int>& nums, int k) {
int n = nums.size();
// To handle cases where k is larger than n
k = k % n;
// Create a new array to store the result
vector<int> newArray(n);
// Rotate the array by calculating the new position for each element
for (int i = 0; i < n; i++) {
newArray[(i + k) % n] = nums[i];
}
// Assign the new array back to the original array
nums = newArray;
}
};2. Java Try on Compiler
class Solution {
// Function to rotate the array using brute force approach
public void rotate(int[] nums, int k) {
int n = nums.length;
// To handle cases where k is larger than n
k = k % n;
// Create a new array to store the result
int[] newArray = new int[n];
// Rotate the array by calculating the new position for each element
for (int i = 0; i < n; i++) {
newArray[(i + k) % n] = nums[i];
}
// Assign the new array back to the original array
for (int i = 0; i < n; i++) {
nums[i] = newArray[i];
}
}
}
3. Python Try on Compiler
class Solution:
# Function to rotate the array using brute force approach
def rotate(self, nums, k):
n = len(nums)
# To handle cases where k is larger than n
k = k % n
# Create a new array to store the result
newArray = [0] * n
# Rotate the array by calculating the new position for each element
for i in range(n):
newArray[(i + k) % n] = nums[i]
# Assign the new array back to the original array
nums[:] = newArray
4. JavaScript Try on Compiler
var rotate = function(nums, k) {
const n = nums.length;
// To handle cases where k is larger than n
k = k % n;
// Create a new array to store the rotated result
let newArray = new Array(n);
// Rotate the array by calculating the new position for each element
for (let i = 0; i < n; i++) {
newArray[(i + k) % n] = nums[i];
}
// Assign the new array back to the original array
for (let i = 0; i < n; i++) {
nums[i] = newArray[i];
}
};
Time Complexity : O(n)
Generating New Array: The code iterates through the entire array once, processing each element once to calculate its new position in the rotated array. This takes O(n) time, where n is the number of elements in the array.
Assigning to the Original Array: After the new array is populated, we assign each element back to the original array, which also takes O(n) time.
Total Time Complexity: O(n) + O(n) = O(n)
Space Complexity : O(n)
Auxiliary Space Complexity: Auxiliary space is the extra space or temporary space used by the algorithm, apart from the input array.
- In this case, a new array newArray of size n is created to store the rotated result.Auxiliary Space - O(n)
Total Space Complexity
Space required by the input array is - O(n)
Auxiliary Space - O(n)
Total Space Complexity: O(n) + O(n) = O(n)
Can We Avoid Using Extra Space and Rearrange the Elements In-Place?Yes, we can avoid using extra space and rearrange the elements of the array in place by using a smarter approach involving array reversals. Let’s Analyze some examples to get an idea on the optimal approach.
Optimal Approach
Intuition
Let’s consider one example,
Input:
nums = [1, 2, 3, 4, 5, 6, 7], k = 3
We need to rotate the array k = 3 steps to the right. The expected output is:
[5, 6, 7, 1, 2, 3, 4]
Observe What Happens When Rotated
When we rotate the array by k = 3, the last 3 elements [5, 6, 7] come to the front, and the remaining elements [1, 2, 3, 4] shift to the right.
- After rotation:
The segment [5, 6, 7] is placed first.
The segment [1, 2, 3, 4] follows.
Think of a Way to Rearrange the Segments
We need to move:
- The last k elements [5, 6, 7] to the beginning.
- The first n - k elements [1, 2, 3, 4] to the end.
Okay then,let’s consider the rotated array instead of the original array.
Rotated array = [5, 6, 7, 1, 2, 3, 4].
From the above array how can we get back our original array without using the extra space? Observe carefully.
Point 1 - first we reverse the first k(3) elements
Then the rotated array becomes = [7, 6, 5, 1, 2, 3, 4]
Point 2 - We reverse the remaining elements in their own positions.
Then the rotated array becomes = [7, 6, 5, 4, 3, 2, 1]
Point 3 - then we reverse whole array we get the original array:
Then the rotated array becomes = [1, 2, 3, 4, 5, 6, 7] = original array.
Isn’t it ?
So, from the above things we have brought our original array from the output right! Can’t we go back, in which way we came to get the rotated array? Absolutely we can, from point 3, 2, 1 !See, points a and b can be interchanged during their execution as they are getting reversed in their own space right, so the order may be 3,2,1 or 3,1,2.
Okay, now let’s Consider the original array as [1, 2, 3, 4, 5, 6, 7].
Step 3 : Reverse the Entire Array
Reversing the entire array flips everything.
- Original array: [1, 2, 3, 4, 5, 6, 7]
- After reversing: [7, 6, 5, 4, 3, 2, 1]
Step 1 or 2 (let’s consider 1) : Reverse the First k Elements
Now, reverse the first k = 3 elements of the array.
- Array after reversing the first k(3) elements: [5, 6, 7, 4, 3, 2, 1]
Step 1 or 2 (Let’s consider 2 ): Reverse the Remaining n - k (4) Elements
Finally, reverse the last n - k = 4 elements.
- Array after reversing the last 4 elements: [5, 6, 7, 1, 2, 3, 4]
This is the rotated array of our original array.
Here, we can use a two-pointers approach to reverse the segments between two pointers as per our intuition by pointing one pointer at the starting and other at the ending of each segment.
Then we can reverse by Swapping the elements at these pointers, then we will move the start pointer forward and the end pointer backward. We will Repeat this process until the pointers cross, ensuring the segment is reversed efficiently.
Approach
Step 1: Handle k > n - If k > n, reduce k by calculating k % n to ensure the rotation is within the bounds of the array.
Step 2: Reverse the Entire Array - Use two pointers: one at index 0 and the other at index n-1. Reverse the entire array by reversing the segment between these two pointers inclusively.
Step 3: Reverse the First k Elements - Use two pointers: one at index 0 and the other at index k-1. Reverse the first k elements by reversing the segment between these two pointers inclusively.
Step 4: Reverse the Remaining n - k Elements - Use two pointers: one at index k and the other at index n-1. Reverse the last n - k elements by reversing the segment between these two pointers inclusively.
Step 5: Result - The array is now rotated by k steps to the right, achieved in-place without extra space.
Dry Run
Initial Array: [10, 20, 30, 40, 50, 60, 70], k=3
Steps with Pointers:
Step 1: Handle k > n
- k = 3 and n = 7 (length of the array).
- Since k < n, no need to reduce k. It remains k = 3.
Step 2: Reverse the Entire Array
- Pointers used: We start with two pointers: one at index 0 and the other at index n-1 (which is 6).
- Reverse the entire array by reversing the segment between these two pointers inclusively.
- Before reversing: [10, 20, 30, 40, 50, 60, 70]
- After reversing: [70, 60, 50, 40, 30, 20, 10]
Step 3: Reverse the First k Elements
- Pointers used: Start with two pointers: one at index 0 and the other at index k-1 (which is 2).
- Reverse the first k = 3 elements by reversing the segment between these two pointers inclusively.
- Before reversing: [70, 60, 50, 40, 30, 20, 10]
- After reversing: [50, 60, 70, 40, 30, 20, 10]
Step 4: Reverse the Remaining n - k Elements
- Pointers used: Start with two pointers: one at index k (which is 3) and the other at n-1 (which is 6).
- Reverse the last n - k = 4 elements by reversing the segment between these two pointers inclusively.
- Before reversing: [50, 60, 70, 40, 30, 20, 10]
- After reversing: [50, 60, 70, 10, 20, 30, 40]
Final Array:
The array is now rotated by 3 steps to the right:[50, 60, 70, 10, 20, 30, 40]
Optimal Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
// Function to reverse a segment of the array between two pointers
void reverseArraySegment(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
start++;
end--;
}
}
// Function to rotate the array to the right by k steps
void rotate(vector<int>& nums, int k) {
int n = nums.size();
// If the array is empty or contains only one element, no need to rotate
if (n == 0 || k == 0 || k % n == 0) {
return;
}
// Handle cases where k > n
k = k % n;
// Step 1: Reverse the entire array
reverseArraySegment(nums, 0, n - 1);
// Step 2: Reverse the first k elements
reverseArraySegment(nums, 0, k - 1);
// Step 3: Reverse the remaining n - k elements
reverseArraySegment(nums, k, n - 1);
}
};
2. Java Try on Compiler
class Solution {
// Function to reverse a segment of the array between two pointers
public void reverseArraySegment(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
// Function to rotate the array to the right by k steps
public void rotate(int[] nums, int k) {
int n = nums.length;
// If the array is empty or contains only one element, no need to rotate
if (n == 0 || k == 0 || k % n == 0) {
return;
}
// Handle cases where k > n
k = k % n;
// Step 1: Reverse the entire array
reverseArraySegment(nums, 0, n - 1);
// Step 2: Reverse the first k elements
reverseArraySegment(nums, 0, k - 1);
// Step 3: Reverse the remaining n - k elements
reverseArraySegment(nums, k, n - 1);
}
}
3. Python Try on Compiler
class Solution:
# Function to reverse a segment of the array between two pointers
def reverseArraySegment(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
# Function to rotate the array to the right by k steps
def rotate(self, nums, k):
n = len(nums)
# If the array is empty or contains only one element, no need to rotate
if n == 0 or k == 0 or k % n == 0:
return
# Handle cases where k > n
k = k % n
# Step 1: Reverse the entire array
self.reverseArraySegment(nums, 0, n - 1)
# Step 2: Reverse the first k elements
self.reverseArraySegment(nums, 0, k - 1)
# Step 3: Reverse the remaining n - k elements
self.reverseArraySegment(nums, k, n - 1)
4. JavaScript Try on Compiler
var rotate = function(nums, k) {
// To handle cases where k > nums.length
k = k % nums.length;
// Reverse the entire array
reverseArraySegment(nums, 0, nums.length - 1);
// Reverse the first k elements
reverseArraySegment(nums, 0, k - 1);
// Reverse the remaining elements
reverseArraySegment(nums, k, nums.length - 1);
};
function reverseArraySegment(arr, start, end) {
while (start < end) {
[arr[start], arr[end]] = [arr[end], arr[start]];
start++;
end--;
}
}Time Complexity : O(n)
Generating New Array: The code iterates through the entire array once, processing each element once to calculate its new position in the rotated array. This takes O(n) time, where n is the number of elements in the array.
Assigning to the Original Array: After the new array is populated, we assign each element back to the original array, which also takes O(n) time.
Total Time Complexity: O(n) + O(n) = O(n)
Space Complexity : O(1)
Auxiliary Space Complexity: Auxiliary space is the extra space or temporary space used by the algorithm, apart from the input array.
- In this case, no extra space is used,so the auxiliary time complexity is O(1)
Total Space Complexity
Input space for the original array - O(n)
Auxiliary space - O(1)
Total Space Complexity: O(n) + O(1) = O(n)
Learning Tip
You are given two strings sentence1 and sentence2, each representing a sentence composed of words.
A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of only uppercase and lowercase English characters.
Two sentences s1 and s2 are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal.
Note that the inserted sentence must be separated from existing words by spaces.
For example, s1 = "Hello Jane" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in s1.
s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, it is not separated from "Frog" by a space.
Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.
You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:
The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.
Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.