189. Rotate Array Leetcode Solution
Rotate Array Leetcode Problem :
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
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]
Rotate Array Leetcode Solution :
Constraints :
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 – 1
- 0 <= k <= 10^5
Example 1:
- Input: nums = [-1,-100,3,99], k = 2
- Output: [3,99,-1,-100]
Intuition :
Rotating an array involves shifting its elements to the right by a given number of steps. This can be done in various ways, but the provided code takes a unique approach by using list reversal. The core idea behind this approach is leveraging the power of reversal operations to achieve the rotation. By reversing the entire array and then reversing specific segments, we can effectively rotate the array.
Approach :
Here’s an approach for the given code:
Start by calculating the actual number of rotations needed. This is done by taking the modulus (%) of k with the length of the array nums. This step ensures that k is within the range of valid rotations.
Reverse the entire array nums to bring the elements that need to be moved to the right to the beginning of the array. This step effectively places the last k elements at the front of the array.
Reverse the first k elements in the array. This operation moves the elements that were originally at the end of the array to their correct positions at the beginning.
Finally, reverse the remaining elements after the first k elements. This step ensures that the elements that were initially at the beginning of the array, after the first k rotations, are moved back to their correct positions.
The combination of these three reverse operations achieves the desired rotation of the array to the right by k steps.
By following this approach, we can effectively rotate the array in-place without requiring additional space
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
void rotate(vector< int>& nums, int k) {
// Calculate the actual number of rotations needed
int n = nums.size();
k = k % n;
// Reverse the entire array
reverse(nums.begin(),nums.begin()+n-k);
// Reverse the first k elements
reverse(nums.begin()+n-k,nums.end());
// Reverse the remaining elements
reverse(nums.begin(),nums.end());
}
};
class Solution {
public static void reverse(int nums[], int start, int end){
// While start index is less than end index
while(start < end){
// Swap elements at start and end indices
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
// Increment start index and decrement end index
start++;
end--;
}
}
public void rotate(int[] nums, int k) {
// Ensure k is within array bounds
k %= nums.length;
// Reverse entire array
reverse(nums, 0, nums.length - 1);
// Reverse first k elements
reverse(nums, 0, k - 1);
// Reverse remaining elements
reverse(nums, k, nums.length - 1);
}
}
class Solution(object):
def rotate(self, nums, k):
if len(nums) == 0:
return []
if k == 0:
return nums
if len(nums)< k:
nums[:] = Solution.rotate(self,nums,len(nums))
nums[:] = Solution.rotate(self,nums,k-len(nums))
nums.reverse()
nums[:k] = reversed(nums[:k])
nums[k:] = reversed(nums[k:])
return nums
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment