def rotate(nums, k): def rev(l, r): while l < r: 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
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
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
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
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 < r: nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r -1 rev() rev(r=k-1) rev(l=k) ```
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)
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?)
My bruteforce approach: class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ for i in range(k): l = nums[len(nums)-1] nums.pop() nums.insert(0,l)
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 < k; i++) { nums[i] = temp[i]; } return nums; } k=k%n was wild throwing a runtime exception lol
Here is my version if k < len(nums): 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)
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
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 < k ; 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; } }
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 < n; start++) { 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 } } }
Same but with less duplication def rotate(self, nums: List[int], k: int) -> None: k = k % len(nums) def reverse(i, j): while i < j: nums[i], nums[j] = nums[j], nums[i] i, j = i + 1, j - 1 # reverse nums reverse(0, len(nums) - 1)
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)
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!
class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k %= n # Handle cases where k >= n l = nums[-k:] r = nums[:-k] nums[:] = l + r
Solution that is not O(1) but uses O(k) extra space: def rotate(nums, k): k = k % len(nums) temp = [] for n in nums[-k:]: temp.append(n) for i in range(len(nums) - k - 1, -1, -1): nums[(i+k) % len(nums)] = nums[i] for i, t in enumerate(temp): nums[i] = t
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) < 2: return while len(nums) < k: k = k - len(nums) l,r = 0, len(nums)-1 while l< r: nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r-1
l,r = 0, k-1 while l< r: nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r-1
l,r = k, len(nums) -1 while l< r: nums[l], nums[r] = nums[r], nums[l] l, r = l + 1, r-1
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.
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
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.
If you're still alive and interested, basically any value of k>n means we have completed 1 rotation and rotating the array again. So it is essentially a repetition of what we did earlier.
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...
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.
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.
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.
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
public class Solution { public void Rotate(int[] nums, int k) { int n=nums.Length; k= k%n; swap(nums,0,n-k-1); swap(nums,n-k,n-1); swap(nums,0,n-1); } private void swap(int[] nums, int left,int right) { while(left
in the bound condition : k=k%len(nums), you said if k is greater than the len(nums) then this condition to be applied but since we haven't made that condition prior so how is k not changing for cases where k is smaller than the len(nums); can somebody explain me this , thankyou!
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.
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
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
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.
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.
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.
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
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.
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
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
def repeat(nums,k): nums1=nums[::-1] nums2=nums1[:k] nums3=nums1[k:] nums4=nums2[::-1]+nums3[::-1] return nums4 print(repeat([1,2,3,4,5,6,7],3)) why not this one
![เปิดบ้าน โคตรสวย ป๋องกพล รู้จักตั้งนาน เพิ่งรู้ว่ารวย!!! l [Nickynachat]](http://i.ytimg.com/vi/tmgCF_2HfYI/mqdefault.jpg)
def rotate(nums, k):
def rev(l, r):
while l < r:
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
its little bit wrong because k might be larger than len(nums) so we have to normalize k first ,, and entire code of yours is correct
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
Thanks you, I was stuck trying to do the O(1) solution. Great explanation!
What a great solution and explanation! I have nothing to say but "thank you, man”！
Me an Intellectual: Slicing!
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
@@Agrover112 not sure about that, the last time that I tried, it worked😛
@@Agrover112 same showed input array
does it modify the original array or create a copy doing it this way?
😂
Thanks for the explanation :)
Also appreciate the chapters in the vid! Makes it super easy to navigate
cant tell if you are being sarcastic or what
Great explanation again :) Though I can't keep myself not thinking, how could I think this and code within 30 minutes?
u practice
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
@@valkon_ yup this, only lower tier companies ask actual DSA questions, everyone else asks med-hard questions that require unintuitive tricks to memorize
@@ThisIsntmyrealnameGoogle Can you elaborate it more please?
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
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 < r:
nums[l], nums[r] = nums[r], nums[l]
l, r = l + 1, r -1
rev()
rev(r=k-1)
rev(l=k)
```
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)
sounds interesting, but what will be your stopping condition for your loop in this case?
@@rahulsbhatt when you have completed n steps where n is length of array
this works only when n is not divisible by k.
@@tanishql1441 I did it using this method, we have to just handle an edge case.
@@isasunasra9910 whats the edge case? and how are you handling it?
This is the best I found, very clear explanation, thank you!
swift version -
func rotate(_ nums: inout [Int], _ k: Int) {
var nItems = nums.count
var k = k % nItems
var targetSlice = nums[nItems - k..
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?)
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
If youre going to do list slicing you can just do this,
Cannot thank enough for all your videos!
how did u get verify?????????
My bruteforce approach:
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for i in range(k):
l = nums[len(nums)-1]
nums.pop()
nums.insert(0,l)
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 < k; i++) {
nums[i] = temp[i];
}
return nums;
}
k=k%n was wild throwing a runtime exception lol
Here is my version
if k < len(nums):
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)
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
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 < k ; 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;
}
}
I will definitely give TLE as it is very very un-optimised
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
2 liner using python O(1):
def rotate(nums, k):
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
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 < n; start++) {
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
}
}
}
First Solution:
Time Complexity: O(n)
Space Complexity: O(n)
Second Solution:
Time Complexity: O(n)
Space Complexity: O(1)
Same but with less duplication
def rotate(self, nums: List[int], k: int) -> None:
k = k % len(nums)
def reverse(i, j):
while i < j:
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)
Thank you man, now I'm clear with this
This one does the job nicely in python.
k = k%len(nums)
if k > 0 :
nums[ : ] = nums[ -k : ] + nums[ : -k]
this is so smart and simple
can you please explain, for this code to work, why is the negative k necessary? what does the negative sign do?
@@sutheerth8479 cant be negative, he meant to just not do anything if its 0
negative k is reverse indexing of the array@@Yougottacryforthis
@@sutheerth8479negative is correct, it means go to the end of the array and subtract to get the actual index…..quick shorthand python trick
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)
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!
finally someone with a similar idea as mine. But i used LCM instead.
This also would work
k = k%len(nums)
copy = nums[0:len(nums)-k]
if k < len(nums):
nums[0:k-1] = nums[-k:]
nums[k:] = copy
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n # Handle cases where k >= n
l = nums[-k:]
r = nums[:-k]
nums[:] = l + r
Nice explaination as always!
Requesting you to please solve cherry pickup, stone game dp solution or bitmasking dp questions.
Send them to prison 😂
for space O(n), the shifting formula is, ans[i] = nums[(i + size - k)%size];
Solution that is not O(1) but uses O(k) extra space:
def rotate(nums, k):
k = k % len(nums)
temp = []
for n in nums[-k:]:
temp.append(n)
for i in range(len(nums) - k - 1, -1, -1):
nums[(i+k) % len(nums)] = nums[i]
for i, t in enumerate(temp):
nums[i] = t
Pop and insert using a for loop. Done😌
Wonderful explanation! Thank you!
Does this work with any k value?
#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]
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) < 2:
return
while len(nums) < k:
k = k - len(nums)
l,r = 0, len(nums)-1
while l< r:
nums[l], nums[r] = nums[r], nums[l]
l, r = l + 1, r-1
l,r = 0, k-1
while l< r:
nums[l], nums[r] = nums[r], nums[l]
l, r = l + 1, r-1
l,r = k, len(nums) -1
while l< r:
nums[l], nums[r] = nums[r], nums[l]
l, r = l + 1, r-1
How do you get the intuition during the interview?
Just keep doing questions and eventually you recognize patterns
Nice Explanation. Thanks!
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.
Wow, it's really very simple!
Nice video! 🔥
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]
Great & easy solution! Thanks man
I am slightly confused, I can't really understand why K = K % len(nums) is being done in the beginning. Could someone please explain?
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.
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
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.
If you're still alive and interested, basically any value of k>n means we have completed 1 rotation and rotating the array again. So it is essentially a repetition of what we did earlier.
Same logic we use in circular queue 👑
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...
Wow! thanks. I will solve it myself now.
Len(numbs) can be 0, hence we should handle that case as well
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.
His is already O(N), technically its O(3N) but you can drop the constants when calculating complexity as they don't grow.
O(1) solution is very interesting and clever
thanks for taking time and explaining! really helfpul
Initially, I thought you were from the USA. Actually, you are also Indian. 🙌🙌
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.
Exactly. Subscribed 👍
Great explanation
Nice explanation! I like it :)
Thank you for an explanation!
Great Solution.
Thank you, understood it well.
😮thanks mate
man thats some genius shit
best explanation
Shit now I look dumb thinking about this for half an hour. Thanks!
what changes do we need to make if we want to rotate the array left side the same way
My Brain is just an Phuckin Ashole...
could you just hold the [-1] of the array and then insert it at 0, k times?
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.
I tried that and got a runtime error for some testcases
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
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.
Cool concept
im your fan! thank you for your video!
Thank you
are this python's insert and pop functions useful?
for i in range(k):
nums.insert(0,nums.pop())
return nums
Inserting at 0 requires moving all other numbers behind it. So that solution would be O(n^2)
public class Solution {
public void Rotate(int[] nums, int k) {
int n=nums.Length;
k= k%n;
swap(nums,0,n-k-1);
swap(nums,n-k,n-1);
swap(nums,0,n-1);
}
private void swap(int[] nums, int left,int right)
{
while(left
oh that is CLEVER
More Pythonic way:
k = k % len(nums)
nums.reverse()
nums[:k] = reversed(nums[:k])
nums[k:] = reversed(nums[k:])
this code won't compile if the given array is empty since k = k % len(nums) will result in modulo by zero, which throws a zero division error
can someone explain to me why you have to decrement and increment left and right in each loop?
You have to manually increment or decrement when using a while loop.
in the bound condition : k=k%len(nums), you said if k is greater than the len(nums) then this condition to be applied but since we haven't made that condition prior so how is k not changing for cases where k is smaller than the len(nums); can somebody explain me this , thankyou!
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.
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
Is the time complexity O(n) if we use multiple while loops
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)
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
You're god man
We can also use pop() and insert() methods too right?
Maybe something like this --
K=k%len(nums)
i=0
While i
In the worst case this takes O(n^2)
Insertion is O(n) and you can do it up to n times here
Why don't we need a temporary variable to swap like we do in C++?
k = k %len(nums)
nums[:] = nums[-k:] + nums[:-k]
THE END
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.
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)
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.
love it!
How did you figuar this out
Sorry but I can't understand why we need to k % length. Any body can help me to explain it please.
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.
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.
U a God
I tried slicing the array but I forgot to mod by the array size and I only did it by k and it didn’t work with odd length arrays. I feel so stupid lol
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)
For I in range(k):
Nums.insert(0, nums.pop())
Return nums
Why not just do this?
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
Because you solution has complexity O(n^2). Inserting at the beginning of the list means creating a new array from scratch
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.
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.
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.
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]
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
Yeah, working fine in IDE but leetcode isn't accepting it.
same issue
@@sagargulati639 slicing creates a copy when doing it
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
Amazing
Lot of likes to you!
why cant we use built in reverse function in python?
you could use but definitely not in a real interview
public void rotate(int[] nums, int k) {
if (k > nums.length) {
k = k % nums.length;
}
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int l, int r) {
while (l < r) {
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
l++;
r--;
}
}
def repeat(nums,k):
nums1=nums[::-1]
nums2=nums1[:k]
nums3=nums1[k:]
nums4=nums2[::-1]+nums3[::-1]
return nums4
print(repeat([1,2,3,4,5,6,7],3)) why not this one