Thank you so much bro! Been racking my brain since the past 48 hours on this problem. I appreciate the gradual and slow explanation with the brute force first. Subscribed!
@9:20 Slight correction, The time complexity is O(2n) = O(n) because the array is traversed twice, once for squaring all the numbers and once for comparing for placement in new array. Also if there is a requirement for something similar in API terms then there can be a solution where you do not modify the original input and just use a single array. Because at any time you are only comparing 2 squares you need not create a separate array of squares, you can store left pointer, right pointer, left square and right square in 4 variables and then do the iteration and store it in the new array directly. class Solution: def sortedSquares(self, A: List[int]) -> List[int]: return_array = [0] * len(A) write_pointer = len(A) - 1 left_read_pointer = 0 right_read_pointer = len(A) - 1 left_square = A[left_read_pointer] ** 2 right_square = A[right_read_pointer] ** 2 while write_pointer >= 0: if left_square > right_square: return_array[write_pointer] = left_square left_read_pointer += 1 left_square = A[left_read_pointer] ** 2 else: return_array[write_pointer] = right_square right_read_pointer -= 1 right_square = A[right_read_pointer] ** 2 write_pointer -= 1 return return_array
We can ignore the traversal of input array to square the integers. int n = nums.length; int[] result = new int[n]; int head = 0; int tail = n - 1; for (int i = n - 1; i >= 0; i--) { int headSquare = nums[head] * nums[head]; int tailSquare = nums[tail] * nums[tail]; if (headSquare > tailSquare) { result[i] = headSquare; head++; } else { result[i] = tailSquare; tail--; } } return result;
You could modify the initial array by using a temporary local variable to store values and then modify the initial array. Depends on your requirements.
![[Live] : ONE 168 วันนี้!! "โจนาธาน vs ซุปเปอร์เล็ก"](http://i.ytimg.com/vi/0jIN65KgJsI/mqdefault.jpg)
Thank you so much bro!
Been racking my brain since the past 48 hours on this problem.
I appreciate the gradual and slow explanation with the brute force first.
Subscribed!
Welcome aboard !!
waiting for such more approaches
lots of love from Mumbai❣
One of the best explanations on youtube... :)...Thanks a lot sir
It helps.. you deserve subscriptions..👍🏻
Bhaiyya you look like my cousin brother
..that's why I feel connected to you....thanksss
great explanation :)
nicely explained thanks..........
@9:20 Slight correction, The time complexity is O(2n) = O(n) because the array is traversed twice, once for squaring all the numbers and once for comparing for placement in new array.
Also if there is a requirement for something similar in API terms then there can be a solution where you do not modify the original input and just use a single array. Because at any time you are only comparing 2 squares you need not create a separate array of squares, you can store left pointer, right pointer, left square and right square in 4 variables and then do the iteration and store it in the new array directly.
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
return_array = [0] * len(A)
write_pointer = len(A) - 1
left_read_pointer = 0
right_read_pointer = len(A) - 1
left_square = A[left_read_pointer] ** 2
right_square = A[right_read_pointer] ** 2
while write_pointer >= 0:
if left_square > right_square:
return_array[write_pointer] = left_square
left_read_pointer += 1
left_square = A[left_read_pointer] ** 2
else:
return_array[write_pointer] = right_square
right_read_pointer -= 1
right_square = A[right_read_pointer] ** 2
write_pointer -= 1
return return_array
we doint consider constants in O notation...so O(kn)=O(n)
can you do this ques in O(1) space complexity without using any extra space
awesome bro. ♥️
In the else loop in comment //increment tail pointer . I can't understand u do it by mistake or it's something else 😕
So sorry for that...it should have been "//decrement tail pointer"
@@nikoo28 no problem bhayia 👍
when you are getting the square of each integer in the array, could you also use the Math.pow method?
yes, you can
thank u
We can ignore the traversal of input array to square the integers.
int n = nums.length;
int[] result = new int[n];
int head = 0;
int tail = n - 1;
for (int i = n - 1; i >= 0; i--) {
int headSquare = nums[head] * nums[head];
int tailSquare = nums[tail] * nums[tail];
if (headSquare > tailSquare) {
result[i] = headSquare;
head++;
} else {
result[i] = tailSquare;
tail--;
}
}
return result;
can we do it in O(1) space
can we solve this without using extra space ?
you need the result array to store your squares. An inplace solution isn't possible
sir can you also provide code of it
Did you check the link in the description?
Can it also be done without taking extra array to copy.
You could modify the initial array by using a temporary local variable to store values and then modify the initial array. Depends on your requirements.
@@araneuskyuro but even if u use temp variable it can store one value at a time. so i think we cannot escape the extra space thing.
@@harshvardhansankpal716 Oh right. Welp, sorry for the misinformation.
❤💯
please launch your dsa course....
I will do that eventually, working on 1 video at a time and building concepts.