Facebook Coding Interview Question - sortedSquaredArray

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@mdouet]

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.

[@harryhopkinson162]

Did you get the job? If so congratulations!

[@hhcdghjjgsdrt235]

bro party !!!!

[@bhaveshgavali531]

Hi

[@davidhahn7391]

youtube algorithm picks up another algo video

[@tannerbarcelos6880]

David Hahn sounds like like recursion right there lmao

[@VKD007]

@@tannerbarcelos6880 its a pointer

[@52.yusrilihsanadinatanegar79]

@@tannerbarcelos6880 yeah, it's like like like recursion there

[@maythecodesbewithyou29]

yup

[@maruf_r]

CanAlgolism

[@AnthonyLauder]

This is essentially the final stages of a merge sort, with one list starting on the left, and the other starting on the right.

[@shahman1]

that's interesting

[@markj.7557]

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.

[@cappuccinopapi3038]

I could binge 4 seasons of this

[@akhila5597]

same

[@Bskater952]

Haha! Facts

[@ThereIsNoSpoon678]

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...

[@umutti11]

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!

[@WhatIsThisAllAbout]

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

[@TheRealisticNihilist]

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.

[@AR-yr5ov]

The whole time I thought the input wouldn't be sorted.

[@memespdf]

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...

[@michaelvoline6205]

Yeah

[@iradnuriel9087]

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.

[@arnabmitra08]

@@iradnuriel9087 Given that the range of input is between -10000 and 10000, you can use counting sort for linear time sort.

[@motiyanshekhar2002]

@@arnabmitra08 that is exactly what came to my mind It's much simpler than this pointer stuff anyway.

[@CST1992]

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.

[@madghostek3026]

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

[@ZeusMoosePlays]

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

[@danieltsikata2898]

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

[@purnendutiwari9570]

hey bro...u r doing gud .... keep updating by these type of questions.......

[@BharatiSubramanian99217]

Man! You are gold. Thankyou so much for making these videos

[@mumen_rider4209]

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

[@minhazulislam4682]

I know coding very little, but enjoy problem solving videos. thanks Nick.

[@jpchato]

Thank you, still learning how to code but I was able to follow along with your explanation 👍

[@mrugankgadgil7368]

Nick White - you really have an excellent thought process while dealing with problems.

[@anirbansarkar6306]

The solution seems so easy once you explain it in your style. Thanks a lot for coming of with such great contents.

[@fawazsullia5620]

Your videos help me have the proper problem solving mindset. Thank you!

[@kristenkrofchik7998]

Your teaching style really clicks for me! Thank you!

[@imlovinit1232]

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.

[@phucminhnguyen8909]

First i think about using hashtable so the time O(n) but it is not optimal way for memory. Your solution is so great.

[@bishwanayak]

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.

[@LoganKearsley]

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.

[@harshitjain8235]

Would love to watch more of such solutions to interview questions

[@halvard1218]

6:07 Hmm. 36 < 25

[@n0ame1u1]

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.

[@gothams1195]

I find this similar to merge sort while we try to merge 2 list into 1. nice video man.....

[@hawsh3066]

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:)

[@user-dc2uy3jf5v]

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

[@mDevinm]

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!!!

[@gangeshshaw172]

We can also make 2 vectors with squared value of - ve and +ve no.s and mergesort them

[@GabrielPerez-ml2go]

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

[@brunokawka]

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.

[@moai834]

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.

[@GustavoCevalhos]

Hi! You would be searching N times in the input, which would lead to N*Lg(N) overall time complexity.

[@brunokawka]

@@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

[@GustavoCevalhos]

@@brunokawka True! I misread the explanation, you are correct :)

[@samridhsinha1126]

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

[@Moses_coder]

Good work, using right and left pointer is the best way to go about it. May be only way!!

[@eversnipestudio]

Dude keep making these kind of videos, it helped so many people. God bless

[@babumon5351]

Great solution. Thanks

[@mdabidiqbal1153]

You have explained quite well.

[@MrKeksdoserl]

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.

[@Maaruks]

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.

[@minhazulislam4682]

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.

[@holatechm]

in 2nd approach if we use while loop instead for loop will improve time complexity @Nick

[@shingiraibondai747]

Well explained please dnt stop these tutorials ☺️

[@nikhilreddy6476]

Oh, I thought to start pointers from middle where sign changes. Great solution.

[@ClearerThanMud]

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.

[@bryancoreavargas9600]

Elegant solution, keep it doing well

[@abhishekbalawan6817]

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.

[@vivek4634]

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.

[@LukeDupin]

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).

[@priyankadey3337]

Thanks for the amazing content!

[@Selim_Hasan_Raj]

Nick could you send the interview tutorial links ?

[@7906jun]

Thank you Nick !

[@sanderschat]

Do a time execution from both code options to show the conclusion of being faster.

[@aswins2529]

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

[@Chr0n0s38]

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.

[@naturallyweird661]

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)

[@sarveshmishra8416]

This is the best explanation of this problem over the internet !!!

[@michaeldang8189]

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

[@dragon_warrior_]

I was I can do this in less than 5 lines in python but this vid has almost 13 mins

[@davideareias7876]

@@dragon_warrior_ yes hes doing on java, phyton is to ez

[@mattop8656]

Yep wtf

[@baka_geddy]

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...

[@michaeldang8189]

@@baka_geddy Sure that works, however the goal of the video is to bring it to linear runtime, i.e., no direct sorting.

[@SidsVlog]

this solution is far better than your previous solution of the same problem. I guess you did that for leetcode. thanks for your work.

[@lets_see_777]

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

[@tetlamed]

What about constant space complexity, sorting in-place?

[@MrHarbltron]

You could save a scrap or two of memory through destructuring by doing "int i = right" in the loop.

[@imlassuom]

I was thinking if v.begin >= 0 just square and return; else if v.end

[@omarghosn8655]

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

[@larenmarkdcruz7074]

Pretty neat explanation! Post more content!

[@mohammedjawahri5726]

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

[@ChiragKava]

Great work!

[@Yarin5879]

Your last method are basically kind of merge two sorted arrays were you handle the minus value as their abs value

[@n0ame1u1]

Is there any way to improve the space complexity? Is it possible to do an in-place merge?

[@powerToYourself36]

What made you chose code signal?

[@Chickenspoon410]

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.

[@bhaveshgavali531]

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.

[@MY-bc3qq]

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.

[@codegirl2069]

That's interesting. Is using Math.abs () not recommended when you want to consider the most optimal solution?

[@B00Mnation]

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.

[@muhammadrizwan4999]

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.

[@aertyty3900]

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)

[@muhammadrizwan4999]

@@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.

[@aertyty3900]

@@muhammadrizwan4999 I meant that for the given bounds both algorithms should work but if number length is unlimited it will run out of memory

[@muhammadrizwan4999]

@@aertyty3900 yes and we are sacrificing memory for speed. My bad I wasn't able to understand your previous reply.

[@emrehamurcu5454]

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 ?

[@youtuberlast8281]

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.

[@addielmartinez9120]

Very well explained with a high quality microphone lol. Thanks!

[@saidaouyous3485]

That was very helpful thanks nick🤗

[@twofaces4410]

Such a great start 0:00👌

[@poojaguru2516]

Awesome Nick🔥

[@mkedzier123]

Solution with reading values from both ends and comparing them is pretty obvious here.

[@codingintelligenceci7081]

I find your videos so easy to understand

[@vanamutt43]

what about looping through the input array and adding the square of each number to a treeset?

[@dev10shah]

Can you tell which screen recorder you use?

[@gabriellerosa6453]

Great explanation !!

[@nayeemrafsan356]

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

[@jesusberrio5682]

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)

[@rafaelpernil]

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!

[@rafaelpernil]

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)

[@saeedbaig4249]

"...yyyoooOOOOOOOOOOOOO (slap) what is up uhh (forgot the word for "coders") coding people that, watch coding videos" lmao I always love your intros

[@dattatreyapujar4068]

Good way of explanation

[@androidking8158]

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.

[@mishikashukla9746]

could we do that using multiset?

[@fredhair]

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.

[@ReTroIIer]

If you need a handy one-liner in java: int[] squaredArray(int[] array) { return Arrays.stream(array).map(i -> i * i).sorted().toArray(); }

[@narendrachowdary6894]

Ikr

[@AmanVerma-lt7px]

I somehow knew that your next video is going to be this one

[@jpm2681]

Nice solution!

[@robertfisher3507]

absolute value of negative elements of input array and sort that array. then all you have to do is square each value in the same order.

[@taggy9117]

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.

[@Naton]

Man this guy is good.