14
\$\begingroup\$

This code is to solve the Hacker Rank problem array left rotation.

A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. For example, if 2 left rotations are performed on array [1,2,3,4,5], then the array would become [3,4,5,1,2].

Given an array of n integers and a number, d, perform d left rotations on the array. Then print the updated array as a single line of space-separated integers.

public static int[] rotLeft(int[] a, int d)
    {
        for (int intI = 0; intI < d; intI++)
        {
            int temp = 0;
            temp = a[0];
            for (int intK = 0; intK < a.Length; intK++)
            {
                a[a.Length - (a.Length - intK)] = a.Length - 1 == intK ? temp : a[a.Length - (a.Length - (intK + 1))];
            }
        }
        return a;
    }
    static void Main(string[] args)
    {
        string[] nd = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(nd[0]);
        int d = Convert.ToInt32(nd[1]);
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp));
        int[] result = rotLeft(a, d);
        Console.WriteLine(string.Join(" ", result));
    }

This program works fine, but it takes too long with some examples. How can I improve it?

\$\endgroup\$
  • 6
    \$\begingroup\$ The best code is no code at all. Do you actually need to rotate the array, or just print the elements in rotated order? Because if that’s the case then you can save a whole lot of copying around. \$\endgroup\$ – Konrad Rudolph Mar 4 at 12:45
  • 7
    \$\begingroup\$ @Caramiriel, you've got the wrong box. The one for answers is further down the page. \$\endgroup\$ – Peter Taylor Mar 4 at 14:32
  • 1
    \$\begingroup\$ @Caramiriel this isn't O(n) because Skip is not clever... as far as I know it iterates the collection to skip the items. \$\endgroup\$ – t3chb0t Mar 4 at 16:00
  • 4
    \$\begingroup\$ @t3chb0t Even if it goes through the array twice, 2n, or 200n for that matter, is still O(n) \$\endgroup\$ – TemporalWolf Mar 4 at 18:09
  • 1
    \$\begingroup\$ @t3chb0t See the canonical answer on What is BigO? When n is 10, 2n is 20 and n^2 is 100... and it only gets worse the larger n gets. That's why. If n is 2 million, then 200n is 400 million and n^2 is 4 trillion... still ten thousand times larger: what the 200n version can do in 1 minute, it will take almost a week (6.94 days) to run at n^2... and that's before you run into memory issues. That's why BigO works the way it does. \$\endgroup\$ – TemporalWolf Mar 5 at 19:13
17
\$\begingroup\$

About naming:

intI and intK: don't include the type in the variable name, it is obvious from the context and intellisense and as a loop index a plain i and k are more understandable.


A first simple optimization is that you can avoid the check if intK has reached the end:

a.Length - 1 == intK ?

Instead you can just iterate up to a.Length - 1 and then append temp at the end:

public static int[] rotLeft(int[] a, int d)
{
  for (int intI = 0; intI < d; intI++)
  {
    int temp = a[0];

    for (int intK = 0; intK < a.Length - 1; intK++)
    {
      a[a.Length - (a.Length - intK)] = a[a.Length - (a.Length - (intK + 1))];
    }

    a[a.Length - 1] = temp;
  }

  return a;
}

Next step is to consider the math:

a.Length - (a.Length - intK) = a.Length - a.Length + intK = intK

and in the same way:

a.Length - (a.Length - (intK + 1)) = intK + 1

So you could write:

public static int[] rotLeft(int[] a, int d)
{
  for (int intI = 0; intI < d; intI++)
  {
    int temp = a[0];

    for (int intK = 0; intK < a.Length - 1; intK++)
    {
      a[intK] = a[intK + 1];
    }

    a[a.Length - 1] = temp;
  }

  return a;
}

But the real performance problem is that you move each entry in the array d number of times. You can move each entry just once by moving it d places. A simple way to do that could be:

public static int[] rotLeft(int[] a, int d)
{
  int[] temp = new int[d];

  for (int i = 0; i < d; i++)
    temp[i] = a[i];

  for (int i = d; i < a.Length; i++)
  {
    a[i - d] = a[i];
  }

  for (int i = 0; i < d; i++)
    a[a.Length - d + i] = temp[i];

  return a;
}

Another issue is that you operate on the input array a directly and return it as a return value. In this way both the return value and a contains the shifted values. In a challenge like this it may not be important, but I think I would return a new array with the shifted data leaving a unchanged - in "real world":

public static int[] rotLeft(int[] a, int d)
{
  int[] result = new int[a.Length];

  for (int i = d; i < a.Length; i++)
  {
    result[i - d] = a[i];
  }

  for (int j = 0; j < d; j++)
  {
    result[a.Length - d + j] = a[j];
  }

  return result;
}

If you want to operate on a directly intentionally it would be more consistent returning void to signal that you're operating on the input directly.

\$\endgroup\$
16
\$\begingroup\$

I guess your code is slow because of the two loops and its O(n^2) complexity. You can actually solve it with only one loop by rotating the index with % (modulo). This would even allow you to rotate the array in both directions;

public static IEnumerable<T> Shift<T>(this T[] source, int count)
{
    for (int i = 0; i < source.Length; i++)
    {
        var j =
            count > 0
            ? (i + count) % source.Length
            : (i + count + source.Length) % source.Length;
        yield return source[j];
    }
}
\$\endgroup\$
  • 11
    \$\begingroup\$ In fact, a general tip for programming challenges like this is that, whenever the challenge says "repeat this operation N times," it almost always actually means "find a faster way to get the same result as if you'd repeated the operation N times." That's because the challenges are meant to be challenging, and just writing a for loop to run the same code multiple times is really no challenge at all. \$\endgroup\$ – Ilmari Karonen Mar 4 at 10:00
  • \$\begingroup\$ % is typically slow; and i+count can't wrap more than once. So really you just need a conditional subtract. If you're actually copying the array, hopefully the compiler can split it into two loops that simply copy the 1st / 2nd parts of the array without doing a bunch of expensive per-index calculation, like Henrik's answer. Also hopefully the compiler will hoist the count>0 check out of the loop. \$\endgroup\$ – Peter Cordes Mar 4 at 10:02
  • 8
    \$\begingroup\$ @PeterCordes - I think % is clearer and never so slow as to justify such an optimization without profiling first. I would be very surprised if it were the bottleneck in application software, rather than, say, disk IO. \$\endgroup\$ – Alex Reinking Mar 4 at 10:41
  • \$\begingroup\$ In C, a simplistic microbenchmark doing just a modulo increment shows that it's about 6x slower on a Haswell CPU. is it better to avoid using the mod operator when possible?. Most things aren't a big deal, but integer division is slow unless it's by a compile-time constant that the compiler can turn into a multiply+shift. The OP already said that their solution for rotating an array was too slow rotating 1 element at a time, so presumably a factor of 6 (or more if the compiler can turn it into 2x memcpy) could matter. \$\endgroup\$ – Peter Cordes Mar 4 at 22:05
  • 3
    \$\begingroup\$ You can hoist the count > 0 check out of the loop by calculating the left-rotate count once. if(count < 0) count += source.Length; Then the loop becomes much more readable, and probably more efficient unless the compiler already managed to do that for you. \$\endgroup\$ – Peter Cordes Mar 4 at 22:14
8
\$\begingroup\$
    static void Main(string[] args)
    {
        string[] nd = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(nd[0]);
        int d = Convert.ToInt32(nd[1]);
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp));

Don't Repeat Yourself. There's an easy opportunity here to factor out a method which reads an array of integers from stdin.

In general I would prefer to remove the explicit lambda, but I think that in this case just passing Convert.ToInt32 would be ambiguous because of the overloads.


        int[] result = rotLeft(a, d);
        Console.WriteLine(string.Join(" ", result));
    }

When implementing a spec, ask yourself what the inputs and the outputs are. As long as you respect those, you should be at liberty to optimise the processing. So it's not actually necessary to rotate the array: just to print the result of rotating it.

        Console.Write(a[d]);
        for (int i = d+1; i < a.Length; i++)
        {
            Console.Write(' ');
            Console.Write(a[i]);
        }
        for (int i = 0; i < d; i++)
        {
            Console.Write(' ');
            Console.Write(a[i]);
        }

But I think that that code probably has a bug. Does the spec make any guarantees about the value of d other than that it's an integer? Can it be negative? Can it be greater than n?

\$\endgroup\$
  • \$\begingroup\$ Most of the I/O code is provided as part of the challenge. The only thing OP has to provide is the code inside the rotLeft function, which should return the rotated array. \$\endgroup\$ – jcaron Mar 4 at 11:50
  • \$\begingroup\$ @jcaron, it's OP's responsibility to ask only about their own code. The help centre is quite explicit that any aspect of the code posted is fair game for feedback and criticism. \$\endgroup\$ – Peter Taylor Mar 4 at 13:01
  • \$\begingroup\$ The constraints say that 1 <= d <= n, so yes, we have guarantees about d. \$\endgroup\$ – Astrinus Mar 5 at 8:12
  • 1
    \$\begingroup\$ @Astrinus, if I wanted answers to those questions I'd have posted them as comments on the question. As I see it, one of the things a code review should do is challenge OP to think about whether they've fully understood the spec, and whether they can update the code if the spec (or their understanding of it) changes. \$\endgroup\$ – Peter Taylor Mar 5 at 8:30
3
\$\begingroup\$

You are focusing on the wrong portion of the problem. You're thinking the array needs to be rotated. The output of the array needs to be "rotated" but the array can remain as-is.

So simply write a loop that starts at the middle of the array, incrementing until it hits the end, and then continues along from the beginning until it hits the index just before the one you started at.

The output of that loop is the "rotated" array, from the visibility of the testing framework.

    string sep = "";
    for (int i = d % a.Length; i < a.Length; i++) {
        Console.Write(sep);
        Console.Write(a[i]);
        sep = " ";
    }
    for (int i = 0; i < d % a.Length; i++)
    {
        Console.Write(sep);
        Console.Write(a[i]);
        sep = " ";
    }

This is a great reason why you should sometimes see hackerrank as a poor place to really learn programming.

hackerrank primarily contains programming problems harvested from programming competitions. Competitions where these problems are meant to be solved fast, with a time deadline. This means that the problems are more about building a quick, clever, solution and less about really learning the lessons that would help you in a programming career.

Another example of a solution is

    string sep = "";
    for (int i = d; a.Length + d - i > 0; i++) {
        Console.Write(sep);
        Console.Write(a[i % a.Length]);
        sep = " ";
    }

Which is, according to hackerranks estimation, "just as good" as the above solution, but is far less readable.

\$\endgroup\$
  • 1
    \$\begingroup\$ Well one thing one should certainly learn from this challenge is what string.Join does and how it avoids the rather awful for loop :) (The given solution also misses some necessary modulo ops) \$\endgroup\$ – Voo Mar 4 at 19:21
  • \$\begingroup\$ @Voo Out of curiosity, which modulo does this miss? I know I wrote it by hand without the aid of a computer, but the loop (in my 5 element example, starting at index 3 would be 3, 4, 5, 6, 7 (8 would be 5 + 3 - 8, so it wouldn't get there). and 3 % 5 = 3, 4 % 5 = 4, 5 % 5 = 0, 6 % 5 = 1, 7 % 5 = 2. Now, I just might have a bug in there after all; but, maybe not, which is a perfect example of why writing it this way is less than ideal and why hackerranks fascination with programming competitions as question banks is bad. \$\endgroup\$ – Edwin Buck Mar 4 at 20:20
  • 2
    \$\begingroup\$ You're supposed to do n rotations. Nowhere does it say that n < arr.Length. You could have an array of 1,2,3 and d=5. Both of your solutions fail with an out of bounds there. \$\endgroup\$ – Voo Mar 4 at 21:14
  • 1
    \$\begingroup\$ @Voo: if you read the challenge, you see that 1 <= d <= n, i.e. rotate an n elements array by d steps, so you cannot have more rotations than elements. \$\endgroup\$ – Astrinus Mar 5 at 8:15
  • \$\begingroup\$ @Voo I think you keep focusing on how (in my latter example) i is often out-of-range of the array. That's probably why you keep saying "out of bounds" which would cause an error if I was pulling out the i element of the array. But I'm not pulling i out of the array, I'm pulling i % a.Length which can't be out of bounds. \$\endgroup\$ – Edwin Buck Mar 5 at 17:10
1
\$\begingroup\$
  • Because of the 2 imbricated for loops in the original code,

    for (int intI = 0; intI < d; intI++) {
    for (int intK = 0; intK < a.Length; intK++) { ... } }

your code performs d * a.Length actions. Which takes quadratic time when d is near a.Length/2.

So, we may ask, can we do better ?

  • The answer is yes. There is a linear-time solution. It is as follows :

    1. "mirror" the first d elements
    2. mirror the whole array
    3. mirror the size-d first elements.

Implementation of mirror (rever an array) is left to the reader.

Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).

So it is clearly an improvement on the original version.

\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Mar 5 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.