instead of comparing squares of both nums[L] and nums[R], we can compare abs(nums[L]) and abs(nums[R]) because squaring takes more time than absolute. Or we can store and reuse the squared values.
@@NeetCode great video! however I think you miscategorized this as a "Binary Search" problem in Leetcode categories, it should prob be an Array or Sliding Window problem
@@orangefield2308 You can solve it using binary search actually. Using binary Search, find the minimum positive value possible and then move towards its left and right. Then keep checking which gives a smaller square and add it to the answer array. Then move backwards/leftwards if it was the negative value or forwards/rightwards if it was a positive value. It's obviously more complex than the above solution but since it was in the binary search section, I tried solving it like this. Time complexity will be O(logN) + O(N) which is O(N)
Reversing the array takes time, why not create a prefilled array with dummy values and keep updating from the last element while checking? Also store the squared numbers in variables so you only count it once(i don't think it's that important but you can see the difference) Great video as always!
I used your explanation and wrote a similar code without the need to reverse the array: def sortedSquared(array): left, right = 0, len(array) - 1 squares = [] for num in array: far_left = array[left] far_right = array[right] # alway insert the biggest in the first position if abs(far_right) >= abs(far_left): squares.insert(0, far_right ** 2) right = right - 1 else: squares.insert(0, far_left ** 2) left = left + 1 return squares I hope it also helps
Aren't you adding one more O(n) to the complexity while reversing the array in the last step? You could introduce the third pointer (equal to the length of the array) and insert the value at the result array from the end. This way you can ditch the reversing.
My solution was 75 lines long. I don't know i just wrote the solution considering all the edge cases and not thinking of finding the largest number and finding the res array. Thanks for the explanation neetcode.
in case of usage: if abs(A[L])>=abs(A[R]):, you can increase your performance on 20 %/ just FYI Runtime: 242 ms, faster than 62.87% class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: A = nums if not A: return A L,R, res = 0,len(A)-1,[] while L=abs(A[R]): res.append(A[L]**2) L+=1 else: res.append(A[R]**2) R-=1 return res[::-1]
idk if its allowed , but leetcode accepted it. beats 100% . class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: return sorted(list(map(lambda x: x * x, nums)))
I used a stack in my solution and it is pretty efficient: class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: stack = [] idx = 0 for val in nums: valSqr = val * val while stack and stack[-1] < valSqr: nums[idx] = stack.pop() idx += 1
Improved your solution a bit, give it a check . I used "Insert" rather than "append". class Solution(object): def sortedSquares(self, nums): """ :type nums: List[int] :rtype: List[int] """ res = [] l,r = 0,len(nums)-1 while l nums[r]*nums[r]: res.insert(0,nums[l]*nums[l]) l+=1 else: res.insert(0,nums[r]*nums[r]) r-=1 return res
My question to you is this: if you have a cs degree and you've never thought of code this way, how would you even begin to think that you would build an external list and then reverse it? That would have never ever occurred to me.
if you run a few example arrays you'll see the biggest values are at the ends of the array and the solution wants them in ascending order. thats how i came to this solution at least... running examples on any problem can give you lots of intuition that just looking/thinking might not
because of the way we are utilizing two pointers. We start by looking at the extreme values from both side of the list which happen to be the highest numbers (ignoring the signs), and approach towards the lower numbers (numbers that are closer to 0) as we finish adding the higher numbers to the output list. So we end up with a list where higher numbers are appended first and lower numbers are appended last
No need to reverse array; Java solution: class Solution { public int[] sortedSquares(int[] nums) { int[] res = new int[nums.length]; int i = nums.length - 1, left = 0, right = i; while (left
Instead of looping through the left and right pointers and then looping again to reverse, you can just loop through the result array in decreasing order, updating the right and left pointers. Example: class Solution: def sortedSquares(self, nums): length = len(nums) result = [0] * length left, right = 0, length - 1 for i in range(length - 1, -1, -1): if abs(nums[left]) > abs(nums[right]): result[i] = nums[left] * nums[left] left += 1 else: result[i] = nums[right] * nums[right] right -= 1 return result
don't know if this is a good question to test a candidate. I can see an IQ 300 candidate, superb programmer, if he didn't see this question before, he may not reach this optimal answer, versus a person who sucked at programmer but have seen this problem before, will start with this, "oh two pointers from both sides" method and get hired? That's totally unjust
Java solution public static int[] makeSquares(int[] arr) { int n = arr.length; int[] squares = new int[n]; int highestSquareIdx = n - 1; int left = 0, right = n - 1; while (left rightSquare) { squares[highestSquareIdx--] = leftSquare; left++; } else { squares[highestSquareIdx--] = rightSquare; right--; } } return squares; }
instead of comparing squares of both nums[L] and nums[R], we can compare abs(nums[L]) and abs(nums[R]) because squaring takes more time than absolute. Or we can store and reuse the squared values.
Good point!
@@NeetCode great video! however I think you miscategorized this as a "Binary Search" problem in Leetcode categories, it should prob be an Array or Sliding Window problem
@@orangefield2308 You can solve it using binary search actually. Using binary Search, find the minimum positive value possible and then move towards its left and right. Then keep checking which gives a smaller square and add it to the answer array. Then move backwards/leftwards if it was the negative value or forwards/rightwards if it was a positive value.
It's obviously more complex than the above solution but since it was in the binary search section, I tried solving it like this. Time complexity will be O(logN) + O(N) which is O(N)
Reversing the array takes time, why not create a prefilled array with dummy values and keep updating from the last element while checking?
Also store the squared numbers in variables so you only count it once(i don't think it's that important but you can see the difference)
Great video as always!
For that we need length of input array
Still O(n)...
@@adventurer2395 space complexity will be different. prob doesnt matter in an interview but still good to know in case they ask to optimize space
yep another pointer pos pointing at end does the trick .. also result array will be size of the original ..
You can also insert at 0
output.insert(0, nums[p] * nums[p])
I used your explanation and wrote a similar code without the need to reverse the array:
def sortedSquared(array):
left, right = 0, len(array) - 1
squares = []
for num in array:
far_left = array[left]
far_right = array[right]
# alway insert the biggest in the first position
if abs(far_right) >= abs(far_left):
squares.insert(0, far_right ** 2)
right = right - 1
else:
squares.insert(0, far_left ** 2)
left = left + 1
return squares
I hope it also helps
that finding the maximum instead of minimum was genius. It made the code so much cleaner
Aren't you adding one more O(n) to the complexity while reversing the array in the last step? You could introduce the third pointer (equal to the length of the array) and insert the value at the result array from the end. This way you can ditch the reversing.
hey @neetcode, enjoyed this problem and your explanation but why is this tagged as binary search?
My solution was 75 lines long. I don't know i just wrote the solution considering all the edge cases and not thinking of finding the largest number and finding the res array. Thanks for the explanation neetcode.
Two pointer jutsu
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l = 0
r = len(nums) - 1
index = len(nums) - 1
res = [1] * len(nums)
while l abs(nums[r]):
res[index] = nums[l] **2
l+=1
else:
res[index] = nums[r] **2
r-=1
index-=1
return res
Nice👍
in case of usage: if abs(A[L])>=abs(A[R]):, you can increase your performance on 20 %/ just FYI
Runtime: 242 ms, faster than 62.87%
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
A = nums
if not A: return A
L,R, res = 0,len(A)-1,[]
while L=abs(A[R]):
res.append(A[L]**2)
L+=1
else:
res.append(A[R]**2)
R-=1
return res[::-1]
Hi, this is in wrong section on neetcode website, it should be two pointers problem not binary search
idk if its allowed , but leetcode accepted it. beats 100% .
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted(list(map(lambda x: x * x, nums)))
Hey,
you accedintly put this video under Binary Search category in your website.
it suppose to be under Two Pointers.
Interesting I was doing this question yesterday and you released a video today lol
Serendipity😎
Best channel
Wow! Your solution just took away my heart. It is beautiful!
I wonder why did you put this problem under Binary Search Category ?
I solved my first question with correct optimal solution without seeing the coding part. Thank you neetcode
U should make a Python DSA course
I used a stack in my solution and it is pretty efficient:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
stack = []
idx = 0
for val in nums:
valSqr = val * val
while stack and stack[-1] < valSqr:
nums[idx] = stack.pop()
idx += 1
stack.append(valSqr)
while stack:
nums[idx] = stack.pop()
idx += 1
return nums
Improved your solution a bit, give it a check . I used "Insert" rather than "append".
class Solution(object):
def sortedSquares(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = []
l,r = 0,len(nums)-1
while l nums[r]*nums[r]:
res.insert(0,nums[l]*nums[l])
l+=1
else:
res.insert(0,nums[r]*nums[r])
r-=1
return res
this is O(n^2), insertion implicitly moves every element in the list to the right every time.
My question to you is this: if you have a cs degree and you've never thought of code this way, how would you even begin to think that you would build an external list and then reverse it? That would have never ever occurred to me.
if you run a few example arrays you'll see the biggest values are at the ends of the array and the solution wants them in ascending order. thats how i came to this solution at least... running examples on any problem can give you lots of intuition that just looking/thinking might not
This was in the binary search section of NC All... I thought I was going crazy haha
You can use unshift for javascript instead of reversing it
Instead of doing the reverse at the end we can just add the numbers to the beginning of the array instead of appending it.
How about if the array contains all negative or positive numbers?
did you find the answer?
Hey thank you so much for the amazing content. I had a question why is the output array built in reverse order rather than from the start/beginning?
because of the way we are utilizing two pointers. We start by looking at the extreme values from both side of the list which happen to be the highest numbers (ignoring the signs), and approach towards the lower numbers (numbers that are closer to 0) as we finish adding the higher numbers to the output list. So we end up with a list where higher numbers are appended first and lower numbers are appended last
If you have to sort in the end after all. Why not just return sorted([ n ** 2 for n in nums]) ?
he reversed the array, not sorted
No need to reverse array; Java solution:
class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int i = nums.length - 1, left = 0, right = i;
while (left
@NeetCode Can we do this in place? thanks
What about if the nums are [-5,-4, -2,-1]?
Ur the GOAT
is there a way to do this in-place? without using a new array?
why is this under Binary search its actually 2 pointers from neetcode sheet
thank you sir
Why is this in binary search rather than two pointers?
You need to search for the first non 0 element which should be done using b search
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
ans = []
i, j = 0, len(nums)-1
while j >= i:
if abs(nums[i]) > abs(nums[j]):
ans.append(nums[i]**2)
i += 1
else:
ans.append(nums[j]**2)
j -= 1
return ans[::-1]
Is a list compreshion not good in this case?
like sorted([x**2 for x in nums])
oh nvm nlog(n)
Hey @NeetCode this problem is in the binary search topic of the NeetCode All on your site. Shouldn't it be in two pointers instead?
I used memo:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
p, q = 0, len(nums) - 1
output = []
memo = {} # memoization
while p abs(nums[q]):
memo[nums[p]] = nums[p] * nums[p]
output.insert(0, memo[nums[p]])
p += 1
else:
memo[nums[q]] = nums[q] * nums[q]
output.insert(0, memo[nums[q]])
q -= 1
return output
Sir can you pls do a video on Average of numbers inside Radius K. Thanks😃
nice explanation , how you are so good
Please move that into the two pointer section
Instead of looping through the left and right pointers and then looping again to reverse, you can just loop through the result array in decreasing order, updating the right and left pointers. Example:
class Solution:
def sortedSquares(self, nums):
length = len(nums)
result = [0] * length
left, right = 0, length - 1
for i in range(length - 1, -1, -1):
if abs(nums[left]) > abs(nums[right]):
result[i] = nums[left] * nums[left]
left += 1
else:
result[i] = nums[right] * nums[right]
right -= 1
return result
wow that was tricky
don't know if this is a good question to test a candidate. I can see an IQ 300 candidate, superb programmer, if he didn't see this question before, he may not reach this optimal answer, versus a person who sucked at programmer but have seen this problem before, will start with this, "oh two pointers from both sides" method and get hired? That's totally unjust
can someone explain line 5 of his code
he basically initialized his left and right pointer to index 0 and last index. SO that we can check both ends of the array at the same time
💯❤
I'm so dumb
Java solution
public static int[] makeSquares(int[] arr) {
int n = arr.length;
int[] squares = new int[n];
int highestSquareIdx = n - 1;
int left = 0, right = n - 1;
while (left rightSquare) {
squares[highestSquareIdx--] = leftSquare;
left++;
} else {
squares[highestSquareIdx--] = rightSquare;
right--;
}
}
return squares;
}
this still use O(n) extra space