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
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)
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?)
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
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) ```
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...
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.
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!
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)
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
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)
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)
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 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; } }
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.
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
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.
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
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 } } }
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.
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.
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
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!
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.
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
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'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.
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 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!
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
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
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
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?
😂
This is the best I found, very clear explanation, thank you!
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)
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,
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
Cannot thank enough for all your videos!
how did u get verify?????????
2 liner using python O(1):
def rotate(nums, k):
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
Thank you, sir; I learned a lot from your tutorials.
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];
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)
```
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
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...
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.
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!
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
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
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)
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
Wonderful explanation! Thank you!
Thank you man, now I'm clear with this
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?
Why don't we need a temporary variable to swap like we do in C++?
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)
My Brain is just an Phuckin Ashole...
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.
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
Great & easy solution! Thanks man
thanks for taking time and explaining! really helfpul
swift version -
func rotate(_ nums: inout [Int], _ k: Int) {
var nItems = nums.count
var k = k % nItems
var targetSlice = nums[nItems - k..
Len(numbs) can be 0, hence we should handle that case as well
Fantastic explanation
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
Nice Explanation. Thanks!
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.
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
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)
what changes do we need to make if we want to rotate the array left side the same way
Does this work with any k value?
Pop and insert using a for loop. Done😌
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.
Nice video! 🔥
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
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)
Nice explanation! I like it :)
Wow! thanks. I will solve it myself now.
Thank you for an explanation!
Wow, it's really very simple!
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
}
}
}
O(1) solution is very interesting and clever
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
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.
Thank you, understood it well.
Great Solution.
Great explanation
How do you get the intuition during the interview?
let me show you something.... still no explanation on the thought about how does this "reverse trick" come up with?
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
Initially, I thought you were from the USA. Actually, you are also Indian. 🙌🙌
GUYS CAN you help me?
Can this be a suitable solution?
n = len(nums)
k = k % n
nums = nums[n - k : n] + nums[: n - k]
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.
In python can't we just do : nums = nums[-k:] + nums[:-k] ?
Thank you
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.
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
Cool concept
Exactly. Subscribed 👍
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.
best explanation
#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]
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)
im your fan! thank you for your video!
love it!
could you proove that this algorithm give the solution ?
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.
😮thanks mate
Shit now I look dumb thinking about this for half an hour. 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]
Can someone explain why this is a two pointer algorithm?
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
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)
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
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.
man thats some genius shit
can't we solve this using two pointers?
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.
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
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
Same logic we use in circular queue 👑
void rotate(int *nums, int numsSize, int k) {
int t=0;
while(t=0;i--){
*(nums + (i+1))=*(nums+i);
}
numsSize++;
*nums=*(nums + numsSize-1);
numsSize--;
t++;
}
}
This code works fine on compilers but does not work on Leetcode can somebody explain plz 🥲😭🙏
man I just feel dumber than I've ever felt
k = k % len(nums)
nums[:] = nums[-k:]+nums[:-k]
Is there something wrong with this solution? It works though!
it's like mine:
i = len(nums) - k % len(nums)
nums[i:], nums[:i] = nums[:i], nums[i:]
Yours is a great O(N) time and O(N) space complexity.
LeetCode solved it in O(1) space.