Just aced my interview with Amazon today (got an email within minutes after the interview that I was selected to move on to the final panel interview). Thanks so much for these videos, def helped get me in the right mindset and made the coding portion of the interview a breeze.
Yup Was the first idea I had as well. Allocate 2x input. Loop over the input and store the negative numbers in the first list and positive in the 2nd. Memory consumption is larger for this case. But end step is just merge the two lists. Original list could be used for this to maintain 3N memory complexity and 2N run time.
Nick, you are the best! I’m a software developer over 7 years and I’d watched so many empty talks and crappy solutions from other people for data structure problems. You teach the technique to solve a problem rather than useless looping, mapping ext... Thanks man! Keep up the great work!
I am currently going through the software developer hiring process. I have lots of feelings of imposter syndrome and doubt. However, your solutions and thought process are fantastic and allow me to relate to you and help me get over my anxiety. This has been such a help to gain confidence. You rock I would love for you to bring these back wherever you are in life right now. Thanks man
I love to watch your tutorials. It gives me a sense of relief each time I watch it. Not to mention that they are extremely helpful. I’m preparing to work at faang and every morning I come to this channel as a pilgrim
Nice one. If you search for a Google interview question(from Google itself), this version is also shown there(find the two values in an array that add up to a given sum, in linear time). Note that this solution only works if the values in the input are sorted. If they are not then you cannot guarantee that the pointers are going to be pointing to the smallest/largest values.
You could modify the space complexity by keeping track of the current number as a variable and modifying the input array if the solution required lowest possible space complexity as well.
Yours is better but I'll say what my idea was. I was thinking binary search the first positive number and save the index. Then I would compare the negative values on the left vs the positive one on the right and same idea as yours but constructing the output from smallest to biggest. Once either one of the pointer reached an end of the input array just fill in the squares of the side that wasn't done yet. Searching: log(n) Construction: n Run time: log(n)+n = O(n) What I said, yours is truly linear but I just wanted to share my idea. Great type of videos, I like them. Keep the good work and explanation method, mentioning the trivial solution is always a good starting point, I like that about the way you solve these
I've literally approached that the same way. Binary search for the index of the first positive value or smallest negative (in case there were no positive ones), and maintain two pointers; right for the found index, and left for right-1. Then just simply comparing whether left or right should be pushed first into a newly created array.
@@GustavoCevalhos in the given approach you only need to perform a binary search once. Just to find a starting index. The comparison itself runs in the linear time. Hence it's O(n + logn) => O(n) overall
Actually u do one extra calculation which is abs() , couse u can just square both compare them put larger in output array and put smallest in var to compare with the next one from other side
Use two pointers ... One at the end of the negative half ( move towards right) One at the starting of the positive half and merge the two halves ( neglect the negative sign while merging moves to left ) Place the merged ones in output array Later square the merge array or do it while merging Return it back Voila O(n)
Great lesson Nick. Another way to optimize this code even better is to loop through the array halfway. This will still give us O(n) for both time and space complexity. Below is my solution (Code in JavaScript btw): function sortedSquareArr(A) { const sortedArr = new Array(); let first = 0; let last = A.length - 1; let i = last; // O(n) - Time complexity // O(n) - Space complexity while(first
This is a nice Coding Interview Question. I had an interview at Facebook and I failed it because I didn't know O(n) algorithm for a much complex problem.
Yeah. I was so confused at the beginning because I couldnt think of a solution that would be better than O(N log n) because in every case you still have to sort the numbers. The problems got so much easier with the realization that the numbers are sorted...
If the input isn’t sorted there is no solution better than O(nlog(n)) , it is easy to prove: Assume that there is a solution in o(nlog(n))(way better than O(nlog(n))) so I can sort any array in this time complexity by first taking the sqrt of any element then running the solution for this problem , but we know that you can’t sort arrays in better than O(nlog(n)), contradiction. Q.E.D.
I'm happy because I managed to figure it out, I once saw somewhat simmilar problem, where you're given two sorted arrays of n size, and you want to find a pair of numbers x and y, one from each array, such that x+y=m. You would put one pointer i on the start of first array and j on the end of second one, and if sum>m then decrease j, if sum
This optimized approach is only possible if input array starts with highest negative and end with highest positive number, ie, the input is sorted either in increasing or decreasing order.
We just need the merge from mergesort between the positive side of the array and the absolute value of the negative side in reverse, and square each element.
please don’t ever stop making these videos. These help so much with learning and you explain everything with such good detail, I can follow along. Thank you!!!
I came up with this before watching your solution: def squared_sorted_array(l): l=[abs(x) for x in l] n=len(l) o=[0]*n for i in range(n): o[i]=min(l) del l[l.index(min(l))] l=[x**2 for x in o] return l But, initially I thought of the same process that you used, but I thought it might be messy so discarded that.
Nice. This wouldn't improve the complexity, but you could improve performance by simply draining the remaining numbers once you have hit the boundary rather than continuing to check each number.
If you order the list using absolute values, yo have the right order, example: [-6, -4, 1, 2, 3, 4, 5] => [1, 2, 3, 4, 5, 6] => [1, 4, 9, 16, 25, 36] it takes o(n)
int numbers[] = {-3,-4,1,2,3,1}; algorithm not working for this input .Works only if the largest element is at the left and not somewhere else. I think you also have to check the last number with any new greater element and then swap them both.
You could just look for the 1 positive number and place a pointer on the positive side and one on the negative. Now just sq the values on either side see compare which is smaller and add that to the op array
For loop of the array which iterated through the size of the array, find number closest to zero, and work backwards. Keep track of lowest, highest, and previously sorted number to make it quicker, then, once sorted, a while or for loop to square each element in the array.
Small tweak of merge sort is best. Find the first negative and first positive. Pad output array, start stepping positive/negative side, insert the smallest. This method avoids using the Math.Abs() and will be faster. O(N).
My solution is finding the first positive value using binary search, splitting negative part from positive part, square both parts and merge them taking into account that the negative part is now "reversely sorted". Divide and conquer style!
My first thought was: Those negative values are the ones making this difficult, so let's get rid of them. And in the end, the worst-case complexity is still N (more precisely logn + 3N)
I think on 6th line of second optimised code there should be Math.abs [right] as well, because as you said array full of negative numbers is a valid input.
Great solution. I would also add that if all the input numbers are positive, this approach can be simplified and done in-place, thus reducing the space complexity to O(1). That’s because when they are all positive, you know squaring them will not change their sorted order. Simply check the first index of your input array, and if its value is positive, square all the numbers in-place. You could also do something similar to save space if all the input numbers are negative, since you know their squares will be in reverse sorted order.
Nick: Simple idea is to square the array then sort it, but it isn't efficient because sorting is n*log(n) at best, we are aiming for linear time complexity Every other python "expert" in the comments: lemme write one liner to show how smart I am using built in sort method
just looking at 6:55, I paused and opened pycharm. I tried once, didn't work. Debugged in two places and it worked!! thanks nick for making these videos.
This algorithm will work if the input array is sorted. We can use modified counting sort algorithm to solve the problem for unsorted input array. It'll take linear time. Maybe I'm wrong.
If there's an O(n) solution for an unsorted array, we can input some positive integers, then apply this algorithm and sqrt each member, in output we'll get an original sorted array and it will work for O(n), but sorting is actually O(n*log n)
@@aertyty3900, count sort and redix sort take linear time (it seems linear) and in required output all numbers are positive. If we take square for each element in array, it'll be done in O(n) and then apply one of these sorting algorithms. It's my thought and I'm not professional programmer.
def sortedSquared(arr: [int]) -> [int]: squared = list(map(lambda x: x*x, arr)) for i in range(len(squared)-1): mini = i for j in range(i+1, len(squared)): if squared[j] < squared[mini]: mini = j t = squared[mini] squared[mini] = squared[i] squared[i] = t return squared
There is a way around the n log n complexity of sorting: the problem explicitly bounds the range of inputs, so you can use a linear-time radio sort. It would be dumb, but you could do it.
After hearing the question, I was like loop through and square, are you serious? You call that a coding interview, blah blah blah, then 2 minutes in... oh
If both left and right values are equal, we can increment left and decrement right i and can sort the values in result array ,except when they are equal
I would argue in favor of the square everything then sort it method. It is O(n * log(n)), which is not slow as you said. Also our n is less than 10000, so when this is not called in a hot loop millions of times readability wins over shaving of one log(n) of the time complexity.
What Nick is doing has time complexity O(n)/linear and he said it's the best way to do it, what if we square numbers of array and then apply MERGE SORT that has time complexity O(nlog(n)) in all the best to worst case time complexity scenarios (we would need left and right(start and end) values in array for merge sort). Which one would be good way to solve the problem please tell me, I'm confused? P.S. Nick's solution and mindset towards problem was absolutely amazing! :)
Even though i understand that your algorithm is clearer to read, but I must point out two things: - you are calling Math.abs each iteration, which is not ideal. you'll have to square it anyway, calling abs is 100% unnecessary. - you aren't really taking advantage of having a sorted array properly. After all the negative (or positive) numbers are "consumed" you know for sure that you can just consume all the leftover numbers in order. pros of mine: - takes less if()s - has no dependency - ifs are faster to evaluate cons of mine: - harder to reaad - took me a bit more time, which is obviously not ideal in an interview int[] sortedSquaredArray(int[] array) { int i = 0; int length = array.length; //square negative ones first for (; (i < length) && (array[i] < 0); i++) { //by naming the arrayaccess value, you don't need to access the array 2 times, only once int val = array[i]; array[i] = val * val; } int[] result = new int[length]; int l = 0; int left = i-1; int right = i; //i'm iterating from the inside, not the outside like you do. while (left >= 0 && right < length) { int leftValue = array[left]; //by naming the arrayaccess value, you don't need to access the array 2 times, only once int rightValue = array[right]; int rightSquaredValue = rightValue * rightValue; if (leftValue < rightSquaredValue) { result[l++] = leftValue; left--; } else { result[l++] = rightSquaredValue; right++; } } //when we get to the end of the minuses or the pluses, we might have a bunch of numbers left. //these numbers are all sorted they need 0 checking, they just need to be added to the result array. if(left >= 0){ for (; left >= 0; left--) { result[l++] = array[left]; } return result; } for (; right < length; right++) { int val = array[right]; result[l++] = val * val; } return result; } please notice me :D
Guys, don't you see that stuff like this gets more and more complicated and thus less maintainable? Would you like to hunt for a bug in code like this? (Do you have experience doing this, especially if this isn't your own code originally?) One of the main goals in modern software development isn't the fanciest most optimized version of an algorithm but to have *readable* code. Code which the next maintainer will understand as fast as possible. It's alright to bring an algorithms from N log N down to N if you really have large input. If this is going to save 20 seconds of runtime within the next four years, it is probably not a good idea to even optimize for this. But any optimization beyond this (as in the post above) needs an enormously good reasoning to be justified. »This is even a little faster« is not such a good reasoning ;-)
@@alfeberlin Then again, this is really easy to test, as you just have to compare its output to the sort(squared_arr) version on random arrays. So you could become pretty confident that the algorithm does what its supposed to do.
@@alfeberlin Honestly, if you want readable code you only do sorting by hand if it is absolutely a must for performance. I'd just .stream().map(...).sorted().collect it. if i really wanted to make it performant, i would do sth like this: Stream negatives = .stream().takeWhile(i < 0).map(...) then Stream positives = .stream().reversed().takeWhile(i >= 0).map(...) and use something like negatives.mergeSorted(positives).reversed() and there you go, 3 lines of code, and even newbies can understand it. Google's coding challenges are stupid, it's much harder to model problems properly than to come up with fancy algorithms, and still they ask you to come up with algorithms that you can argue a lot about whether it's good or not.
just to be clear: + before the last step the indices are always equal (because the total number of processed elements is len(array) - 1 + hence it doesn't really matter for the last step which index is advanced; + if all elements are negative, the left pointer always advances because the absolute value of a negative is greater than any negative number (including the first) + if all elements are positive, the right pointer always advances because the left pointer points to the element with the smallest absolute value + the same reasoning applies when the negatives run out before the positives vs the positives run out before the negatives + if the order is negative, positive, negative, positive... or positive, negative, positive, negative -- then the two pointers meet in the middle, and which pointer advances last depends on the parity of the length and which element came first + elements with equal absolute values are treated as elements from the "right" side (they fall in the else clause)
@Nick White it may have been more intuitive (though that's debatable) to condition the loop on equality of the indices and then just take the final element. But this is OK too, because on each loop step each index is changed by one, so the sum of the distances traveled by each index equals the number of iterations.
2nd method will be faster, it's only taking 1 parse through the array, so N. In first case we were going through the array to square each element, so the time complexity is already N + sorting time
There's no need, he gave the time complexity. The O(n^2) solution can on occasion be faster than O(n), so execution time doesn't tell you much unless you run it on a sufficient number of inputs.
Just one minor add on to the comparison, we can replace the call to Math.abs by adding the two numbers together and return right on positive/left on negative.
Nice! But in practice there is no difference in runing time. With 10000 integer both method finished in 1ms. Perhaps running with 100 000 or more ... Do not forget: calling Math.abs() and if()-s has price too.
watched this video, went to solve the question, proceeds to forget about the for loop and does it with while loop, now i have 2 solutions. So the algorithm explanation was well done.
Niko Ursol If we are really nailing it to that detail, you’ll square each number twice by the way you describe. Better just compare the sum of two numbers with zero to get the optimal solution timewise.
@@MY-bc3qq why would you have to square it twice? It's only one time thing - before you comparing them, and than just merge stuff together as you go. You have to copy each int twice tho, but its cheap. (by copy twice i mean copy in buff to square them, and then emplace (copy again to resulting list) in the end even squaring whole list, grouping them together, reversing one half, merging them would be in O(n)
What if you go through the list, if you see a negative int, square it and throw it in a max heap (or max priority queue, or I'm assuming a normal queue would work also since array is sorted so negative ints thrown into the queue will be smallest square at the back biggest square at the front), If you see a positive int then square it? check max heap and keep popping until max element is less than your positive int, then just keep going, throwing elements in whatever new list you initialized at the beginning Should be O(n) if I'm not missing anything
Though it is not written here,I have to assume that optimal time complexity is what the interviewers are seeking??/And should I think about optiimizing my time complexity or spae complexity,when nothing about them are written here???
# Python Solution for the Equivalent Java Logic def sortedSquareArray(nums) : n = len(nums) output = [0]*n
left = 0 right = n-1
for i in range(n)[::-1] : if abs(nums[left]) < abs(nums[right]) : output[i] = nums[right]*nums[right] right = right - 1 else : output[i] = nums[left]*nums[left] left = left + 1 return output
solution doesn't work for all negative numbers - you need to do abs of right hand side too , and left and right pointers cross each other as there's no check for them "meeting"
I think you can add this into top of your methode to make it more efficent. if( array[left]>0){result[i]=array[right]*array[right];right--;} Because if array[left] if bigger than zero it is already sorted right ?
6 lines in python: def sortedarray(array): new_array = [] for number in array: new_array.append(number**2) return sorted(new_array) print(sortedarray([-7,-3,-1,4,8,12]))
or better solution: def sortedarray(array): new_array = [] for number in array: new_array.append(number**2) for i in range(len(new_array)): for j in range(len(new_array)): if new_array[i] < new_array[j]: t = new_array[i] new_array[i] = new_array[j] new_array[j] = t return new_array print(sortedarray([-4,-4,-2,6,7]))
Before the video: I’d use another array and I would go through the original array, square the element and use a binary search to find the location that the element should go and then place it: insertion sort. Edit: didn’t realize the original array would be sorted
Python answer: def selectionSort(l): for i in range(len(l)-1): minimum = i for j in range(i, len(l)): if l[j] < l[minimum]: minimum = j if minimum != i: temp = l[i] l[i] = l[minimum] l[minimum] = temp return l def sortedSquaredArray(arr): arr = [i**2 for i in arr] arr = selectionSort(arr) return arr
What if we use sets to store the data. It will automatically sort as the data will be entered. (No number is repeating).. What will be its time complexity?
Theres a similar way still linear (2n tops) that I believe in real world could be faster on a large data set with all or mostly positive / negative inputs. If you can first find if/where the first positive or negative meets you could possibly perform some optimisations. So you're still comparing iterators but instead of working inwards from each end you work outwards from the midpoint. The solution in video is definitely better for general cases but if you know roughly what your inputs are like you can usually make optimisations. I believe this is something you learn with real world experience as 2 linear solutions can have vastly different runtimes.. this is one thing i dont like about these kind of questions.. yes it demonstrates knowledge and understanding of algorithms and datasets but in actual coding the problems are rarely like this and some calculation in a linear solution can work out slower than a n log n solution (its unlikely but possible). Profiling should always be preferred to simply relying on your time or data complexity.
I ended up checking if they were equal (having a -12 and a +12) so I had an extra conditional statement but checking the absolute value of the left value to the right value is actually kind of elegant...didnt dawn on me to do that
put another condition when left pointer iterates all the negative and we're only left with positive numbers just insert all the positive numbers as the given sequence btw great video
i thought of travelling to 1st positive number and then use 2 pointers on right and left list just like in video, but i guess that travelling is unnecessary now
Is there ever a case where you would need to have math.abs for the right pointer as well. Such as, if there are more negative numbers than positive and the right pointer hits a negative.
I would complain that they didn't specify how the input array would be sorted. Also, sorted means arranged in a certain way, so you can just copy the input array, square each value, and say it is sorted by input array matching order. That is actually legitimate. The specifications of the problem are unclear and I would argue that. Sorted, for example, could mean all single digit numbers followed by all non single digit numbers. It does NOT always mean nonascending or nondescending. They didn't specify how they wanted the output sorted so ANY pattern is acceptable, as long as it is well defined (input array element position matching is well defined = unambiguous). You didn't specify if the examples you presented here came from you or came from FB, so I cannot assume they were from FB as part of the problem. So my solution is simpler and faster than the one presented here so I "win". So to be clear, if the input array was [-7, -3, -1, 4, 8, 12], my output (sorted) array would be [49, 9, 1, 16, 64, 144]. It is a valid solution based on the definition of the word sorted. Another output sorting could be [1, 9, 49, 144, 64, 16] which is single digit results first followed by non single digit results. Just to be clear, sorting is basically the opposite of random. Random means no order assigned (intentionally), but sorted means there is some order given to something (but not necessarily nonascending or nondescending). I can start work on Monday FB.
Just aced my interview with Amazon today (got an email within minutes after the interview that I was selected to move on to the final panel interview). Thanks so much for these videos, def helped get me in the right mindset and made the coding portion of the interview a breeze.
Did you get the job? If so congratulations!
bro party !!!!
Hi
This is essentially the final stages of a merge sort, with one list starting on the left, and the other starting on the right.
that's interesting
Yup
Was the first idea I had as well.
Allocate 2x input.
Loop over the input and store the negative numbers in the first list and positive in the 2nd. Memory consumption is larger for this case. But end step is just merge the two lists. Original list could be used for this to maintain 3N memory complexity and 2N run time.
youtube algorithm picks up another algo video
David Hahn sounds like like recursion right there lmao
@@tannerbarcelos6880 its a pointer
@@tannerbarcelos6880
yeah, it's like like like recursion there
yup
CanAlgolism
Nick, you are the best!
I’m a software developer over 7 years and I’d watched so many empty talks and crappy solutions from other people for data structure problems. You teach the technique to solve a problem rather than useless looping, mapping ext...
Thanks man! Keep up the great work!
And all of my friends accused my teachers, saying that we would never use Math as an adult. Because my computer will be my calculator...
I could binge 4 seasons of this
same
Haha! Facts
I am currently going through the software developer hiring process. I have lots of feelings of imposter syndrome and doubt. However, your solutions and thought process are fantastic and allow me to relate to you and help me get over my anxiety. This has been such a help to gain confidence. You rock I would love for you to bring these back wherever you are in life right now. Thanks man
I love to watch your tutorials. It gives me a sense of relief each time I watch it.
Not to mention that they are extremely helpful.
I’m preparing to work at faang and every morning I come to this channel as a pilgrim
Nice one. If you search for a Google interview question(from Google itself), this version is also shown there(find the two values in an array that add up to a given sum, in linear time).
Note that this solution only works if the values in the input are sorted. If they are not then you cannot guarantee that the pointers are going to be pointing to the smallest/largest values.
You could modify the space complexity by keeping track of the current number as a variable and modifying the input array if the solution required lowest possible space complexity as well.
Yours is better but I'll say what my idea was.
I was thinking binary search the first positive number and save the index. Then I would compare the negative values on the left vs the positive one on the right and same idea as yours but constructing the output from smallest to biggest. Once either one of the pointer reached an end of the input array just fill in the squares of the side that wasn't done yet.
Searching: log(n)
Construction: n
Run time: log(n)+n = O(n)
What I said, yours is truly linear but I just wanted to share my idea.
Great type of videos, I like them. Keep the good work and explanation method, mentioning the trivial solution is always a good starting point, I like that about the way you solve these
I've literally approached that the same way. Binary search for the index of the first positive value or smallest negative (in case there were no positive ones), and maintain two pointers; right for the found index, and left for right-1. Then just simply comparing whether left or right should be pushed first into a newly created array.
Basically we are doing one iteration of merge sort at the end:
1. split list into two sorted halves
2. merge them
-- I like this solution better.
Hi!
You would be searching N times in the input, which would lead to N*Lg(N) overall time complexity.
@@GustavoCevalhos in the given approach you only need to perform a binary search once. Just to find a starting index. The comparison itself runs in the linear time. Hence it's O(n + logn) => O(n) overall
@@brunokawka True! I misread the explanation, you are correct :)
Actually u do one extra calculation which is abs() , couse u can just square both compare them put larger in output array and put smallest in var to compare with the next one from other side
Use two pointers ...
One at the end of the negative half ( move towards right)
One at the starting of the positive half and merge the two halves ( neglect the negative sign while merging moves to left )
Place the merged ones in output array
Later square the merge array or do it while merging
Return it back
Voila O(n)
Great lesson Nick. Another way to optimize this code even better is to loop through the array halfway. This will still give us O(n) for both time and space complexity. Below is my solution (Code in JavaScript btw):
function sortedSquareArr(A) {
const sortedArr = new Array();
let first = 0;
let last = A.length - 1;
let i = last;
// O(n) - Time complexity
// O(n) - Space complexity
while(first
This is a nice Coding Interview Question. I had an interview at Facebook and I failed it because I didn't know O(n) algorithm for a much complex problem.
The whole time I thought the input wouldn't be sorted.
Yeah. I was so confused at the beginning because I couldnt think of a solution that would be better than O(N log n) because in every case you still have to sort the numbers. The problems got so much easier with the realization that the numbers are sorted...
Yeah
If the input isn’t sorted there is no solution better than O(nlog(n)) , it is easy to prove:
Assume that there is a solution in o(nlog(n))(way better than O(nlog(n))) so I can sort any array in this time complexity by first taking the sqrt of any element then running the solution for this problem , but we know that you can’t sort arrays in better than O(nlog(n)), contradiction. Q.E.D.
@@iradnuriel9087 Given that the range of input is between -10000 and 10000, you can use counting sort for linear time sort.
@@arnabmitra08 that is exactly what came to my mind
It's much simpler than this pointer stuff anyway.
I'm happy because I managed to figure it out, I once saw somewhat simmilar problem, where you're given two sorted arrays of n size, and you want to find a pair of numbers x and y, one from each array, such that x+y=m. You would put one pointer i on the start of first array and j on the end of second one, and if sum>m then decrease j, if sum
This optimized approach is only possible if input array starts with highest negative and end with highest positive number, ie, the input is sorted either in increasing or decreasing order.
We just need the merge from mergesort between the positive side of the array and the absolute value of the negative side in reverse, and square each element.
please don’t ever stop making these videos. These help so much with learning and you explain everything with such good detail, I can follow along. Thank you!!!
Second approach will not for input (1,-4,7,-2,5,3,-6). I mean, if elements(abs values) are not arranged in decreasing and increasing order.
hey bro...u r doing gud .... keep updating by these type of questions.......
I came up with this before watching your solution:
def squared_sorted_array(l):
l=[abs(x) for x in l]
n=len(l)
o=[0]*n
for i in range(n):
o[i]=min(l)
del l[l.index(min(l))]
l=[x**2 for x in o]
return l
But, initially I thought of the same process that you used, but I thought it might be messy so discarded that.
Nice. This wouldn't improve the complexity, but you could improve performance by simply draining the remaining numbers once you have hit the boundary rather than continuing to check each number.
If you order the list using absolute values, yo have the right order, example:
[-6, -4, 1, 2, 3, 4, 5] => [1, 2, 3, 4, 5, 6] => [1, 4, 9, 16, 25, 36]
it takes o(n)
If you need a handy one-liner in java:
int[] squaredArray(int[] array) {
return Arrays.stream(array).map(i -> i * i).sorted().toArray();
}
Ikr
int numbers[] = {-3,-4,1,2,3,1}; algorithm not working for this input .Works only if the largest element is at the left and not somewhere else. I think you also have to check the last number with any new greater element and then swap them both.
You could just look for the 1 positive number and place a pointer on the positive side and one on the negative. Now just sq the values on either side see compare which is smaller and add that to the op array
For loop of the array which iterated through the size of the array, find number closest to zero, and work backwards. Keep track of lowest, highest, and previously sorted number to make it quicker, then, once sorted, a while or for loop to square each element in the array.
Small tweak of merge sort is best. Find the first negative and first positive. Pad output array, start stepping positive/negative side, insert the smallest. This method avoids using the Math.Abs() and will be faster. O(N).
6:07 Hmm. 36 < 25
My solution is finding the first positive value using binary search, splitting negative part from positive part, square both parts and merge them taking into account that the negative part is now "reversely sorted".
Divide and conquer style!
My first thought was: Those negative values are the ones making this difficult, so let's get rid of them. And in the end, the worst-case complexity is still N (more precisely logn + 3N)
You could save a scrap or two of memory through destructuring by doing "int i = right" in the loop.
I think on 6th line of second optimised code there should be Math.abs [right] as well, because as you said array full of negative numbers is a valid input.
Great solution. I would also add that if all the input numbers are positive, this approach can be simplified and done in-place, thus reducing the space complexity to O(1). That’s because when they are all positive, you know squaring them will not change their sorted order. Simply check the first index of your input array, and if its value is positive, square all the numbers in-place. You could also do something similar to save space if all the input numbers are negative, since you know their squares will be in reverse sorted order.
in 2nd approach if we use while loop instead for loop will improve time complexity @Nick
this solution is far better than your previous solution of the same problem. I guess you did that for leetcode. thanks for your work.
def solution(lst):
if not lst:
return "Invalid Input"
return sorted(map(lambda x: x**2, lst))
lista = [-7, -3, -1, 4, 8, 12]
print(solution(lista))
Nick: Simple idea is to square the array then sort it, but it isn't efficient because sorting is n*log(n) at best, we are aiming for linear time complexity
Every other python "expert" in the comments: lemme write one liner to show how smart I am using built in sort method
Loop from the number closest to zero, compare it to the neighbours with their absolute values, square the larger one and put it in the result array.
just looking at 6:55, I paused and opened pycharm. I tried once, didn't work. Debugged in two places and it worked!! thanks nick for making these videos.
This algorithm will work if the input array is sorted. We can use modified counting sort algorithm to solve the problem for unsorted input array. It'll take linear time. Maybe I'm wrong.
If there's an O(n) solution for an unsorted array, we can input some positive integers, then apply this algorithm and sqrt each member, in output we'll get an original sorted array and it will work for O(n), but sorting is actually O(n*log n)
@@aertyty3900, count sort and redix sort take linear time (it seems linear) and in required output all numbers are positive. If we take square for each element in array, it'll be done in O(n) and then apply one of these sorting algorithms. It's my thought and I'm not professional programmer.
@@muhammadrizwan4999 I meant that for the given bounds both algorithms should work but if number length is unlimited it will run out of memory
@@aertyty3900 yes and we are sacrificing memory for speed. My bad I wasn't able to understand your previous reply.
def sortedSquared(arr: [int]) -> [int]:
squared = list(map(lambda x: x*x, arr))
for i in range(len(squared)-1):
mini = i
for j in range(i+1, len(squared)):
if squared[j] < squared[mini]:
mini = j
t = squared[mini]
squared[mini] = squared[i]
squared[i] = t
return squared
Been out of touch with problem solving for a while now. Being able to solve this optimally made me good about myself. Idk why I'm writing this....
There is a way around the n log n complexity of sorting: the problem explicitly bounds the range of inputs, so you can use a linear-time radio sort. It would be dumb, but you could do it.
Good work, using right and left pointer is the best way to go about it. May be only way!!
After hearing the question, I was like loop through and square, are you serious? You call that a coding interview, blah blah blah, then 2 minutes in... oh
I was I can do this in less than 5 lines in python but this vid has almost 13 mins
@@dragon_warrior_ yes hes doing on java, phyton is to ez
Yep wtf
Atleast we can take the absolute value of the elements and sort it and then get the output...
Edit: I did not watch this video fully...
@@baka_geddy Sure that works, however the goal of the video is to bring it to linear runtime, i.e., no direct sorting.
This is so easy in javascript with the sort command.
You just sort the array and then use the forEach command to get the output.
Oh, I thought to start pointers from middle where sign changes. Great solution.
If both left and right values are equal, we can increment left and decrement right i and can sort the values in result array ,except when they are equal
I would argue in favor of the square everything then sort it method. It is O(n * log(n)), which is not slow as you said. Also our n is less than 10000, so when this is not called in a hot loop millions of times readability wins over shaving of one log(n) of the time complexity.
What Nick is doing has time complexity O(n)/linear and he said it's the best way to do it, what if we square numbers of array and then apply MERGE SORT that has time complexity O(nlog(n)) in all the best to worst case time complexity scenarios (we would need left and right(start and end) values in array for merge sort).
Which one would be good way to solve the problem please tell me, I'm confused?
P.S. Nick's solution and mindset towards problem was absolutely amazing! :)
Even though i understand that your algorithm is clearer to read, but I must point out two things:
- you are calling Math.abs each iteration, which is not ideal. you'll have to square it anyway, calling abs is 100% unnecessary.
- you aren't really taking advantage of having a sorted array properly. After all the negative (or positive) numbers are "consumed" you know for sure that you can just consume all the leftover numbers in order.
pros of mine:
- takes less if()s
- has no dependency
- ifs are faster to evaluate
cons of mine:
- harder to reaad
- took me a bit more time, which is obviously not ideal in an interview
int[] sortedSquaredArray(int[] array) {
int i = 0;
int length = array.length;
//square negative ones
first
for (; (i < length) && (array[i] < 0); i++) {
//by naming the arrayaccess value, you don't need to access the array 2 times, only once
int val = array[i];
array[i] = val * val;
}
int[] result = new int[length];
int l = 0;
int left = i-1;
int right = i;
//i'm iterating from the inside, not the outside like you do.
while (left >= 0 && right < length) {
int leftValue = array[left];
//by naming the arrayaccess value, you don't need to access the array 2 times, only once
int rightValue = array[right];
int rightSquaredValue = rightValue * rightValue;
if (leftValue < rightSquaredValue) {
result[l++] = leftValue;
left--;
} else {
result[l++] = rightSquaredValue;
right++;
}
}
//when we get to the end of the minuses or the pluses, we might have a bunch of numbers left.
//these numbers are all sorted they need 0 checking, they just need to be added to the result array.
if(left >= 0){
for (; left >= 0; left--) {
result[l++] = array[left];
}
return result;
}
for (; right < length; right++) {
int val = array[right];
result[l++] = val * val;
}
return result;
}
please notice me :D
Guys, don't you see that stuff like this gets more and more complicated and thus less maintainable? Would you like to hunt for a bug in code like this? (Do you have experience doing this, especially if this isn't your own code originally?)
One of the main goals in modern software development isn't the fanciest most optimized version of an algorithm but to have *readable* code. Code which the next maintainer will understand as fast as possible. It's alright to bring an algorithms from N log N down to N if you really have large input. If this is going to save 20 seconds of runtime within the next four years, it is probably not a good idea to even optimize for this. But any optimization beyond this (as in the post above) needs an enormously good reasoning to be justified. »This is even a little faster« is not such a good reasoning ;-)
@@alfeberlin Then again, this is really easy to test, as you just have to compare its output to the sort(squared_arr) version on random arrays. So you could become pretty confident that the algorithm does what its supposed to do.
@@lucast2212 Testability doesn't make the code clean ;-) You will find out the difference as soon as one of the tests fails ;-)
I'll take "what is compiler optimisation" for $0
@@alfeberlin Honestly, if you want readable code you only do sorting by hand if it is absolutely a must for performance. I'd just .stream().map(...).sorted().collect it.
if i really wanted to make it performant, i would do sth like this:
Stream negatives = .stream().takeWhile(i < 0).map(...)
then
Stream positives = .stream().reversed().takeWhile(i >= 0).map(...)
and use something like negatives.mergeSorted(positives).reversed()
and there you go, 3 lines of code, and even newbies can understand it. Google's coding challenges are stupid, it's much harder to model problems properly than to come up with fancy algorithms, and still they ask you to come up with algorithms that you can argue a lot about whether it's good or not.
just to be clear:
+ before the last step the indices are always equal (because the total number of processed elements is len(array) - 1
+ hence it doesn't really matter for the last step which index is advanced;
+ if all elements are negative, the left pointer always advances because the absolute value of a negative is greater than any negative number (including the first)
+ if all elements are positive, the right pointer always advances because the left pointer points to the element with the smallest absolute value
+ the same reasoning applies when the negatives run out before the positives vs the positives run out before the negatives
+ if the order is negative, positive, negative, positive... or positive, negative, positive, negative -- then the two pointers meet in the middle, and which pointer advances last depends on the parity of the length and which element came first
+ elements with equal absolute values are treated as elements from the "right" side (they fall in the else clause)
@Nick White it may have been more intuitive (though that's debatable) to condition the loop on equality of the indices and then just take the final element. But this is OK too, because on each loop step each index is changed by one, so the sum of the distances traveled by each index equals the number of iterations.
Do a time execution from both code options to show the conclusion of being faster.
2nd method will be faster, it's only taking 1 parse through the array, so N.
In first case we were going through the array to square each element, so the time complexity is already N + sorting time
There's no need, he gave the time complexity.
The O(n^2) solution can on occasion be faster than O(n), so execution time doesn't tell you much unless you run it on a sufficient number of inputs.
Just one minor add on to the comparison, we can replace the call to Math.abs by adding the two numbers together and return right on positive/left on negative.
That's interesting. Is using Math.abs () not recommended when you want to consider the most optimal solution?
Nick White - you really have an excellent thought process while dealing with problems.
Nice! But in practice there is no difference in runing time. With 10000 integer both method finished in 1ms. Perhaps running with 100 000 or more ... Do not forget: calling Math.abs() and if()-s has price too.
watched this video, went to solve the question, proceeds to forget about the for loop and does it with while loop, now i have 2 solutions. So the algorithm explanation was well done.
I know coding very little, but enjoy problem solving videos. thanks Nick.
Likely better to square them all up front. That avoids the absolute value and array operations are usually faster. Good video. Thanks.
Is it really faster though? You would need to loop through the array twice.
@@StraightCrossing you can do it as you compare them
Niko Ursol If we are really nailing it to that detail, you’ll square each number twice by the way you describe. Better just compare the sum of two numbers with zero to get the optimal solution timewise.
@@MY-bc3qq why would you have to square it twice? It's only one time thing - before you comparing them, and than just merge stuff together as you go.
You have to copy each int twice tho, but its cheap. (by copy twice i mean copy in buff to square them, and then emplace (copy again to resulting list)
in the end even squaring whole list, grouping them together, reversing one half, merging them would be in O(n)
Yeah. You are making potentially millions of calls to ABS(). That's expensive
First i think about using hashtable so the time O(n) but it is not optimal way for memory. Your solution is so great.
In Javascript:
function double(ar) {
let arr = [];
let pointer1 = 0;
let pointer2 = ar.length - 1;
for (let index = 0; index < ar.length; index++) {
if (Math.abs(ar[pointer1]) > Math.abs(ar[pointer2])) {
arr.unshift(ar[pointer1] * ar[pointer1]);
pointer1++;
} else {
arr.unshift(ar[pointer2] * ar[pointer2]);
pointer2--;
}
}
return arr;
}
What if you go through the list, if you see a negative int, square it and throw it in a max heap (or max priority queue, or I'm assuming a normal queue would work also since array is sorted so negative ints thrown into the queue will be smallest square at the back biggest square at the front), If you see a positive int then square it? check max heap and keep popping until max element is less than your positive int, then just keep going, throwing elements in whatever new list you initialized at the beginning
Should be O(n) if I'm not missing anything
Lol meanwhile in python all you need to do is return sorted([x*x for x in input], reverse = False) where input is the list they give you.
"...yyyoooOOOOOOOOOOOOO (slap) what is up uhh (forgot the word for "coders") coding people that, watch coding videos"
lmao I always love your intros
can i use sort function of python to sort it after squaring every element.. i think it's time will be O(n)..??
you was 18k sub like a day ago ,I blinked and now you're 21.4K looks like somebody discovered the youtube algorithm secrete!!!!
gj keep it up:)
I find this similar to merge sort while we try to merge 2 list into 1. nice video man.....
Very well explained with a high quality microphone lol. Thanks!
what about looping through the input array and adding the square of each number to a treeset?
Though it is not written here,I have to assume that optimal time complexity is what the interviewers are seeking??/And should I think about optiimizing my time complexity or spae complexity,when nothing about them are written here???
# Python Solution for the Equivalent Java Logic
def sortedSquareArray(nums) :
n = len(nums)
output = [0]*n
left = 0
right = n-1
for i in range(n)[::-1] :
if abs(nums[left]) < abs(nums[right]) :
output[i] = nums[right]*nums[right]
right = right - 1
else :
output[i] = nums[left]*nums[left]
left = left + 1
return output
solution doesn't work for all negative numbers - you need to do abs of right hand side too , and left and right pointers cross each other as there's no check for them "meeting"
last approach does not work for the input : { 4, -2, 0, 9, 3} -- output will be : 0,4,81,9,16
The problem says that the input array is already sorted. The input you gave isn't.
If we use the 'Set' data type the output would be sorted right? Isn't that O(n) complexity?
The rest part of the code is the same.
I think you can add this into top of your methode to make it more efficent. if( array[left]>0){result[i]=array[right]*array[right];right--;}
Because if array[left] if bigger than zero it is already sorted right ?
The solution seems so easy once you explain it in your style. Thanks a lot for coming of with such great contents.
6 lines in python:
def sortedarray(array):
new_array = []
for number in array:
new_array.append(number**2)
return sorted(new_array)
print(sortedarray([-7,-3,-1,4,8,12]))
or better solution:
def sortedarray(array):
new_array = []
for number in array:
new_array.append(number**2)
for i in range(len(new_array)):
for j in range(len(new_array)):
if new_array[i] < new_array[j]:
t = new_array[i]
new_array[i] = new_array[j]
new_array[j] = t
return new_array
print(sortedarray([-4,-4,-2,6,7]))
Before the video: I’d use another array and I would go through the original array, square the element and use a binary search to find the location that the element should go and then place it: insertion sort.
Edit: didn’t realize the original array would be sorted
Your last method are basically kind of merge two sorted arrays were you handle the minus value as their abs value
Python answer:
def selectionSort(l):
for i in range(len(l)-1):
minimum = i
for j in range(i, len(l)):
if l[j] < l[minimum]:
minimum = j
if minimum != i:
temp = l[i]
l[i] = l[minimum]
l[minimum] = temp
return l
def sortedSquaredArray(arr):
arr = [i**2 for i in arr]
arr = selectionSort(arr)
return arr
Your videos help me have the proper problem solving mindset. Thank you!
4:07 Arrays.sort(square_the_array);
Isn't this question too easy for something like facebook? idk
dude , are you dumb somehow?
The time complexity is nlogn....too high.Facebook wants less not the average soln
What if we use sets to store the data. It will automatically sort as the data will be entered. (No number is repeating)..
What will be its time complexity?
Man! You are gold. Thankyou so much for making these videos
Theres a similar way still linear (2n tops) that I believe in real world could be faster on a large data set with all or mostly positive / negative inputs. If you can first find if/where the first positive or negative meets you could possibly perform some optimisations. So you're still comparing iterators but instead of working inwards from each end you work outwards from the midpoint. The solution in video is definitely better for general cases but if you know roughly what your inputs are like you can usually make optimisations. I believe this is something you learn with real world experience as 2 linear solutions can have vastly different runtimes.. this is one thing i dont like about these kind of questions.. yes it demonstrates knowledge and understanding of algorithms and datasets but in actual coding the problems are rarely like this and some calculation in a linear solution can work out slower than a n log n solution (its unlikely but possible). Profiling should always be preferred to simply relying on your time or data complexity.
You said sorting is worst case O(NlogN). But its worst case is O(N^2) right? And just the average sort time for a random array is O(NlogN)?
Thank you, still learning how to code but I was able to follow along with your explanation 👍
Your teaching style really clicks for me! Thank you!
I ended up checking if they were equal (having a -12 and a +12) so I had an extra conditional statement but checking the absolute value of the left value to the right value is actually kind of elegant...didnt dawn on me to do that
put another condition when left pointer iterates all the negative and we're only left with positive numbers just insert all the positive numbers as the given sequence
btw great video
i thought of travelling to 1st positive number and then use 2 pointers on right and left list just like in video, but i guess that travelling is unnecessary now
We can also make 2 vectors with squared value of - ve and +ve no.s and mergesort them
Dude keep making these kind of videos, it helped so many people. God bless
Solution with reading values from both ends and comparing them is pretty obvious here.
Is there ever a case where you would need to have math.abs for the right pointer as well. Such as, if there are more negative numbers than positive and the right pointer hits a negative.
I would complain that they didn't specify how the input array would be sorted. Also, sorted means arranged in a certain way, so you can just copy the input array, square each value, and say it is sorted by input array matching order. That is actually legitimate. The specifications of the problem are unclear and I would argue that. Sorted, for example, could mean all single digit numbers followed by all non single digit numbers. It does NOT always mean nonascending or nondescending. They didn't specify how they wanted the output sorted so ANY pattern is acceptable, as long as it is well defined (input array element position matching is well defined = unambiguous). You didn't specify if the examples you presented here came from you or came from FB, so I cannot assume they were from FB as part of the problem. So my solution is simpler and faster than the one presented here so I "win". So to be clear, if the input array was [-7, -3, -1, 4, 8, 12], my output (sorted) array would be [49, 9, 1, 16, 64, 144]. It is a valid solution based on the definition of the word sorted. Another output sorting could be [1, 9, 49, 144, 64, 16] which is single digit results first followed by non single digit results. Just to be clear, sorting is basically the opposite of random. Random means no order assigned (intentionally), but sorted means there is some order given to something (but not necessarily nonascending or nondescending). I can start work on Monday FB.
Yo Nick. The solution is neat, but it will fail in the case when the whole array is made of negative numbers. Math.abs should be done for both sides.
This is the best explanation of this problem over the internet !!!