CODEWITHSUNDEEP
c#algorithmperformancefor-loop
Matteo
Matteo

Reputation: 81

Rotate array of k position performance c#

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"

Upvotes: 4

Views: 476

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

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:

1234567

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

4321 765

Now revese the whole array:

5671234

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

Upvotes: 2

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

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

Upvotes: 1

Stephen Gilboy
Stephen Gilboy

Reputation: 5825

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

Upvotes: 2

Related Questions