Rotate Array

It is Friday and a week since the problem with our furnace showed up. We have switched service companies. We are now going to replace the furnace. Have not heard from the technician yet. Hope to have the new unit installed earlier next week. The temperature in the Twin Cities of Minneapolis and St. Paul is slowly going down.

Due to the COVID pandemic, I stopped donating blood to the Red Cross. For the past decade or so, I have been giving blood twice a year. I do it once for my wife and the second for me. Not sure if we will ever be in need of blood, but I am aware that it is constantly needed. My next appointment is towards the beginning of November.

Today I selected the next problem from LeetCode which happened to be “Rotate Array. It is ranked at Medium difficulty.

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

Constraints:

o 1 <= nums.length <= 105
o -231 <= nums[i] <= 231 - 1
o 0 <= k <= 105

Follow up:

o Try to come up with as many solutions as you can. 
	There are at least three different ways to solve this problem.
o Could you do it in-place with O(1) extra space?

Hints:

o Array
o Math
o Two Pointers

The requirements are quite simple. We are provided with an array of integers and the numbers of steps we need to rotate the array right.

    public void rotate(int[] nums, int k) {
        
    }

We are going to solve the problem using the Java programming language and the VSCode IDE on a Windows computer. Since Java is very portable you should be able to use any platform and IDE and get the same results.

Since we will be developing the code on my machine, we will need a test scaffold. The test code will read the two input lines, populate the associated variables, display them, invoke the function of interest and display the output.

1,2,3,4,5,6,7
3
main <<< nums: [1, 2, 3, 4, 5, 6, 7]
main <<< k: 3
<<< k: 3
<<< nums: [7, 6, 5, 4, 3, 2, 1]
<<< nums: [5, 6, 7, 4, 3, 2, 1]
<<< nums: [5, 6, 7, 1, 2, 3, 4]
main <<< output: [5, 6, 7, 1, 2, 3, 4]


-1,-100,3,99
2
main <<< nums: [-1, -100, 3, 99]
main <<< k: 2
<<< k: 2
<<< nums: [99, 3, -100, -1]
<<< nums: [3, 99, -100, -1]
<<< nums: [3, 99, -1, -100]
main <<< output: [3, 99, -1, -100]


1,2,3
4
main <<< nums: [1, 2, 3]
main <<< k: 4
<<< k: 1
<<< nums: [3, 2, 1]
<<< nums: [3, 2, 1]
<<< nums: [3, 1, 2]
main <<< output: [3, 1, 2]


1,2
1
main <<< nums: [1, 2]
main <<< k: 1
<<< k: 1
<<< nums: [2, 1]
<<< nums: [2, 1]
<<< nums: [2, 1]
main <<< output: [2, 1]


1
2
main <<< nums: [1]
main <<< k: 2
main <<< output: [1]

The first input line holds the values for the integer array `nums`. The second line holds the value for `k` which represents the number of times the array will be rotated right. Something you need to think about is the relationship between `k` and the number of elements in the `nums` array. We do not want to rotate the array more times than needed.

We will be solving the same problem three times. Since we modify the `nums` array, instead of saving the array and then restoring it for the next implementation, I decided to just comment out the multiple calls. Our test code runs a single implementation at a time. The run that you see in the screen capture is for the fastest implementation.

Please take a few moments to look at the different test cases and make sure you agree with the results. The first two test cases came from LeetCode.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read int[] nums ****
        int[] nums = Arrays.stream(br.readLine().trim().split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** read k ****
        int k = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< nums: " + Arrays.toString(nums));
        System.out.println("main <<< k: " + k);

        // **** call function of interest ****
        rotate0(nums, k);
        // rotate1(nums, k);
        // rotate2(nums, k);

        // **** display result ****
        System.out.println("main <<< output: " + Arrays.toString(nums));
    }

The test code seems to match very close to our previous description. Note that there are three implementations but only the first is currently enabled.

At this time I have nothing else to add to the test scaffold. Please note that if you use the on-line IDE provided by LeetCode you will not have to develop a test scaffold. The test code IS NOT PART OF THE SOLUTION.

    /**
     * Rotate the array to the right by k steps, 
     * where k is non-negative.
     * 
     * Brute force approach.
     * 
     * 37 / 38 test cases passed.
     * Status: Time Limit Exceeded
     * Submitted: 0 minutes ago
     *
     * Runtime: O(k * n) - Space: O(1)
     */
    static public void rotate2(int[] nums, int k) {

        // **** initialization ****
        k %= nums.length;

        // ???? ????
        System.out.println("<<< k: " + k);
        
        // **** loop once per rotation ****
        for (int i = 0; i < k; i++) {

            // **** save last element ****
            int tmp = nums[nums.length - 1];

            // **** rotate array right to left ****
            for (int j = nums.length - 1; j > 0; j--)
                nums[j] = nums[j - 1];

            // **** restore last element ****
            nums[0] = tmp;
        }
    }

This is a slow implementation of the function of interest.

We start by refreshing the value of the argument `k`. This prevents unnecessary rotations. If the step `k` is larger than or equal to the length of the `nums` array, we would be rotating all the elements at least once per number of elements in the array.

In this implementation we loop once per rotation as specified by the `k` parameter.

For each loop, we rotate each element once. This is the brute force approach. It works, but as you can tell by reading the comments section of this function, the run times out and is not accepted by LeetCode.

    /**
     * Rotate the array to the right by k steps, 
     * where k is non-negative.
     * 
     * Using auxiliary array.
     * 
     * 38 / 38 test cases passed.
     * Status: Accepted
     * Runtime: 1 ms
     * Memory Usage: 56.4 MB
     * 
     * Runtime: O(n) - Space: O(n)
     */
    static public void rotate1(int[] nums, int k) {
        
        // **** sanity check(s) ****
        if (nums.length == 1) return;

        // **** initialization ****
        k           %= nums.length;
        int[] arr   = new int[nums.length];

        // ???? ????
        System.out.println("<<< k: " + k);

        // **** copy back sub array - O(k) ****
        for (int i = 0; i < k; i++)
            arr[i] = nums[nums.length - k  + i];

        // ???? ????
        System.out.println("<<< arr: " + Arrays.toString(arr));

        // **** copy front sub array - O(n - k) ****
        for (int i = 0; i < nums.length - k; i++)
            arr[k + i] = nums[i];

        // ???? ????
        System.out.println("<<< arr: " + Arrays.toString(arr));

        // **** copy arr to nums ****
        for (int i = 0; i < arr.length; i++)
            nums[i] = arr[i];
    }

We start this implementation taking care of the argument `k` as we did in the previous pass.

We also initialize a target array which we will use to generate our output.

We start by copying the two sub arrays that make up the final solution. We do not perform rotations.

When we are done, we just copy the contents of the int[] array `arr` into the `nums` array.

Take a look at the comments section. All test cases were passed and the solution was accepted.

    /**
     * Rotate the array to the right by k steps, 
     * where k is non-negative.
     * 
     * 38 / 38 test cases passed.
     * Status: Accepted
     * Runtime: 0 ms
     * Memory Usage: 56.4 MB
     * 
     * Runtime: O(n)  - Space: O(1)
     */
    static public void rotate0(int[] nums, int k) {
       
        // // **** sanity check(s) ****
        // if (k == 0 || nums.length == k) return;
        // if (nums.length == 1) return;

        // **** initialization ****
        k  %= nums.length;

        // ???? ????
        System.out.println("<<< k: " + k);

        // **** reverse entire array - O(n) ****
        reverse0(nums, 0, nums.length - 1);

        // ???? ????
        System.out.println("<<< nums: " + Arrays.toString(nums));   

        // **** reverse front sub array - O(k)****
        reverse0(nums, 0, k - 1);

        // ???? ????
        System.out.println("<<< nums: " + Arrays.toString(nums));   

        // **** reverse back sub array - O(n - k) ****
        reverse0(nums, k, nums.length - 1);

        // ???? ????
        System.out.println("<<< nums: " + Arrays.toString(nums));   
    }

In this implementation we need to note three steps that would take us from the initial `nums` array to the solution.

We need to reverse the entire contents of the array. We then reverse the fron sub array and then the back one. Note that this approach is quite similar to the previous implementation.

To get this function to work, we need to implement the auxiliary function `reverse0`.

This function was also accepted by LeetCode and the actual execution time is in the comments section of the associated code.

    /**
     * Reverse elements in specified array and range.
     */
    static private void reverse0(int[] arr, int s, int e) {
        while (s < e) {
            int tmp = arr[s];
            arr[s++] = arr[e];
            arr[e--] = tmp;

            // // **** update start and end indices ****
            // s++;
            // e--;
        }
    }

This is the auxiliary function that reverses the contents of a section of an array.

We enter a loop with the range, swap the values between the current indices, and move the `s` index right and the `e` index left.

That is all folks. I believe there are many more approaches to solve this problem. We just came up with three in this post.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.