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)
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)
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 } } }
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 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?)
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
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)
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; } }
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!
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 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...
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.
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.
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.
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.
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
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!
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
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.
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
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.
Here is a one-line solution: nums[:] = nums[len(nums) - k % len(nums):] + nums [:len(nums) - k % len(nums)] Let me explain: The slice assignment notation in Python allows you to modify a portion of a mutable sequence object (such as a list) in place: `nums[:] =` Then, we pick the last 'k' elements of the list using slicing: `nums[len(nums) - k % len(nums):]` The expression `len(nums) - k % len(nums)` calculates the starting index for the slice, ensuring that it wraps around the list when 'k' is larger than the length of 'nums'. Next, we concatenate this slice with the elements from the beginning of the list up to the last 'k' element: `+ nums[:len(nums) - k % len(nums)]` This concatenation effectively shifts the elements in 'nums' to the right by 'k' positions. The combined result of these slices is then assigned back to 'nums', effectively modifying the list in place.
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.
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
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
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
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?
😂
What a great solution and explanation! I have nothing to say but "thank you, man”！
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)
```
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
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?
swift version -
func rotate(_ nums: inout [Int], _ k: Int) {
var nItems = nums.count
var k = k % nItems
var targetSlice = nums[nItems - k..
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)
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
}
}
}
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
Cannot thank enough for all your videos!
how did u get verify?????????
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,
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
2 liner using python O(1):
def rotate(nums, k):
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
First Solution:
Time Complexity: O(n)
Space Complexity: O(n)
Second Solution:
Time Complexity: O(n)
Space Complexity: O(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)
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
How do you get the intuition during the interview?
Just keep doing questions and eventually you recognize patterns
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
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
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
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
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
Does this work with any k value?
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.
for space O(n), the shifting formula is, ans[i] = nums[(i + size - k)%size];
#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]
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
Thank you man, now I'm clear with this
Pop and insert using a for loop. Done😌
Nice explaination as always!
Requesting you to please solve cherry pickup, stone game dp solution or bitmasking dp questions.
Send them to prison 😂
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]
Wonderful explanation! Thank you!
Nice video! 🔥
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...
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.
Great explanation
Great & easy solution! Thanks man
Wow, it's really very simple!
what changes do we need to make if we want to rotate the array left side the same way
O(1) solution is very interesting and clever
My Brain is just an Phuckin Ashole...
Wow! thanks. I will solve it myself now.
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.
Len(numbs) can be 0, hence we should handle that case as well
thanks for taking time and explaining! really helfpul
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.
Same logic we use in circular queue 👑
Thank you for an explanation!
Initially, I thought you were from the USA. Actually, you are also Indian. 🙌🙌
Great Solution.
Thank you, understood it well.
Nice explanation! I like it :)
Cool concept
oh that is CLEVER
Exactly. Subscribed 👍
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.
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)
😮thanks mate
man thats some genius shit
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
best explanation
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.
Why don't we need a temporary variable to swap like we do in C++?
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!
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--;
}
}
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
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.
Thank you
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
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.
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
More Pythonic way:
k = k % len(nums)
nums.reverse()
nums[:k] = reversed(nums[:k])
nums[k:] = reversed(nums[k:])
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)
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
im your fan! thank you for your video!
How did you figuar this out
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)
Shit now I look dumb thinking about this for half an hour. Thanks!
You're god man
why cant we use built in reverse function in python?
you could use but definitely not in a real interview
love it!
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.
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.
k = k %len(nums)
nums[:] = nums[-k:] + nums[:-k]
THE END
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
Here is a one-line solution:
nums[:] = nums[len(nums) - k % len(nums):] + nums [:len(nums) - k % len(nums)]
Let me explain:
The slice assignment notation in Python allows you to modify a portion of a mutable sequence object (such as a list) in place:
`nums[:] =`
Then, we pick the last 'k' elements of the list using slicing:
`nums[len(nums) - k % len(nums):]`
The expression `len(nums) - k % len(nums)` calculates the starting index for the slice, ensuring that it wraps around the list when 'k' is larger than the length of 'nums'.
Next, we concatenate this slice with the elements from the beginning of the list up to the last 'k' element:
`+ nums[:len(nums) - k % len(nums)]`
This concatenation effectively shifts the elements in 'nums' to the right by 'k' positions.
The combined result of these slices is then assigned back to 'nums', effectively modifying the list in place.
Can someone explain why this is a two pointer algorithm?
U a God
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]
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
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