Problem: Rotate an Array

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

Example:

Input:

nums = [1,2,3,4,5,6,7], k = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

• Rotate 1 step 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]

Approach:

1. Reverse the Entire Array: First, reverse the entire array. This step moves the elements into the reverse order.

2. Reverse the First k Elements: After reversing the entire array, the first k elements should be reversed to restore the correct order.

3. Reverse the Remaining Elements: Finally, reverse the remaining numsSize - k elements to bring them into the correct order.

4. Modulo Operation: If k is greater than or equal to numsSize, we use k = k % numsSize to handle rotations that go beyond the array size.

C Code Solution:

#include <stdio.h>

void reverse(int* nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;  // In case k is larger than numsSize
    reverse(nums, 0, numsSize - 1);  // Reverse the entire array
    reverse(nums, 0, k - 1);  // Reverse the first k elements
    reverse(nums, k, numsSize - 1);  // Reverse the rest of the array
}

int main() {
    int nums[] = {1, 2, 3, 4, 5, 6, 7};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int k = 3;

    rotate(nums, numsSize, k);

    printf("Rotated array: ");
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("n");

    return 0;
}

Explanation of Code:

1. Reverse Function:

   • The reverse function takes the array and two indices (start and end). It swaps the elements at the start and end indices and keeps moving towards the center, effectively reversing the portion of the array.

2. Rotate Function:

   • First, k = k % numsSize ensures that k is within the array bounds (i.e., no need to rotate more than the size of the array).
   • The array is then reversed in three steps:
     • Reverse the entire array.
     • Reverse the first k elements.
     • Reverse the remaining elements from index k to numsSize - 1.

3. Main Function:

   • Initializes the array and calls the rotate function. It then prints the rotated array.

Time and Space Complexity:

• Time Complexity: O(n)O(n), where nn is the number of elements in the array. We reverse the entire array and its sections, which requires linear time.
• Space Complexity: O(1)O(1), as we modify the array in place without using any additional space.

Example Walkthrough:

Example 1:

Input:

nums = [1, 2, 3, 4, 5, 6, 7], k = 3

1. Reverse the Entire Array:

   [1, 2, 3, 4, 5, 6, 7] -> [7, 6, 5, 4, 3, 2, 1]
   

2. Reverse the First k = 3 Elements:

   [7, 6, 5, 4, 3, 2, 1] -> [5, 6, 7, 4, 3, 2, 1]
   

3. Reverse the Remaining Elements:

   [5, 6, 7, 4, 3, 2, 1] -> [5, 6, 7, 1, 2, 3, 4]
   

Output:

[5, 6, 7, 1, 2, 3, 4]

Example 2:

Input:

nums = [-1, -100, 3, 99], k = 2

1. Reverse the Entire Array:

   [-1, -100, 3, 99] -> [99, 3, -100, -1]
   

2. Reverse the First k = 2 Elements:

   [99, 3, -100, -1] -> [3, 99, -100, -1]
   

3. Reverse the Remaining Elements:

   [3, 99, -100, -1] -> [3, 99, -1, -100]
   

Output:

[3, 99, -1, -100]