Lets Code Everyday - Day 21

Hello there 👋, enthusiasts.

I wanted to share with others what I had learned from my mistake, which is that it is more necessary to understand the question and the restrictions offered rather than attempting to immediately answer the problem by simply comprehending the examples given.

Question - 21:

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

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]

Example 2:

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<sup>5</sup>

• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

• 0 <= k <= 10<sup>5</sup>

First approach:

class Solution {
    public void rotate(int[] nums, int k) {
        int len=nums.length;
        int[] res= new int[len];
        int j=0;
        k=k%len;
        for(int i=k;i>=1;i--){
            res[j]=nums[len-i];
            j++;
        } 
        for(int i=k;i<len;i++){
            res[i]=nums[i-k];
        }

        for(int i=0;i<res.length;i++) {
           nums[i]=res[i];
            } 
    }
}

Step-by-step implementation:

1. The method takes two parameters: an integer array nums and an integer k that represents the number of positions by which the array should be rotated.

2. The length of the array nums is stored in a variable len.

3. A new integer array res is created with the same length as the original array nums.

4. An integer j is initialized to 0.

5. The value of k is reduced to its equivalent value within the range of the length of nums (i.e., k is set to k%len).

6. A loop is initiated from i=k to i>=1, where each iteration takes the last i-th element from the original array nums and stores it in the j-th index of the new array res. The j index is then incremented by 1.

7. A second loop is initiated from i=k to i<len, where each iteration takes the (i-k)-th element from the original array nums and stores it in the i-th index of the new array res.

8. A third loop is initiated to copy the contents of the new array res back into the original array nums.

9. Within the third loop, each element of res is assigned to the corresponding index of nums.

10. The rotate method finishes execution, and the rotated nums array is returned as the result.

• Time complexity: The rotate method consists of three loops that iterate over the nums and res arrays. The first loop runs k times, the second loop runs len-k times, and the third loop runs len times. Therefore, the time complexity of the rotate method is O(k + len), which simplifies to O(n) where n is the length of the input array nums.

• Space complexity: The rotate method creates a new integer array res that has the same length as the input array nums. Therefore, the space complexity of the rotate method is O(n), where n is the length of the input array nums.

Second approach:

class Solution {
    public void rotate(int[] nums, int k) {
    int len = nums.length;
    k = k % len;

    // Reverse the entire array
    reverse(nums, 0, len - 1);

    // Reverse the first k elements
    reverse(nums, 0, k - 1);

    // Reverse the remaining elements
    reverse(nums, k, len - 1);
}
private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}
}

Step-by-step implementation:

1. The method takes two parameters: an integer array nums and an integer k that represents the number of positions by which the array should be rotated.

2. The length of the array nums is stored in a variable len.

3. The value of k is reduced to its equivalent value within the range of the length of nums (i.e., k is set to k%len).

4. The reverse method is called three times with different input parameters to perform the rotation. The first call reverses the entire array nums from index 0 to index len-1. The second call reverses the first k elements of the array nums from index 0 to index k-1. The third call reverses the remaining elements of the array nums from index k to index len-1.

5. The rotate method finishes execution, and the rotated nums array is returned as the result.

6. The reverse method takes three parameters: an integer array nums, and two integer indices start and end that represent the range of the array to be reversed.

7. Within the reverse method, a while loop is used to swap the elements of the array nums between the start and end indices. The start index is initially set to the first element of the range (start = 0), and the end index is initially set to the last element of the range (end = nums.length - 1).

8. Within each iteration of the while loop, the elements at start and end indices are swapped using a temporary variable temp. The start index is then incremented by 1, and the end index is decremented by 1.

9. The while the loop continues until the start index is greater than or equal to the end index. At this point, the range between start and end indices have been reversed.

• Time complexity: The rotate method calls the reverse method three times, and each call to the reverse method takes O(n/3) time complexity (where n is the length of the input array nums) because it reverses a subarray of size n/3. Therefore, the total time complexity of the rotate method is O(n/3 * 3), which simplifies to O(n).

• Space complexity: The rotate method uses a constant amount of extra space for temporary variable temp. Therefore, the space complexity of the rotate method is O(1).

Conclusion:

Both the first and the second approaches have the same time complexity i.e., O(n). Whereas the second approach is using less space i.e., O(1) comparatively with the first approach i.e., O(n).

The Second approach that uses the reverse method is a better implementation in terms of space complexity, readability, and simplicity.

Thanks for reading...Happy Learning 😁