Rotate array [LC150]

Hello friends,

Today we’re going to discuss and solve another Leetcode DSA problem about rotating array. link- https://leetcode.com/problems/rotate-array/description/

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]

Solution-1 (Elementory):

private static void rotateRight(int[] nums, int k) //Brute force 0(n^2)
        {
            for (int i = 0; i < k; i++)
            {
                int temp = nums[nums.Length - 1];
                for (int j = nums.Length - 1; j > 0; j--)
                {
                    nums[j] = nums[j - 1];
                }
                nums[0] = temp;
            }

            Console.WriteLine(string.Join(" ", nums));
        }

Explanation:

The provided method rotateRight performs a right rotation of an array nums by k steps using a brute-force approach.

Time Complexity:

• The outer loop runs k times.
• Inside each iteration, it shifts all elements of the array by one position, which takes O(n) time, where n is the length of the array.
• Therefore, the total time complexity is O(k * n).

Space Complexity:

• The method uses a constant amount of extra space (a temporary variable temp), regardless of the size of the input array.
• Hence, the space complexity is O(1).

Solution-2 (Cleaner, Better)

private static void rotateRight2(int[] nums, int k) //Optimised solution 0(n)
        {
            int[] result = new int[nums.Length];
            int count = 0;

            for (int i = nums.Length - k; i < nums.Length; i++)
            {
                result[count++] = nums[i];
            }

            for (int i = 0; i < nums.Length - k; i++)
            {
                result[count++] = nums[i];
            }

            result.CopyTo(nums, 0);

            Console.WriteLine(string.Join(" ", nums));
        }

Explanation:

Time Complexity:

The method rotateRight2 has a time complexity of O(n), where n is the length of the input array nums. This is because it iterates through the array elements twice: once to copy the last k elements into the result array and once to copy the remaining elements. Each element is processed a constant number of times, leading to linear time complexity.

Space Complexity:

The space complexity is also O(n) due to the creation of an auxiliary array result of the same size as the input array. This additional space is used to store the rotated elements before copying them back into the original array.

Hope you liked the article. Please share your comment/ suggestion.