Rotate Function | LeetCode 396 - Python

Added: 2026-05-06

[00:00:00]Hello everyone. I'm Paul and this is problem 396 rotate function. This is a medium math problem so next we'll go step-by-step.

[00:00:10]We are given an integer array nums. So let's say that we are given this and we need to return the maximum value of a rotation function that we are given here. So first we call the function with zero rotations, then with one and so on up to n minus one.

[00:00:27]So if we're given this here n is equal to four because we have four elements and we need to call this function four times. And here it says that we need to rotate elements in clockwise direction.

[00:00:40]So if we do one rotation, we can move this six to the start. So we get something like this. So if we do zero rotations, we get the same order 4 3 2 6. If we do one rotation, we get 6 4 3 2. If we do two rotations, we get 2 6 4 3 and if we do three rotations, we get 3 2 6 4. Now the result of each call is given by each index times its corresponding value. So we go through indices 0 1 and so on up to the last index. This means that for example here, the result of this call is given by 4 * 0 which is 0 + 3 * 1 which is 3 + 2 * 2 which is 4 + 6 * 3 which is 18.

[00:01:37]The result here is uh 25.

[00:01:42]The result of this call is given by 6 * 0 + 4 * 1 + 3 * 2 + 3 * 2. The result is uh 12 16.

[00:01:54]Here the result is 2 * 0 + 6 * 1 + 8 + 9. This is equal to 23.

[00:02:04]And the result of this call is 26.

[00:02:09]Now we need to get the maximum value of every call. So the maximum value here is 26. This is the result. This is the most important part here. So let's say that we replace K with zero. What if we use zero rotations? Well we could say that F0 is equal to this index meaning zero times the corresponding value nums at zero + index one times the corresponding value which is nums at one + the same for every other index up to the last index which is n minus one times the corresponding value at n minus one.

[00:02:52]Okay? So this is basically the same but we are using zero rotations. Now what happens if we use one rotation? Now we are saying that we move this number to the front. So we have something like this. Previously we were multiplying nums at zero by index zero because this was index zero. But now here we have a six. So this is index one. This is index zero and this is index two. This is index three. So we can say that F1 is equal to index one now times this value nums at zero because this now corresponds to index one + and here we can take two times nums at one because as you can see here nums at one corresponds to index two now + the same for every other index and here regarding the last value, we have an edge case. We uh have to multiply this by zero. So we should do zero times nums at n minus one.

[00:04:04]Now let's see what's happening here. How do we go from zero rotations to one rotation? First here we were doing zero times this value and now we are doing one times this value. So if we look at this part, we are just adding nums at zero. We are adding a four.

[00:04:25]If we look at this part before we were doing one times this value, now we are doing two times this value. So the difference here is just nums at one. The difference is three. So we can do nums at zero + nums at one + every other number in the array.

[00:04:47]And remember this edge case. We don't have to sum this number because the new index is zero and zero times anything is zero. So we can say that F1 is the previous accumulated result meaning F0 + the total sum of this array which is 15 minus the number that we have to remove because remember that here we take the total sum. So even though we have to remove this number, we subtract it here and then we need to subtract the contribution of this last number in the previous scenario. Why? Well because remember that we are taking the total result for this previous scenario. So we need to subtract the corresponding contribution because now we need to do zero times this last number. Okay? So we are taking the total 15 minus the number six and we need to subtract this contribution in this previous scenario.

[00:05:44]So this is the final formula. And now with this we can build the result. What if we call F0? Well we can just go through these elements one by one and take each index times its value. 0 * 4 is 0 + 3 * 1 + 2 * 2 + 6 * 3. The result here is 25. So the result of F0 is 25 and we get this in big O of n time complexity. We have to go through these elements and that's it.

[00:06:20]Now how do we get F1? Well for this we have the formula. We can take the previous accumulated result which is 25 and now we can go one by one. Remember what we do in F1. We remove this element from here and add it to the start. So we can go through these elements from right to left starting from this one. First we remove this element. So we can do 25 + and here we take the total which was 15 minus the value for this element six minus n minus one is three. Here we have four elements. So this is three times this value six.

[00:07:06]This is equal to 16. So here we put 16.

[00:07:11]Next we are here. Remember that we go from right to left. So this is the next number. We take the previous accumulated number which is 16 in this case + total which was 15 minus the current number two minus the total amount of elements minus one. This is equal to three times the current number two.

[00:07:36]This is equal to 23. So the result of two rotations is 23. And just to be clear, this means that if we have this scenario the result is 23. Next we are here and if we do the same after this rotation, the result is 26.

[00:07:59]The maximum possible result among these four is 26. So we return this. Time complexity here is big O of n. Why? Well remember that we need to get the total sum which requires big O of n and then we have to try n rotations. This rotation requires big O of n and every other rotation runs in big O of one.

[00:08:26]Why? Well because we are using dynamic programming. We take the previous accumulated result and add the corresponding contribution for every step. So this is overall big O of n and space complexity is big O of one.

[00:08:43]Now with this in mind, let's see how to code this up. First we can say that n is the length of nums. Previous is zero initially and total is the sum of nums.

[00:08:56]And now we can say for every index in range n, every time previous plus equal nums i times the corresponding index.

[00:09:06]And we can say that the result up to this moment is equal to previous. And just to be clear, here we have F0. Okay?

[00:09:15]So now we need to compute every other result. For every index in range and here we go in reverse from n minus one up to zero in steps of minus one and every time we say that previous is equal to previous + and remember the formula.

[00:09:33]We take total minus the current number nums i and we need to subtract the contribution for this number in the previous scenario. So here we take minus n minus one times nums i. Okay?

[00:09:50]And every time the result is the maximum between what we already have in the result and previous. And finally, we can return result.

[00:10:01]So, this is the entire code. Let's submit this and see if it works.

[00:10:05]As you can see, this works and it's very efficient. So, if you find this useful, please drop a like, subscribe, and see you in the next one. Bye-bye.