Given an integer array nums, rotate it by one position to the left.
Example 1
Input: nums = [1, 2, 3, 4, 5]
Output: [2, 3, 4, 5, 1]
Explanation: Element 1 moves from the first position to the final position. Elements 2, 3, 4, and 5 shift one position toward the beginning.
Example 2
Input: nums = [-1, 0, 3, 6]
Output: [0, 3, 6, -1]
Explanation: Element -1 moves to the final position, while all remaining elements shift one position toward the beginning.
Brute Force Approach
Create an auxiliary array to store the rotated arrangement without overwriting any unprocessed values.
Every element except the first moves one position to the left. The original first element moves to the final position.
Algorithm
If the array contains at most one element, no rotation is needed because its arrangement cannot change.
Create an auxiliary array
tempof the same size asnums, which allows the rotated values to be placed without overwriting elements that are still needed.Starting from index
1, place eachnums[index]attemp[index - 1]. This shifts every element except the first one position to the left.Place the original first element at the last index of
temp, completing the one-position rotation.Copy the values from
tempback intonumsso the original array stores the rotated arrangement.
Dry Run
Rotate Array by One Place Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: void leftRotateByOne(vector<int>& nums) { int n = nums.size(); // Arrays with at most one element remain unchanged. if (n <= 1) { return; } vector<int> temp(n); // Shift every element except the first one position to the left. for (int index = 1; index < n; index++) { temp[index - 1] = nums[index]; } // The original first element moves to the last position. temp[n - 1] = nums[0]; // Copy the rotated arrangement back into the original array. for (int index = 0; index < n; index++) { nums[index] = temp[index]; } }};int main() { vector<int> nums = {1, 2, 3, 4, 5}; Solution solution; solution.leftRotateByOne(nums); for (int num : nums) { cout << num << " "; } return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the number of elements. One traversal creates the rotated arrangement, and another copies it into nums.
Space Complexity: O(N), because an auxiliary array of size N is used.
Optimal Approach
Only the original first element needs to be preserved before shifting begins.
Store it temporarily, shift every remaining element one position to the left, and place the stored value at the final index.
Algorithm
If the array contains at most one element, return directly because rotating it does not change the array.
Store
nums[0]infirstbefore shifting begins, since the value at index0will be overwritten during the first shift.Traverse from index
1to the last index and assignnums[index]tonums[index - 1]. This moves every remaining element one position to the left.Place
firstat the last index, restoring the saved value in its correct rotated position.
Dry Run
Rotate Array by One Place Optimal Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: void leftRotateByOne(vector<int>& nums) { int n = nums.size(); // Arrays with at most one element remain unchanged. if (n <= 1) { return; } // Save the first value before shifting overwrites it. int first = nums[0]; // Move every remaining element one position to the left. for (int index = 1; index < n; index++) { nums[index - 1] = nums[index]; } // Place the saved first value at the end. nums[n - 1] = first; }};int main() { vector<int> nums = {1, 2, 3, 4, 5}; Solution solution; solution.leftRotateByOne(nums); for (int num : nums) { cout << num << " "; } return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the number of elements. Every element except the first is shifted once.
Space Complexity: O(1), because only one temporary variable is used.
Interview follow-up Questions
The value at index 0 is overwritten during the first shift. Storing it temporarily preserves it for placement at the final index.
Be the first to add a comment.