Rotate Array - Leetcode 189 - Python
Ғылым және технология
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: leetcode.com/problems/rotate-...
0:00 - Read the problem
1:35 - Drawing Explanation
6:33 - Coding Explanation
leetcode 189
This question was identified as a google interview question from here: github.com/xizhengszhang/Leet...
#rotate #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.
Пікірлер: 192
What a great solution and explanation! I have nothing to say but "thank you, man”!
Thanks you, I was stuck trying to do the O(1) solution. Great explanation!
This is the best I found, very clear explanation, thank you!
Thanks for the explanation :) Also appreciate the chapters in the vid! Makes it super easy to navigate
@jigarchudasama
5 ай бұрын
cant tell if you are being sarcastic or what
Updated versrion with helper function >> rev() ``` class Solution: def rotate(self, nums: List[int], k: int) -> None: k = k % len(nums) def rev(l=0, r=len(nums) - 1): while l nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r -1 rev() rev(r=k-1) rev(l=k) ```
Thank you, sir; I learned a lot from your tutorials.
Me an Intellectual: Slicing!
@Agrover112
2 жыл бұрын
lol i was trying slicing getting the correct output but idk why the fuck leetcode still showed the nums as the original array? Is it someting with their test cases
@programming1734
2 жыл бұрын
@@Agrover112 not sure about that, the last time that I tried, it worked😛
@subhadeepdeb3678
2 жыл бұрын
@@Agrover112 same showed input array
@jinphinity158
2 жыл бұрын
does it modify the original array or create a copy doing it this way?
@sKONNIKASTURI
9 ай бұрын
😂
Great explanation again :) Though I can't keep myself not thinking, how could I think this and code within 30 minutes?
@adityapatel1
2 жыл бұрын
u practice
@valkon_
2 жыл бұрын
After months of leetcoding, I am starting to believe that 80% is memorizing solutions. No way I would think that in a interview setting under pressure
@ThisIsntmyrealnameGoogle
2 жыл бұрын
@@valkon_ yup this, only lower tier companies ask actual DSA questions, everyone else asks med-hard questions that require unintuitive tricks to memorize
@omkarjadhav848
Жыл бұрын
@@ThisIsntmyrealnameGoogle Can you elaborate it more please?
@velainsan5339
8 ай бұрын
that means lower tier companies asks easy dsa question which can be solved in an interview setting under pressure without memorizing the solution before hand which in return tests your problem solving abilitites (therefore he referred to it as real dsa questions ) @@omkarjadhav848
def rotate(nums, k): def rev(l, r): while l nums[l], nums[r] = nums[r], nums[l] l +=1 r -=1 rev(0, len(nums) - 1) rev(0, k-1) rev(k, len(nums)-1) return nums # saving you all to write while loop three times
Cannot thank enough for all your videos!
@bishwashkumarsah171
Жыл бұрын
how did u get verify?????????
thanks for taking time and explaining! really helfpul
Great & easy solution! Thanks man
Thank you for an explanation!
Wow! thanks. I will solve it myself now.
Nice Explanation. Thanks!
Thank you, understood it well.
Wonderful explanation! Thank you!
Nice explaination as always! Requesting you to please solve cherry pickup, stone game dp solution or bitmasking dp questions.
@Dragon-Slay3r
9 ай бұрын
Send them to prison 😂
Thank you man, now I'm clear with this
Exactly. Subscribed 👍
for space O(n), the shifting formula is, ans[i] = nums[(i + size - k)%size];
Nice video! 🔥
Great explanation
Nice explanation! I like it :)
I got stuck at 37/38 cases and I hit time limit exceeded. I was trying to do O(1) space. Your approach was so different than mine 😂 this one had me stumped
Wow, it's really very simple!
Great Videos! But i know you teach only the efficient way but i want to know what are the other way programs to differenciate. i want learn other approaches also for learn to solve same problems in different way so please upload different approches with code also...
Fantastic explanation
I think this solution is even easier k = k % len(nums) if k != 0: nums[:] = nums[-k:] + nums[:len(nums)-k] You can just slice last k elem and first len(nums)-k elems It's also O(n) in time but takes O(n) space, although leet code shows the same amount of space for both (maybe because of caching?)
Same logic we use in circular queue 👑
what changes do we need to make if we want to rotate the array left side the same way
Thank you
swift version - func rotate(_ nums: inout [Int], _ k: Int) { var nItems = nums.count var k = k % nItems var targetSlice = nums[nItems - k..
im your fan! thank you for your video!
Cool concept
Here is my version if k nums.reverse() nums[:k] = nums[:k][::-1] nums[k:] = nums[k:][::-1] else: self.rotate(nums,k-len(nums)) if the number of rotation is greater than len of list we do rotation of the list k-len(nums) time for example [1,2,3] and k = 4 the rotation of this will be like the rotation of k = 1 so we do self.rotate(nums,1)
There is a second way to do it. Let's say you have 1,2,3,4,5. and k = 2. Step 1. move index 0 number to k+0 position(2). the array now will be _,2,1,4,5 and you use a temp int to store the index k+i number which is 3. Step 2.instead of moving index 1 number, you move k+2 number. u shift 3 to 3+k position. now you temp int will be 5. and array will be _,2,1,4,3. With 3 more steps you will get your result. You are only using 1 temp integer so the space is O(1) and the time is O(n)
@rahulsbhatt
Жыл бұрын
sounds interesting, but what will be your stopping condition for your loop in this case?
@RohithMusic
Жыл бұрын
@@rahulsbhatt when you have completed n steps where n is length of array
@tanishql1441
Жыл бұрын
this works only when n is not divisible by k.
@isasunasra9910
10 ай бұрын
@@tanishql1441 I did it using this method, we have to just handle an edge case.
@disenchanted_dove
7 ай бұрын
@@isasunasra9910 whats the edge case? and how are you handling it?
Great Solution.
best explanation
😮thanks mate
hey! this was a really heplful vedio but how did you figure out you have to mod it I mean the math part to solve the out of bounds part. I cant figure how to do this stuff while solving . it will be very helpful if you replied.
love it!
Does this work with any k value?
great video man. But there is an even better solution. it's possible to do this in O(N) time and O(1) memory in one single pass, rather than two passes over the array. it's not so much of an optimization over yours, but just saying that there is a slightly better solution.
@oblivitv1337
Жыл бұрын
His is already O(N), technically its O(3N) but you can drop the constants when calculating complexity as they don't grow.
there is actually a problem in this code, we have to update the value of k by k = k % nums.length in order avoid index out of bounds error , for the cases like nums = [ 1 , 2 ] and k = 3.
Came up with another soln this too is a constant space soln and works for rotating the array to the left too for some problems (just in case) by slight changes code - public static int[] rotate_array_to_right_by_k_steps(int[] nums,int k){ int n = nums.length; k=k%n; int[] temp = new int[k]; int m=0; for(int i=n-k;i=k;i--){ nums[i] = nums[i-k]; } int j=0; for (int i = 0; i nums[i] = temp[i]; } return nums; } k=k%n was wild throwing a runtime exception lol
are this python's insert and pop functions useful? for i in range(k): nums.insert(0,nums.pop()) return nums
@jokester398
Жыл бұрын
Inserting at 0 requires moving all other numbers behind it. So that solution would be O(n^2)
i did this. class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ while k >0: ele = nums.pop() nums.insert(0,ele) k -= 1
Len(numbs) can be 0, hence we should handle that case as well
This also would work k = k%len(nums) copy = nums[0:len(nums)-k] if k nums[0:k-1] = nums[-k:] nums[k:] = copy
Is the time complexity O(n) if we use multiple while loops
@mirzataimoor9632
2 жыл бұрын
Yes. Because the number of operations will be n. In worst case, O(n) + O(n) + O(n) = O(3n). In BigO, you ignore the constant, hence it becomes O(n)
can someone explain to me why you have to decrement and increment left and right in each loop?
@ernestmummey6446
2 жыл бұрын
You have to manually increment or decrement when using a while loop.
I am slightly confused, I can't really understand why K = K % len(nums) is being done in the beginning. Could someone please explain?
@cici-lx6np
2 жыл бұрын
It may not needed when k value is smaller than the length of the nums. When k >= len(nums), adding this step could save time. Hope this could help.
@triscuit5103
2 жыл бұрын
Sup babe? Listen, yeah? Say your array length is 5, you got 5 items in your array. Say K is 12, yeah? Since your array has 5 items, shifting it 5 times gives you the original array again with the items in their original places. That's why you can remove all multiples of 5 from your K, since each shift of 5 times will end up not changing the array at all. 12 % 5 = 2. So you just need to shift twice? You get what I am saying love? Hugs and kisses you dirty naughty bad boy, go get it tiger
@johnchen3166
Жыл бұрын
This comment might come too late, but the intuition behind it is exactly an explanation of how mod works. In this rotation method we wrote up, we can't store any element in an index greater than 5. For example, if you have an index at 6, you loop back to 1. That is the definition of mod. If you have worked with mod before, you will know the problem basically screaming you to use it. Here's a nutshell explanation. Think of a clock. It only has numbers 1-12: the number 13 doesn't exist since it looks back to 1. In our situation, imagine the indices of our array is a big clock with the numbers 1-5 instead. What happens if you have the number 6? It goes back to 1. If it's 7, it goes to 2. If it's 8, it goes to 3 etc. Hope this helps.
Shit now I look dumb thinking about this for half an hour. Thanks!
man thats some genius shit
Same but with less duplication def rotate(self, nums: List[int], k: int) -> None: k = k % len(nums) def reverse(i, j): while i nums[i], nums[j] = nums[j], nums[i] i, j = i + 1, j - 1 # reverse nums reverse(0, len(nums) - 1) # reverse nums[:k] reverse(0, k - 1) # reverse nums[K:] reverse(k, len(nums) - 1)
This one does the job nicely in python. k = k%len(nums) if k > 0 : nums[ : ] = nums[ -k : ] + nums[ : -k]
@fishertech
Жыл бұрын
this is so smart and simple
@sutheerth8479
Жыл бұрын
can you please explain, for this code to work, why is the negative k necessary? what does the negative sign do?
@Yougottacryforthis
9 ай бұрын
@@sutheerth8479 cant be negative, he meant to just not do anything if its 0
@lilrdjackofa
7 ай бұрын
negative k is reverse indexing of the array@@Yougottacryforthis
@salczar
2 ай бұрын
@@sutheerth8479negative is correct, it means go to the end of the array and subtract to get the actual index…..quick shorthand python trick
i did came with solition on my own which works in o(1) space and O(k n) Time but gives TLE code below. class Solution { public void rotate(int[] nums, int k) { for(int i = 0; i rotate(nums); } } public static void rotate(int[] nums){ int idx1 = nums.length - 1; int idx2 = nums.length - 2; while(idx2 >= 0){ swap(idx1 , idx2 , nums); idx1 = idx2; idx2 = idx2-1; } } public static void swap(int a , int b , int[] nums){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }
@arishsheikh3000
Жыл бұрын
I will definitely give TLE as it is very very un-optimised
could you just hold the [-1] of the array and then insert it at 0, k times?
@omik7429
3 жыл бұрын
you could do it that way but insertion at 0 will basically shift every element after it to its right. and it might get expensive if the list is too long.
@fishertech
Жыл бұрын
I tried that and got a runtime error for some testcases
U a God
IMPRESSIVE
quicker solution: class Solution(object): def rotate(self, nums, k): k = k%(len(nums)) nums[:] = nums[::-1] nums[:k],nums[k:]=nums[:k][::-1], nums[k:][::-1] return nums
How did you figuar this out
We can also use pop() and insert() methods too right? Maybe something like this -- K=k%len(nums) i=0 While i
@bartekbinda6978
4 ай бұрын
In the worst case this takes O(n^2) Insertion is O(n) and you can do it up to n times here
Its kind of suprising to me, that this problem is set as medium difficulty. I thought it was pretty simple. Honestly, I've seen wuite a few easy problems that were more complex.
hi, can I do this? k = len(array)//k # if k is greater than length of array new_array = array[-k:] + array[0:-k] # adding the back part of the array to the front part return new_array
Here's my O(N) time, O(1) space complexity, with a single pass over the data class Solution: def rotate(self, nums: List[int], k: int) -> None: L = len(nums) if L 1 and (l := gcd(L, k)) > 1: # When gcd > 1, a fraction of the array loop between themselves. for i in range(1, l): swap(i)
@lightlysal
11 ай бұрын
I got the idea of looping through "cycles" of numbers like this but I couldn't figure out how to calculate where the loops were! I'll take this home to try and study it. Thanks!
@ruthlessogre2441
10 ай бұрын
finally someone with a similar idea as mine. But i used LCM instead.
I'm a little confused, can someone please explain to me why this time is O(1) and not O(log N) ? We have 3 cycles, where we go through half of the original array with the first cycle, the second cycle and the third cycle also through half of the array.
@cosmoscrew2
Жыл бұрын
Because the number of operations will be n. In worst case, O(n) + O(n) + O(n) = O(3n). In BigO, you ignore the constant, hence it becomes O(n)
@trenvert123
Жыл бұрын
To add to this. Big O(logn) would actually be better than O(n). O(logn) would be, for instance if we eliminated half the array each operation, and didn't need to loop through the entire thing.
Does anyone know why is this not working def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ nums = nums[k+1:]+nums for i in range(k): nums.pop() print("nums = ",nums) here while printing its giving right answer but its not passing the case when it ran in the console
The cleanest code that's used in all practical applications is nums= nums[-k:] + nums[:k+1]. Does anyone know why this doesn't work for the "in place" requirement? Even if you do nums_new = nums_new[-k:] + nums_new[:k+1] nums = nums_new
@bradleyhanson
Ай бұрын
Slicing creates a copy of the array so you are allocating space and therefore your solution is O(n) space. Optimal is O(1) space.
Why don't we need a temporary variable to swap like we do in C++?
Initially, I thought you were from the USA. Actually, you are also Indian. 🙌🙌
why cant we use built in reverse function in python?
@ihsannuruliman3656
2 жыл бұрын
you could use but definitely not in a real interview
Why am I getting time limit Exceeded error on my code? class Solution(object): def rotate(self, nums, k): for x in range(k): a = nums.pop() nums.insert(0, a)
Amazing Lot of likes to you!
Can someone explain why this is a two pointer algorithm?
How about two pointer. i for k steps then continue i till end while starting j from start until i reaches the end. then return arr[j:]+arr[:j]
First Solution: Time Complexity: O(n) Space Complexity: O(n) Second Solution: Time Complexity: O(n) Space Complexity: O(1)
why is: nums[l] = nums[r] nums[r] = nums[l] different than writing it as: nums[l], nums[r] = nums[r], nums[l] I had been getting the wrong solution because of this syntax when reversing it using the first method I get: [7,6,5,4,3,2,1] which is the desired output, but the other way I get: [7,6,5,4,5,6,7]
@NeetCode
Жыл бұрын
The second one is the equivalent of temp = nums[r] nums[l] = nums[r] nums[r] = temp Which is different from the first one you wrote. Hope that helps.
@GP-rn6bx
Жыл бұрын
@@NeetCode thanks!
@rodrigo-tj1gf
Жыл бұрын
@@NeetCode what even is temp ????
@ankiitamalik
Жыл бұрын
@@rodrigo-tj1gf a variable, here using for temporarily storing data
Sorry but I can't understand why we need to k % length. Any body can help me to explain it please.
@poomprawatkomolthitinan5209
2 жыл бұрын
because rotating over length time will repeat the process. Consider list of 1,2,3. Rotating it 1,4,7,10,.. times yield the same result 3,1,2.
@nateo7045
2 жыл бұрын
Tbh if you don’t know what the modulo operator’s function is, you probably shouldn’t be attempting medium questions. This is a pretty big jump though on their “14 days algorithm” plan thing if you got it from there. But basically it is a way of putting a cap on any number so that it’s confined within that value and anything that “overflows” over that value resets against from 0. So say say for “n % 3”, any number under 3 will just be 3, but once we surpass 3, the remainder becomes our new value.. 1%3=1, 2%3=2, 3%3=0, 4%3=1, 5%3=2, 6%3=0, 7%3=1.. and so on. It’s actually pretty easy to understand, just look it up if you haven’t yet.
But what if k is 0 and length is 8? You'd be reversing the whole array in the first while loop when it should not be modified at all.
@yongxuan5196
Жыл бұрын
you'll reverse it twice I believe, once for the whole array and once on the third reversal since k=0. the second reversal is skipped.
@chrisaguilera1767
11 ай бұрын
Of course you can optimize to return immediately if k is 0. Even if you don't return early, the entire array will be reversed twice, so the array will ultimately be unchanged.
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; k = k % n; // Normalize k to prevent unnecessary rotations int count = 0; // Counter to track the number of elements placed in their correct positions for (int start = 0; count int current = start; // Initialize current with the start of the cycle int prev = nums[start]; // This holds the value that will be moved around in the cycle do { int next = (current + k) % n; // Calculate the index to place the value of `prev` int temp = nums[next]; // Store the value at `next` index before it's overwritten nums[next] = prev; // Place the previous value into its new position prev = temp; // Update prev to the value that was at `next` to continue the cycle current = next; // Move to the next index count++; // Increment the counter since we've placed another element correctly } while (start != current); // Continue until the cycle is complete } } }
Why does slicing not work? class Solution(object): def rotate(self, nums, k): b=nums[-k:] a=nums[:(len(nums)-k)] b.extend(a) nums=b Leetcode shows the same input array, but it works perfectly in IDE
@sagargulati639
2 жыл бұрын
Yeah, working fine in IDE but leetcode isn't accepting it.
@BruKfu
2 жыл бұрын
same issue
@humanityrush
2 жыл бұрын
@@sagargulati639 slicing creates a copy when doing it
@joejohn.
Жыл бұрын
I surprised myself with 95% runtime but only 28% memory percentile with a stab before watching using this idea. class Solution: def rotate(self, nums: List[int], k: int) -> None: nk = k % len(nums) c = nums.copy() sub = c[-nk:] del c[-nk:] c = sub + c for i, v in enumerate(c): nums[i] = v
You're god man
Your explanation is great. But, as a beginner, I still don't understand why % come into place. Could you elaborate, please?
@ugochukwustephenmbonu7974
Жыл бұрын
Imagine you have [1,2] and k is 3. If you rotate 3 times, it will go like this: 1 rotation [2,1] 2 rotation [1,2] 3 rotation [2,1] This is same as rotating just once, which we can get with k % len(nums) (3 mod 2 = 1) Using % or mod here will keep our number of rotations within array size
i love you
My Brain is just an Phuckin Ashole...
if k%2!=0: k = k+1 nums = nums[k: len(nums)]+nums[0:k] print(nums) why it's not working in leetcode? But it's working in Python IDE!
@renukabavana5712
2 жыл бұрын
can you please tell me what is this k refers to ??
@amangautam1779
2 жыл бұрын
@@renukabavana5712 number of steps to rotate the array
#TC : O(n), space:O(1) inplace def rotate(nums, k): k %= len(nums) # nums[-k:] = [5, 6, 7] # nums[:-k] = [1, 2, 3, 4] nums[:] = nums[-k:] + nums[:-k] nums,k = [1, 2, 3, 4, 5, 6, 7],3 rotate(nums, k) print(nums) # Output: [5, 6, 7, 1, 2, 3, 4]
In python can't we just do : nums = nums[-k:] + nums[:-k] ?
If max array size is smaller than k, leetcode can't accept the above answer. I added some code with neetcode's code. I hope it will help you guys. class Solution: def rotate(self, nums: List[int], k: int) -> None: if len(nums) return while len(nums) k = k - len(nums) l,r = 0, len(nums)-1 while l nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r-1 l,r = 0, k-1 while l nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r-1 l,r = k, len(nums) -1 while l nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r-1
The pythonistas that want to use slicing, here, def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k = k%n nums[0:n-k] = nums[0:n-k][::-1] nums[n-k:n] = nums[n-k:n][::-1] nums[0:n] = nums[::-1]
For I in range(k): Nums.insert(0, nums.pop()) Return nums Why not just do this?
@Proxxx100
2 жыл бұрын
I think the point of the question in an interview is for you to go through the process instead of using built in functions that solve the point of the question you know? That is how they are able to differentiate who can actually think and who is just spitting something they just repeated over and over
@MrWr99
2 жыл бұрын
Because you solution has complexity O(n^2). Inserting at the beginning of the list means creating a new array from scratch
why cannot we just pop the 0th element and append it to x%len(nums) times huhhh??
@iamashwincherian
22 күн бұрын
There is a test case where the len of nums is millions. The loop takes forever to complete.
could you proove that this algorithm give the solution ?
k = k % len(nums) nums[:] = nums[-k:]+nums[:-k] Is there something wrong with this solution? It works though!
@WaldoTheWombat
Жыл бұрын
it's like mine: i = len(nums) - k % len(nums) nums[i:], nums[:i] = nums[:i], nums[i:]
@DavidDLee
Жыл бұрын
Yours is a great O(N) time and O(N) space complexity. LeetCode solved it in O(1) space.
man I just feel dumber than I've ever felt
can't we solve this using two pointers?
pretty neet
Although all these tricks are cool and sexy. wonder what the point of those is if they are not intuitive.
@jigarchudasama
5 ай бұрын
to clear interviews.