Analysis of recursive approach for rotating an array of integers

While solving Array rotation on LeetCode, I wrote a recursive algorithm to solve the problem:

Given an array, 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 <= 2*104
-231 <= nums[i] <= 231 – 1
0 <= k <= 105

For further clarification the link to the problem is here.

The solution I came up with is as follows:

class Solution {
  public void rotate(int[] nums, int k) {
    rotateArr(nums, nums.length, k % nums.length, 0);
  }

  public static void rotateArr(int[] arr, int len, int steps, int current) {
    if (len <= steps) {
      return;
    }
    rotateArr(arr, len - 1, steps, current + 1);
    int stepsTaken = 0;
    int i = current;
    int temp;
    while (stepsTaken < steps) {
      temp = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = temp;
      i++;
      stepsTaken++;
    }
  }
}

According to my analysis of the solution the function rotateArr() will first divide, by recuring nums.length – k times. After that it start conquering, which will happen in nums.length – k + 1 steps and at each step its performing k operations. Summing up everything we get:

• (nums.length – k) + (nums.length – k + 1) k = nums.length + nums.length k – k^2

Although I have a quadratic term but its a constant, thus I believe my runtime is O(n).
I want to know the following:

• Is my analysis correct ?
• If it’s correct, then why my runtime always falls arround 100 ms on LeetCode ? As opposed to others with 0 ms. Is it because of recursion ?

Answer

Utkarsh Tiwari, I think your analysis is not correct. According to my calculation the conquer step will happen for A.length - k times and not A.length - k + 1.

Let us consider the second input array you mentioned:

[-1, -100, 3, 99]

Here the first call to rotateArray(A, 4, 2, 0) takes place in the main() method. The second recursive call is this: rotateArray(A, 3, 2, 1) and the last one is this: rotateArray(A, 2, 2, 2).

However, in the last recursive call the conquer will not take place since the base condition is satisfied.

if(length <= steps) return.

The function will simply return the last time without performing any significant steps. Hence, all the k number of operations will occur only in the first two recursive calls which is according to the expression A.length - k or 4-2 in this case.

Hence, the time complexity will be (A.length-k) * k.

Now, lets look at the constraints you provided:

1 <= nums.length <= 2 * 10^4

-2^31 <= nums[i] <= 2^31 - 1

0 <= k <= 10^5

Here, k is not constant. Its possible value even exceeds the maximum value of nums.length. The time complexity depends both on the value of A.length and k. It would have been O(nums.length) if the possible value of k were between 5 to 20. However, with current constraints it can take a value which is more than A.length.

Lets notice another subtle detail in your implementation. In the first call to rotateArray(), you pass k % A.length as one of the parameters. Now the possible value of k reduces to:

0 <= k < A.length

If we choose value of k as A.length/2 and put in our time complexity, we get:

(A.length - A.length/2) * A.length

which reduces to O(A.length^2) which will be the worst case complexity.

I hope I have helped you. Do comment if you face any problems in the solution.