Welcome Reader!
We hope you are enjoying learning from our daily newsletter. In the last blog, we discussed the problem Arrays: Plus One. In this article, we explain the approach to solve the problem of “Rotate Array.”
Problem Link. Give the problem a shot before diving into the solution.
Problem Statement
Given an array, rotate the array to the right by k steps, where k is non-negative.
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231-1
0 <= k <= 105
Examples
Example I
Input: nums = [ 1, 2, 3, 4, 5, 6, 7] , k = 3
Output: [ 5, 6, 7, 1, 2, 3, 4]
Explanation:
Step 1. Rotate 1 step to the right : [ 7, 1, 2, 3, 4, 5, 6]
Step 2. Rotate 1 step to the right : [ 6, 7, 1, 2, 3, 4, 5]
Step 3. Rotate 1 step to the right : [ 5, 6, 7, 1, 2, 3, 4]
Example 2
Input: nums = [ -1, -100, 3, 99] , k = 2
Output: [ 3, 99, -1, -100]
Explanation:
Step 1. Rotate 1 step to the right : [ 99, -1, -100, 3]
Step 2. Rotate 1 step to the right : [ 3, 99, -1, -100]
Approach:
In the first example, the length of an array, say n = 7 and k = 3.
Original array : [ 1, 2, 3, 4, 5, 6, 7]
Reverse all elements of the array : [ 7, 6, 5, 4, 3, 2, 1]
Reverse first k elements : [ 5, 6, 7, 4, 3, 2, 1]
Reverse last n-k elements : [ 5, 6, 7, 1, 2, 3, 4]
Implementation:
Complexities:
Time Complexity: O(N)
Explanation: We parse the array only once.
Space Complexity: O(1)
No extra space is required except for maintaining the start, and end.
Contributed by: Anshul Arya
Regards,
The Daily Code Team.
Thanks for this informative post Ravi Tandon & Anshul Arya ! This really helps !