Left Rotate Array by K Places
EasyReverse three times
Problem
Given an integer array nums and a non-negative integer k, rotate the array to the left by k steps.
Reverse the first k, reverse the rest, then reverse the whole thing — the array spins by k.
The idea
Reverse the first k elements, reverse the rest, then reverse the whole array — the two blocks end up swapped and each back in order. It gives an in-place rotation in O(n) with no extra array and no juggling of cycle indices.
The trick
- Take k modulo n first, or a large k walks off the end.
- Reverse(0,k-1), reverse(k,n-1), reverse(0,n-1) — that exact order.
- For a right rotation, use n-k in place of k.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — nums = [1, 2, 3, 4, 5, 6], k = 2 Values: 1, 2, 3, 4, 5, 6.
1k = k % n2reverse(nums, 0, k-1)3reverse(nums, k, n-1)4reverse(nums, 0, n-1)Input
- array
- [1, 2, 3, 4, 5, 6]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3, 4, 5], k = 2
- Output:
- [3, 4, 5, 1, 2]
- Explanation:
- The first two slide to the back.
Example 2
- Input:
- nums = [1, 2, 3], k = 3
- Output:
- [1, 2, 3]
- Explanation:
- Rotating by the length returns the original.
Example 3
- Input:
- nums = [1, 2, 3, 4], k = 1
- Output:
- [2, 3, 4, 1]
- Explanation:
- Everyone shifts left by one.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 0 <= k <= 10^5
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.