Facebook Coding Interview Question - First and Last Position of X in Sorted Array

11th May 2022 update - I have two slots in my interview-prep group classes! errichto.com/c...
Finding value in sorted array? Sounds easy, doesn't it? This is a coding interview question from Facebook. You can try it yourself on Leetcode: leetcode.com/p....
Get your CV reviewed and get a referral to FANG company, using www.rooftopslu...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Err...
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Err...
#Coding #Programming #CodingInterview

[@0lange]

"Thinking is very good in programming"

[@NoName-ip4tt]

That also means: "Not Thinking is too bad in programming!"

[@stevancorre1951]

lol nice icon

[@AAAAAA-gj2di]

@@NoName-ip4tt *very bad

[@senatorpoopypants7182]

Damn he's good, and it takes me a minute to just process his logic after he writes it. Someday senpai, someday

[@luhuang5256]

Yep. This is a common interview question and it's a good one because it's just different enough from standard binary search to avoid a memorized solution and just simple enough to be implemented and discussed in a half hour interview. Sure, plenty of people have practiced this but writing it out and testing it on a whiteboard still demonstrates programming ability.

[@user-mo6ov1qf2q]

Thanks for the video, clear and short as usual. Besides lower_bound and upper_bound, there is one builtin function that not everyone knows about called equal_range that does exactly what required in a single step

[@PavanKumar-jt5mq]

Cool, I just coded two binary search one for first pos and other for last pos. Yours is cleaner. Nice :)

[@abhinavdhama7193]

If I write in java...I could have just first arranged it in ascending order and then I would have simple typed:- l.indexOf(x) // l being the array and then l.lastIndexOf(X) as simple as that!

[@Squirrelschaser]

@@abhinavdhama7193 uh no. 1) The interviewer is obviously not looking for that 2) It's already in ascending order. 3) indexOf is O(n).

[@abhinavdhama7193]

@@Squirrelschaser why is the interviewer not looking for that?

[@Squirrelschaser]

@@abhinavdhama7193 Because he obviously does not want you to use a built-in function and it's not even the optimal solution?

[@areks4397]

@@Squirrelschaser Not optimal according to what? I guarantee you if you use that in an everyday problem your teammates are going to hang you from your nails.

[@martinsauer4854]

My first answer probably would have been just looping through the array once and then saving and returning the index if time complexity was irrelevant 😅

[@luffyy8084]

I didnt underrstand the last part as to why we initialise firstpos=n and not firstpos=-1 . can anyone help

[@bivashthakur9199]

bcz in the case of n=0 the position would be 0,0 and not -1,-1

[@AbhishekSingh-cd6yc]

heyyy :) first sponsor. i am feeling like a proud father.

[@Errichto]

I also got an offer from some game :D

[@AbhishekSingh-cd6yc]

@@Errichto that's nice to here. keep on moving forward.

[@mirelahmed9625]

The concept of modifying the function to check element >= x and then using It to find pos of x+1 is lit! The best use of the fact that the array is/can be sorted

[@TheBestNameEverMade]

You can do this with less opperations with one binary search. By restarting the search a lot of useful information is thrown away. Even with the solution given here one could have at least started your second binary search from the first element found.

[@MojahooProducer]

:0 sponsor! Thank you for all the videos and content in general, I can't express my gratitude enough

[@imlassuom]

std::equal_range() then check and adjust the iterators pair...

[@SumeetSharma87]

I haven't run the code myself but I was dry running it in my mind and it looks like if you assign first_pos as -1, then you don't need to have the check for first

[@SumeetSharma87]

Ah I wrote the code and I see the importance of the check It is check for unary array case and I must say that is the most killing logic in whole soln

[@freddyhaug9379]

I have much to catch up, I would've just scanned the array from the front and the back until I found the positions Binary Search is much faster in a SORTED Array

[@florianpiper9872]

binary search is only posible in a SORTED Array ;-)

[@jonathanmantello3974]

Great video! I understood most of it, up until the last bit. I'm still fairly new to programming and don't know algorithms yet, but I am confident I can learn with resources like this. Thank you!

[@eyosiasbitsu4919]

i also had trouble with understanding what he did after he created the function called it two times for the right and the left

[@eyosiasbitsu4919]

it would be cool if @Errichto would explain it a little bit more

[@Biliklok]

I think you could do `last = first_pos(a[first_pos..], x + 1) - 1` There is no need to take the full array since you know that it's sorted and that x + 1 is going to be bigger than x :)

[@verushannaidoo9450]

Oh yes that makes it even faster ! ;)

[@dorijanlendvaj8356]

@@verushannaidoo9450 It's only 1 less iteration of binary search on average, if for example n=2^17 instead of doing 34 iterations in total you'll do 33 on average. It really doesn't matter that much.

[@verushannaidoo9450]

@@dorijanlendvaj8356 Makes sense a very slight and unnoticeable difference

[@incrediblecoder3369]

Was waiting for something. Good question to understand important concepts.

[@Errichto]

Yup, especially when you try to implement this in a simple way.

[@incrediblecoder3369]

I have solved a problem like this only twist is the array is not sorted. I remember using the Dutch flag method to do this using pivot value as the given element and use partition method used in quick sort.

[@incrediblecoder3369]

@@urstrulyubc O( N ) indeed as we need to traverse through the array and move the numbers lesser than the element to the left and greater elements to the right and to track the elements equal with start and stop indices. Ofcourse we need to handle case of given number not in the list.

[@omrib40]

Basically you could just search for x+0.5 and x-0.5 in order to achieve it using normal binary search, if the inputs are integers. First = binsearch(x-0.5) Last = binsearch(x+0.5)

[@MrNsaysHi]

There is also the function of std::equal_range() in C++.

[@AADIPRAKASHMANCHEKARBIT]

yeah like this, vector v = {1,2,3,4,5,5,5,6,7,8,9}; cout

[@hoangucmanh299]

I'm really looking forward to your videos on Dynamic Programming and Backtracking since they're fundamental

[@Errichto]

I did some videos on DP already. Maybe will cover backtracking in the future.

[@julesjacobs1]

A more compact way to do it: int first_pos(vector& a; int x){ int low = -1, high = n; while(high - low > 1){ int mid = (low + high)/2; if(a[mid] < x) low = mid; else high = mid; } return high; }

[@angelbythewings]

mid should not be calculated in the manner you have it in your code, it should be low + (high-low)/2, that is done to avoid integer overflow for large array size

[@julesjacobs1]

@@angelbythewings That's what people often say, but that's outdated info on 64 bit platforms. The 32 bit int can still overflow even with your code. If you want it to not overflow, use a 64 bit int and then it doesn't matter.

[@angelbythewings]

@@julesjacobs1 I don't think I completely follow you, how do you claim that it does not matter ?

[@julesjacobs1]

@@angelbythewings If your 64 bit value overflows, that means that your array is 9223372 terabytes. Until such memory becomes available, there is absolutely no issue.

[@tannerbarcelos6880]

Brilliant solution. I thought binary search, but then was stumped with “I found left boundary.. how do I do this without a for loop off of this index?” And then you explained the binary search on x and then a value greater than it, it all clicked. Thank you!

[@wagnerrodrigues6440]

Thanks, Errichto very nice solution! I did two binary searches, its a nice idea to use the information you obtained on the first search!!!.

[@fmxy]

could you add complexity discussion at the end? I would have just reversed the array at some point which probably would've increased time complexity.

[@haze86]

Excellent content, I'm learning a lot. Thank you for what you're doing.

[@kirdiekirdie]

Without looking at the video, just use the library functions to reverse it and then the one to find the first element, not fast but 3 lines of code 😁

[@Rikenm14]

Binary search questions have a really good disceranble pattern.

[@brucewayne2480]

I would do a binary search to find the element then create two variables min max intialized to that position , one that goes to the right and the other to the left if they find another element different from that element , i will save the last position

[@Errichto]

Your solution is O(N) instead of O(log(N)).

[@harshbaliyan5867]

Worst case scenario: O(N) You will loop through all the element

[@shubham-pp4cw]

Nice and Simple Explanation, thank for video keep it up

[@DAEDSOLOGAMES]

I haven’t watched the full video. Yet i am not an expert programmer but i can say that we can find the first and the last specific element we need by doing the following: first we do a loop starts from index 0 to the first specific element we catch. Then we do a loop starts from array.length-1 and breaks on the first specific element we want.

[@MrStar1102]

That's correct, but the time complexity would be O(2n) = O(n), with binary search, the time complexity downs to O(logn), that would be much faster.

[@DAEDSOLOGAMES]

Weirdo Beardo i am sorry to say that i have not studied Data Structure yet.

[@MrStar1102]

@@DAEDSOLOGAMES Haha, dont say that dude. Glad to help you!

[@DAEDSOLOGAMES]

Weirdo Beardo Glad to learn new thing from you. Thanks dude

[@lan2667]

That kind of only works better for test cases that have a large duplicate string X like, finding bounds of 3 in 12333333333333333333333334. It wouldn't do 112222222222222223333333333333...44444444444444..999999 any favors if you're trying to find bounds of 1.

[@izzfhd_70-16]

I think it can easily be done by upper bound and lower bound. If we can't find the val. in the array then cout -1. I THINK

[@amey7064]

What's faster? lower_bound method or your implementation?

[@Errichto]

lower_bound might be slightly faster, but you should never care about so small differences.

[@kiranbhanushali7069]

Thank you for your videos. Can u tell the right direction to improve the CP for Intermediate. I can only solve first 1-2 problems in contest. How can i improve that. Thanks in advance.

[@treyquattro]

quite brilliant. I would have just linear searched for min & max positions like most people I presume

[@MrBarralex]

Sure, but we also know is slow as fuck, so i would think in other ways too.

[@Daniel_WR_Hart]

I didn't try this question, but I find that if they specify a desired time complexity, your solution can fail if it's too slow for a larger test case

[@fritt_wastaken]

Most non-programmers would. I can't really imagine a programmer not using binary search :D

[@DreadDoom]

@@fritt_wastaken Then you have a poor imagination.

[@treyquattro]

I meant binary search for the number, then naively linear search backwards and forwards for the ends of the range. I may not be that smart, but I'm not that not smart...

[@iamdhruvcool]

Just solve using segtree. First find leftmost position using one query then do same to find rightmost . Node stores count of 8 in the range

[@Errichto]

Linear iteration would be much faster and simpler than creating a segment tree ;p

[@iamdhruvcool]

@@Errichto yea but I have noticed that thinking in pressure is much harder for me. With segtree there are so many times I don't have to think. I just gave alternate solution. I would have also used upper bound and lower bound and then taken their difference.

[@iamdhruvcool]

@@Errichto Also can you make video bitmask dp I want to understand it properly.

[@ouyaah]

Nice explanations. For the second call of first_pos, if you give the same vector but only starting from "first" index, found in the previous call, I guess it gives a speed up, right? Or is it not worth it?

[@yazanzo3bi610]

is there a problem to solve the question with brute force strategy

[@nl8163]

in python you could do x = int(input()) a = [3, 4, 5, 6, 6, 6, 7, 8, 9] try: index = a.index(x) count = a.count(x) print([index, index+count-1]) except: print([-1, -1])

[@NikhilKumar-oy7mx]

Can't you just search element and then traverse untill element changes.

[@bruhmoment8167]

HiImBrunzz oh that’s what slower means

[@shmaestro]

No, as the problem asks for it to be done in log(N). If all values are x (i.e. match the expected number), then it will be O(N).

[@lan2667]

@@bruhmoment8167 username checks out!

[@ShubhamSinghYoutube]

Why vector&a , not vectora , somebody explain

[@jalsol]

vector a will create a new copy, while vector &a will take the vector passed from the main function directly (but modifying it also modifies the vector in main)

[@ShubhamSinghYoutube]

@@jalsol cool, that's what I thought , Thanks a lot

[@TheSd321]

It's not only me who solved a problem 9 (or 1) months ago and then getting "wrong-answer" on re-attempt. :p Until 07:25 I was thinking you are going to solve it in one while loop. Thanks for the lesson, mate! :)

[@Errichto]

It's very easy for a mistake in such a problem, I also got WA here :D

[@gabriellerosa6453]

I love you videos Errichto !!! Thanks so much !!

[@hardlane2961]

The king of algorithms

[@mohdar2061]

I made it so that I first find any x with Binary Search then run in a while() as much as possible to the left and right where left and right are indexes of elements that equal x and at the same time right and left are within the array length and 0. I think it is with the same time complexity as yours. I like your solution more though

[@peculiaroluwagbemiro5656]

No it’s not, your solution is O(N) worst case.

[@maxdeboer6362]

Does this also work with an array like [1,2,3,4,5] when you are looking for 5? First_pos(a, 6) returns then -1, so the program returns {-1, -1} instead of [4,4] I think

[@variancaesar4778]

I think no, first_pos(a, 5) returns 4 first_pos(a, 6) returns 5 then he subtracts it with 1. The final result is 4,4 which is correct as you mentioned

[@nikhilmakam8794]

Hi Errichto, thanks for all the work you're doing. Can you please make a video on Manachers Algorithm? #Suggestion

[@apdy27]

If using stl, equal_range could be used.

[@tindo0038]

goated content. thank you.

[@petyoruzhin7191]

My solution in Javascript but it could be applied to any programming language: /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function(nums, target) { var res = [-1, -1]; for(var num in nums) { if (nums[num] == target) { if (res[0] === -1) { res[0] = num; } res[1] = num; } } return res; }; So why did you write so much code? :D

[@Chr0n0s38]

Your solution would not be accepted because it was `O(n)`. Take a look at the problem description on the left, it wants a `O(log n)` solution. Consider an array of size 10000, yours could (in the worst case) take 10000 iterations (n), while his would take less than 20 (log n).

[@siddhantsharma2779]

in the example array given, first binary search does not find the first instance of 8, it finds the second Final answer will be 6, 7 But the correct answer is 5, 6 Please explain

[@sardorboboshov1797]

a=[] for i in range(len(list)): if list(i)==8: a.append(i) return max(a),min(a) Why we need binary search?

[@asurp7173]

yeah, you dont have to return min max, you just return first position in a list and the last one. Clever solution btw

[@sardorboboshov1797]

@@asurp7173 yes, we can also wright return a[0],a[-1]. Thanks, for attention

[@bear-oh6dc]

Your time complexity is O(N)

[@amreenmazhar]

Sir, How about using binary search to find first occurance... And using jump search left side and right side to find occurances

[@reassume4826]

Thanks a lot for putting videos.

[@gv_1010]

Errichto, can you please break down the intuition on leetcode problems like buy and sell stock and it’s variants in DP . Thank you .

[@Errichto]

I try to break down the intuition for all problems I'm covering on my channel ;p

[@kwakukusi4094]

please don't get angry with my question but why didn't you use equal_range ?

[@Harish-rz4gv]

Why you can't write in python are complete in just 2 lines like this return [nums.index(target), len(nums) - 1 nums[ :: -1].index(target)]

[@nickfeofentov4700]

Wouldn't it breaks if there is no x in your array? First it would return first position of something greater than x (e.g. 9) and then exactly the same position on the second run. Please correct me if I'm wrong.

[@mettudheeraj1393]

I always get compilation error driver not found in leetcode but when i run the same code in intellij it works fine.Can someone help me with this,By the way the error is array.length cannot find symbol[in_Driver_.Java].

[@shadowbanned3136]

interesting. I would have written a for loop with a switch statement inside. for loop scans through every value and returns the first index of the value that matches condition then it goes to the next case and does the same thing this time it breaks when it reaches the end of the array. I initialize the outputs with -1 so it just returns -1,-1 if nothing is found. I haven't written anything yet. I'm ok mobile. It time complexity is the problem I'll jus learn about a searching algorithm and use it.

[@allenjue7562]

Seems like you’re trying to do a strange type of linear search, which in this case you just need to loop through once, no need to break unless it’s the second instance of the target. The problem is it’s not optimal because time complexity is O(n) compared to binary search, which is O(logn)

[@TsArun-qw6xn]

I don't understand why first_pos has to be 'n' instead of -1.

[@muhammedjaabir2609]

here's the code in python : nums = [1,2,3,4,5,6,7,7,8,8,8,9] or nums = [int(input('X : ')) for _ in range(int(input('N : ')))] x = int(input('X : ')) index = [] count = 0 for i in nums: if x == i: index.append(count) count += 1 if index != []: print('Starting index : {} Ending index : {}'.format(index[0] , index[-1])) else: print('The elem {} is not found in the list'.format(x))

[@tarangkapoor8743]

Upper bound and lower bound

[@jugsma6676]

I used hashmap to do, and her's my solution: def find_f_n_l(arr, x): hashmap = {} for i, v in enumerate(arr): lst = [] if v in hashmap: lst.append(hashmap[v][0] + 1) lst.append(i) hashmap[v] = lst else: lst.append(1) lst.append(i) hashmap[v] = lst if x in hashmap: return((hashmap[x][1] - hashmap[x][0])+1, hashmap[x][1]) else: return(-1, -1)

[@pacomarmolejo3492]

Nice vid! How would the algo be modify to count all instances of the target num?

[@debayondharchowdhury2680]

clean and elegant.

[@BonBonShrimp]

You're using C++, right? I know C++ but have done most of my coding in C. Can you recommend some good resources to learn/practice more C++? I know the syntax alright, but I start writing code, C language flows out automatically instead of C++. Btw, what's your opinion on C or C++, vs something like Python? From a job perspective, is it better to market myself as a C++ programmer vs a Python programmer? (I am only learning Python, never used it to write any large code.)

[@khilarihemanshu7581]

From the beginning of the video i was wondering why you haven't mentioned about lower_bound and upper_bound

[@alizine8354]

+1

[@ajmalali1875]

Well the whole point of these questions are about implementing the algorithm itself, not just knowing language features.

[@Errichto]

@@ajmalali1875 Exactly!

[@BonBonShrimp]

I used recursion. I find the middle element (mid) first. If this element matches X, then I make two recursive calls - one for the array elements 'start' through mid-1, and the other for array elements mid+1 through 'end' (where 'start' and 'end' represent the indices of the first and last element of the original array). The first recursive call will return the 'left' position and the second one the 'right' position. What do you think of his approach? What's your opinion on using recursion in general? Thanks.

[@pulkitgupta2009]

In my opinion sir, this would take a lot more steps than the ones taken above. Therefore the program would be inefficient. Recursion is good but usually it leads to having many functions in stack which ultimately causes stack overflow.

[@Chr0n0s38]

@@pulkitgupta2009 If you have the right algorithm, that's not a problem. Tail recursion avoids stack overflows because the function call re-uses the same stack frame (which also means it can be converted into a loop, tail recursion done right is more clear than a loop though in my opinion).

[@SamareshMaity231]

could you please make a video on concept of magic square and its variations.

[@sasankasekharde9835]

Why don't you do a video on the gear that you use to code/build anything? We would love to see it.

[@farhanfuad2898]

I did not hear about team blind?, BUT I SURELY DID ABOUT TEAM ROCKET.

[@mdzaid5925]

Hello, can you please make a video stating important maths topics for programming.

[@sahej97]

Hi Errichto, thanks for the video and the cool explanation. What software do you use to draw your solution? Is it microsoft whiteboard?

[@siddharthmishra8012]

Suppose if we get any position in array and traverse left until we get first value and traverse right until we get different element Can we apply this approach

[@vaibhavmandir2010]

Yes, but it will be slow. Your solution is O(n). Whereas solution in video will be O(log n). Where n is number of elements in array. Correct me if I am wrong.

[@piyush12121]

Hey, What if your 'x' is INT_MAX? Would it still work?

[@yuehuang5639]

Did anyone really try the lower_bound() from stl? seems like it can`t handle the {-1, -1} situation. Here is my naive code : "vector searchRange(vector& a, int x) { auto first = lower_bound(a.begin(), a.end(), x); auto last = lower_bound(a.begin(), a.end(), x + 1) - 1; return {(int)(first - a.begin()), (int)(last - a.begin())}; }" for a = [5,7,7,8,8,10] , x =6, the expected answer is {-1, -1}, but the code generates {1,0}, any suggestion?

[@Lucky_Vaibhav]

If the element is not present lowerbound-a..begin will be equal to upperbound-a.begin . Simply check if they are equal return {-1,-1}

[@David-op8go]

why don't you just loop it and if you find it you save it and the next elemt that's not the search value -1 and there you go

[@vasujain1970]

Love this video!

[@ketanlalcheta4558]

Does normal binary search always gives first element in case duplicate value are present in sorted vector ?

[@mayaki2406]

Hello! someone know why he did low+(high-low)/2 for the mid value instead of high+low/2 ? Okey just did a quick search, in case someone was wondering the same as my its because in C++, Java and other coding languages the integers have a fixed value range so in some cases high and low could be in the value range but their sum produce an overflow.

[@abhinavanand6072]

It's because the value will overflow, suppose high and low is nearly maximum value that data type int can hold , so when we add both ,it won't be able to handle it ,but if we just add simply the difference of them ,we can be saved from overflow.

[@jxggxr_dxv]

He explains in the video why.

[@mayaki2406]

@@jxggxr_dxv Which minute? I don't find it

[@jxggxr_dxv]

@@mayaki2406 Sorry, my bad, indeed is not in this video. I mixed up things. He explains the Binary Search in this video: kzbin.info/www/bejne/fYaadaOdfa6BjbM it should start where he explains why is better to use the formula you mentioned. However, I suggest to watch the full video though, it's a good one. :)

[@mayaki2406]

@@jxggxr_dxv I will do it for sure!! tyvm sir

[@lunaeclipse5768]

*programming is understanding*

[@henrynguyen7143]

I havent watched the full video but i used Binary Search to find the position of the number we are looking for, and then store the index of the number into two integer var, represent for the first and last postition of X. And then, i move the integer (first pos) backward until the previous element in the array doesnt have the same value and i do the same with the integer (last pos) but move forward. Then print them out. Is that a good solution ??

[@riadhossain4020]

Erricto I think e better optimisation with this algorithm might be if we binary search the last_pos only in the subArrary that starts with the index of first_pos and ends at n. What do you think???

[@jalsol]

it's better, but not by much, since binary search itself is already very fast

[@prakash.vishwakarma]

What tool do you use to write to black canvas screen, may be if you're using one note for example, then do you use mouse for writing or do you have touch enabled device?

[@muhamedsufail8089]

arr=[1,2,3,4,4,5,6,7,8,8,8,9] x=4 foundFirst=false for(var i=0;i

[@MrJ4ckie]

Because its much slower in a sorted array. Your code looks at every single element of the array, his essentially halves the number of possible elements with every step it doesnt find x. Not a really distinguishable difference with the example arrays, but using this many times in a row with large arrays will eventually stack up to a noticeable performance improvement.

[@muhamedsufail8089]

@@MrJ4ckie Oh i never thought about performance.. Thank You !!

[@LordLobov]

Modified binary search, two times

[@246rs246]

ja trafiłem tu od joma, fajnie ze Polska w kodowaniu cos znaczy 😀możesz polecić jakieś strony z prostymi zadaniami naprawdę prostymi dla beginnerów do próbowania swoich sił?

[@rakesh4354]

Can we just use lower_bound and upper_bound-1

[@ayushghosh3912]

What if we store each element of the sorted array in a String and use indexOf() and lastIndexOf() I am a java person and i dont know c++ or anything else and i am guessing lastindex and index is in C++....

[@cwagnello]

That's doing a linear scan for the values. It's not as fast a binary search which is log(n). In small arrays the time difference is trivial but in larger arrays the search time becomes significant.

[@yahia1355]

hey ! does solving this question interview (after being called from Facebook ) , make them accept you directly or it increases your chances to be accepted ?

[@slamn222]

the problem can be easily solved with reverse sorting the array no? : z = [2, 3, 5, 6, 7, 8, 8, 8, 12] target = 8 if not(target in z): print([-1, -1]) else: list = [] list.append(z.index(target)) z.sort(reverse=True) list.append(len(z) - 1 - z.index(target)) print(list) NOTE: list.index(element) always returns the smallest index in an array with duplicates of element

[@jounaydguedoura5306]

Za3ma "The problem can be easily solved" Ah doe normaal xD Zebb

[@slamn222]

@@jounaydguedoura5306 haha kowed

[@jounaydguedoura5306]

@@slamn222 ma zyt gy gay?

[@jalsol]

traversing the array is already O(n), sorting it makes it even worse

[@ax5344]

@8:45 I did not quite get it why "first_pos = size_of_array" rather than "first_pos=-1". Tried to repeat several times but still could not. Can someone help?

[@twnhny1994]

I guess this way when your target is not an element of the array, the first position is set to 'size_of_array' so then the second time when you search for index of 'x+1' to find the next element, that index will always be at most 'size_of_array -1' so this way you get {-1, -1} because first > last, and that takes care of any error handling you'd otherwise have to do. I don't know if this is the reason why, but it's what I'm getting out of it.

[@dhairyakhanna4960]

Could you please make a video for preparation of Google Code Jam 2020

[@Errichto]

Solve algo problems, including those from previous editions of Google Code Jam. You're welcome :D

[@abhishekbalawan6817]

Has anyone tried rooftop slushie that Ericto is talking about? How is it?

[@Leon-xg7zj]

What if target is Integer Max Value?

[@Leon-xg7zj]

I figure that out myself. last will be smaller than first, and it will return -1,-1. Thanks!

[@marounayle3697]

Errichto encouraged me to train to become a competitive programmer!

[@zeeu]

will they kick me out if I did this: var searchRange = function(arr, tar) { let first = -1; let last = -1; for(i=0;i

[@ahmedouyahya]

Genius

[@Ichigo-yy2my]

I feel like I m missing something. What if the array is [4 5 6 7 8 8 8 ] Wouldn't this solution return 4 for first -1 for last And ultimately -1,-1

[@souratendupraharaj4287]

He will return N from the function not -1, in your case he will return 4 and 8 which will have final return value as 4,7

[@Ryan-xq3kl]

This code only works for its specific use case just like every facebook related/clickbait coding video you will find EVER

[@contractcenter965]

If our array lenght is n , cant we iterate through our array first (n --> 1) , so the first x here is the last x pos and then revers iteratr , the first x here is the first x pos ?

[@hritwiksom3032]

That is the obvious solution, but it takes O(n) time while this takes O(logn). Basically this is a lot faster...