I'm solving problems on LeetCode, and refering to this problem https://leetcode.com/problems/rotate-array/description/?envType=study-plan&id=algorithm-i

I gave my solution as:

public void Rotate(int[] nums, int k) {
    if (k <= 0)
        return;

    int t = 0;

    for (int i = 0; i < k; i  ) {
        t = nums[nums.Length - 1];

        for (int j = nums.Length - 1; j > 0; j--) {
            nums[j] = nums[j - 1];
        }

        nums[0] = t;
    }
}

My question is not about the solution, but is about his performance.

Can I improve my solution to be faster? Or is wrong my approach?

Cause it pass all the test cases, but it fail the last one cause is a big array with big numbers, and it fail on being fast enough, it give me "Time Limit Exceeded"

CodePudding user response：

You could run it in a single while loop. I don't have leetcode so I can't test it, I just ran it locally but if you run this what do you get? Also, it doesn't do the in place movement so if there is a memory test it might fail that.

  public static int[] Rotate(int[] nums, int k) {
        if (k <= 0) return nums;
        var n = new int[nums.Length];
        var stopAt = nums.Length - k;
        while(stopAt < 0) {
            stopAt = nums.Length - Math.Abs(stopAt);
        }
        var i = stopAt;
        var y = 0;
        while (true) {
            n[y] = nums[i];
            y  ;
            i  ;
            if (i >= nums.Length) {
                i = 0;
            }
            if (i == stopAt) break;
        }
        return n;
    }

CodePudding user response：

If you are looking for performance you can get rid of nested loops to have O(n) time complexity vs. O(n * n):

1. Compute what each item of the result array should be
2. Copy result array into initial one

Code:

public void Rotate(int[] nums, int k) {
    int[] result = new int[nums.Length];
    
    for (int i = 0; i < nums.Length;   i) {
        int index = (i   k % nums.Length   nums.Length) % nums.Length;
        
        result[index] = nums[i];
    }
    
    Array.Copy(result, nums, nums.Length);
}

Note, that in general case we have a quite complex formula for index:

  int index = (i   k % nums.Length   nums.Length) % nums.Length;

we should be ready for negative k (while index must not be negative) and huge k (possible integer overflow). If k >= 0 and k <= 1e5 as Leet Code claims we can simplify index into

  int index = (i   k) % nums.Length;

and have compact solution as

public void Rotate(int[] nums, int k) {
    int[] result = new int[nums.Length];
    
    for (int i = 0; i < nums.Length;   i) 
        result[(i   k) % nums.Length] = nums[i];
    
    Array.Copy(result, nums, nums.Length);
}

Edit: Why % (remainder) appears in index formula?

Let's have a look on what's going on. When i k is less than nums.Length we should write the value just at i k index. When i k == nums.Length we should write at index == 0, when i k == nums.Length 1 we should write at index == 1, ..., when i k == nums.Length r then we should write at index == r, note that r == (i k) % nums.Length == (nums.Length r) % nums.Length == 0 r == r