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
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
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
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)
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) ```
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
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!
The % operator returns the remainder . Say 8%3 returns 2. However, when the divisor is lesser than the dividend such as 1%3, you get the divisor back again since it can not be further divided. Hope this helps.
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
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
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)
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 } } }
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.
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; } }
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!
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...
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
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.
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
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.
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.
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
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
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.
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.
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
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.
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.
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.
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
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
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]
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
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
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
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
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”！
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 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
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?
😂
This is the best I found, very clear explanation, thank you!
def rotate(nums,k):
for i in range(k):
nums.insert(0,"")
nums[0] = nums[-1]
nums.pop(-1)
return(nums)
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?
Cannot thank enough for all your videos!
how did u get verify?????????
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)
```
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,
swift version -
func rotate(_ nums: inout [Int], _ k: Int) {
var nItems = nums.count
var k = k % nItems
var targetSlice = nums[nItems - k..
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
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!
The % operator returns the remainder . Say 8%3 returns 2. However, when the divisor is lesser than the dividend such as 1%3, you get the divisor back again since it can not be further divided. Hope this helps.
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
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
Does this work with any k value?
How do you get the intuition during the interview?
Just keep doing questions and eventually you recognize patterns
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)
Thank you man, now I'm clear with this
2 liner using python O(1):
def rotate(nums, k):
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
for space O(n), the shifting formula is, ans[i] = nums[(i + size - k)%size];
just use slicing instead
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k = k%n
nums[:] = nums[n-k:]+nums[:n-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
}
}
}
Nice explaination as always!
Requesting you to please solve cherry pickup, stone game dp solution or bitmasking dp questions.
Send them to prison 😂
First Solution:
Time Complexity: O(n)
Space Complexity: O(n)
Second Solution:
Time Complexity: O(n)
Space Complexity: O(1)
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.
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
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
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
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)
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.
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...
Wonderful explanation! Thank you!
what changes do we need to make if we want to rotate the array left side the same way
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
Great & easy solution! Thanks man
#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]
Wow! thanks. I will solve it myself now.
Pop and insert using a for loop. Done😌
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.
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
My Brain is just an Phuckin Ashole...
thanks for taking time and explaining! really helfpul
Nice Explanation. Thanks!
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]
Wow, it's really very simple!
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)
Len(numbs) can be 0, hence we should handle that case as well
O(1) solution is very interesting and clever
Why don't we need a temporary variable to swap like we do in C++?
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.
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
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
Same logic we use in circular queue 👑
Nice explanation! I like it :)
Nice video! 🔥
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
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.
Great explanation
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
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.
Thank you for an explanation!
Thank you, understood it 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.
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.
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
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)
Exactly. Subscribed 👍
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)
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.
im your fan! thank you for your video!
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
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]
Shit now I look dumb thinking about this for half an hour. Thanks!
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.
More Pythonic way:
k = k % len(nums)
nums.reverse()
nums[:k] = reversed(nums[:k])
nums[k:] = reversed(nums[k:])
why cant we use built in reverse function in python?
you could use but definitely not in a real interview
Initially, I thought you were from the USA. Actually, you are also Indian. 🙌🙌
How did you figuar this out
Can someone explain why this is a two pointer algorithm?
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
Great Solution.
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
best explanation
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]
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.
@@NeetCode thanks!
@@NeetCode what even is temp ????
@@rodrigo-tj1gf a variable, here using for temporarily storing data
why cannot we just pop the 0th element and append it to x%len(nums) times huhhh??
There is a test case where the len of nums is millions. The loop takes forever to complete.
k = k %len(nums)
nums[:] = nums[-k:] + nums[:-k]
THE END
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
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
man thats some genius shit
Cool concept
Your explanation is great. But, as a beginner, I still don't understand why % come into place. Could you elaborate, please?
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
😮thanks mate
man I just feel dumber than I've ever felt