Rotate array of k position performance c#

Question

I'm solving problems on LeetCode, and referring to this problem: 189. Rotate Array

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]

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 its 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 gives me

"Time Limit Exceeded"

Related: [How to efficiently rotate an array?](https://stackoverflow.com/questions/38482696/how-to-efficiently-rotate-an-array) — Theodor Zoulias, Dec 08 '22 at 02:03
@DmitryBychenko please don't recreate tags that have [previously been removed](https://meta.stackoverflow.com/q/399117/6296561). The [leetcode] tag is not a good tag for Stack Overflow — Zoe, Dec 13 '22 at 17:05

Stephen Gilboy · Answer 1 · 2022-12-07T18:51:34.870

2

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;
    }

edited Dec 07 '22 at 18:51

answered Dec 07 '22 at 18:12

Stephen Gilboy

5,572
2
30
36

Side note: often `k < 0` means that we should rotate to the *opposite* side. – Dmitry Bychenko Dec 07 '22 at 18:19
`Given an array, rotate the array to the right by k steps, where k is non-negative.` Is why I didn't account for negatives. And yeah, I should have checked for `IndexOutOfBounds` but I was just throwing a quick solution together. – Stephen Gilboy Dec 07 '22 at 18:23
Updated my answer to deal with `k > nums.length`. I'm sure there's a more elegant solution but I'm no maths whiz. – Stephen Gilboy Dec 07 '22 at 18:53
It's correct now, all leet code tests are passed. – Dmitry Bychenko Dec 07 '22 at 18:59
Awesome! Thanks for checking and helping me out. – Stephen Gilboy Dec 07 '22 at 19:00

score 2 · Answer 2 · answered Dec 08 '22 at 04:00

2

There's a trick to performing this in place that involves a transformation over two steps. O(n) time, O(1) space.

Example, k = 3:

First reverse in place each of the two sections delineated by n-k:

4321 765

Now revese the whole array:

Reversing sections in place left as an exercise to the reader.

answered Dec 08 '22 at 04:00

גלעד ברקן

23,602
3
25
61

1

Very clever! I posted an implementation [here](https://stackoverflow.com/a/74725759/11178549). – Theodor Zoulias Dec 08 '22 at 05:12

Dmitry Bychenko · Accepted Answer · 2022-12-07T19:17:29.383

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

Compute what each item of the result array should be
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

Can you explain how are you using % to get the index please? — Matteo, Dec 07 '22 at 19:08
Thank you, I tried to modify your solution to don't use extra space but I couldn't find a way to make it easy. And I like the use of the % to skip a lot of operations. And i guess that to make mine faster the only way was to remove a loop — Matteo, Dec 07 '22 at 20:17

Rotate array of k position performance c#

3 Answers3

Linked