Day 38 of DSA Problem Solving

Approach 1

Approach

Complexity

1. Time complexity: O(n)

2. Space complexity: O(1)

Code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */

var rotate = function(nums, k) {
  let len = nums.length;
  k = k % len; 

  reverse(nums, 0, len - 1)
  reverse(nums,  0, k - 1)

  reverse(nums,  k  , len - 1)

  return nums
};
function reverse(nums, start, end) {
  while(start < end){
    let temp = nums[start]
     nums[start] = nums[end]
     nums[end] = temp;
     start++;
     end--;
  }

}

Approach 2

Given an array nums and an integer k, rotate the array to the right by k steps. Do not return anything, modify the array in-place instead.

Approach:

1. Input Handling:

• We are provided with an array nums and an integer k, where k represents the number of positions to rotate the array to the right.

2. Modifying k:

• The rotation of an array by its length results in the same array. Hence, if k is greater than the length of the array, we reduce it to k % len(nums) to avoid unnecessary rotations.

3. Dividing the Array:

• First Part:

  • We split the array into two parts:
  • The first part consists of the first len(nums) - k elements, which will eventually move to the back of the array.
  • Example: For nums = [1, 2, 3, 4, 5, 6, 7] and k = 3, the first part will be [1, 2, 3, 4].

• Second Part:

  • The second part consists of the last k elements, which will be moved to the front after the rotation.
  • Example: For nums = [1, 2, 3, 4, 5, 6, 7] and k = 3, the second part will be [5, 6, 7].

4. Concatenating the Parts:

• After splitting the array, we concatenate the second part with the first part:
  • Example: [5, 6, 7] + [1, 2, 3, 4] = [5, 6, 7, 1, 2, 3, 4].

5. Reassigning to nums:

• Since the problem requires in-place modification, we will overwrite the original array nums by updating its elements in place with the concatenated result.

The algorithm modifies the original array without creating a new one.

6. Result:

• After performing the above steps, the array nums is rotated by k positions to the right, and no new array is returned. The rotation happens in-place.

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */


var rotate = function(nums, k) {
  let len = nums.length;
  k = k % len; 
  let First_Part = nums.slice(0, len - k)
  let Second_Part =  nums.slice(len - k, len + k)
  const rotated = Second_Part.concat(First_Part);

    for (let i = 0; i < nums.length; i++) {
        nums[i] = rotated[i];
    }
    return nums
};