C++ First Missing Int, faster than 100%!

First Missing Positive Int problem in C++.
This time we use a single-pass algorithm that has the correct big-O time and space requirements.
― mCoding with James Murphy (mcoding.io)
Source code: github.com/mCo...
Previous video: • Find the First Missing...
SUPPORT ME ⭐
---------------------------------------------------
Patreon: / mcoding
Paypal: www.paypal.com...
Other donations: mcoding.io/donate
BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------
Discord: / discord
Github: github.com/mCo...
Reddit: / mcoding
Facebook: / james.mcoding

[@bala3508]

I'm a beginner .Learnt a lot from your last few vids. Keep up the good work :)

[@mCoding]

Thanks, will do!

[@etopowertwon]

That reminds 100 prisoners puzzles where the strategy is to put numbers in the places they are supposed to be.

[@rammsund]

The audio sounds kinda muffled, not sure how to describe it

[@Ganerrr]

muffled

[@deViant14]

Looking back on earlier videos it's surprising there weren't more problems what with the mic being so far out of position.

[@mCoding]

*Audio knowledgeable people please read!* I am having so much trouble with my audio setup. It's definitely an issue, but I'm not exactly sure what the source of the problem is. I've heard that it could be mic placement, mic hardware (I'm using a SpeechWare FlexyMike), or not equalizing/compressing properly. If you have recommendations or better yet if you are willing to troubleshoot with me, please reach out! I want to get this fixed to improve the quality of my videos.

[@soer7022]

@@mCoding Would recommend getting a studio mic, like a blue yeti or something on a boom arm, it often has way better quality and control of the sound than normal microphones :)

[@Alex-kh8zj]

@@mCoding ​ @mCoding eq out the low end, add a little reverb heres my attempt: check my channel for it since youtube is deleting the link

[@ShreyasRavibighero6]

Oh, I just made a new array that stores the count of each number at that index, i.e. the occurrences of the number '1' would be stored in count[1], then I just find the first one that is 0. I thought that was quite elegant until I saw this. Excellent solution!

[@fazex4185]

Yours is cool too

[@electra_]

Nice! The previous solution seemed unsatisfying, this one is super smart!

[@mCoding]

Glad you think so! Unfortunately in real code the other solution is likely more useful because this kind of function should really not be modifying its argument... But a problem's a problem!

[@trulyUnAssuming]

@@mCoding if you instantiate a second vector with zeros and write the numbers in there you can just scan that for a zero I guess. So it doesn't seem like the inplace overriding is inherent to this algorithm

[@brunch.]

@@trulyUnAssuming making a scratch vector would impact the efficiency of the solution so its not something that can be done for free. Although it is still probably worth it, but depends on the use case. (ofc still linear time) edit: nvm i believe i read somewhere further down in the comments that there is also a space requirement for the problem

[@georgioschatzigiannis5206]

OK i m guessing im missing something. but wouldnt be enough just to find the minimum of the input? so the extra space is just a long long, you go through the list only once and you check if the element in the list is positive and smaller than the buffered number

[@nikitamyazin6586]

If you have input like 1, 2, 3, 5, 6 then your answer should be 4. If you just find a minimum then you will return 1, right? But that's not the correct answer. And neither 2 or 3, for example. The task is to find missing minimal element in the input, not just the minimal element in the input.

[@usuyus]

I'd solve this using DSU which would use O(n * alpha(n)) time and O(n) extra space. Every number in the array that we care about merges i-1 and i in the DSU, then we just return the size corresponding to the 0th set. This may run worse because of the alpha term + the extra O(n) memory, but I think this would be another cool solution for this problem :)

[@mCoding]

This solution is O(n) time and O(1) space! But thanks for the alternative solution.

[@joseville]

Hey! This would work with a few caveats. 1. You need to make sure you ignore negative numbers, otherwise the 0th disjoint set could be for a range of negative numbers. 2. You would need to check for the special case that the 0th disjoint set doesn't start at 1, in which case the answer is 1. Another way to deal with this is to force a `0` in there. --- Noting all that, you'd be doing a lot of unnecessary work to compute all the other disjoint sets. There is a better way where you manually maintain what would be 0th disjoint set. If interested, I can share the code for that solution.

[@mr.mirror1213]

In the for loop, I should be long long right, doesn't this over flow for Large N?

[@mCoding]

I didn't mention in the vid, but the problem statement restricts the input to 32-bit ints, so long long, which is at least 64 bits, is sufficient for this problem.

[@sophiacristina]

Sorry if i'm being annoying, but, if N reaches a number that is covered by "long long", wouldn't "i" modulo itself if it reaches over "int" distance?

[@IamusTheFox]

Do I get bonus points if I can do it in one line? auto sort_find(std::vector v){ std::sort(v); long long counter; for(auto const & e : v) if(v != ++counter) return v;}

[@mCoding]

Yes you do! But the std::sort prevents the algorithm from being linear time as the problem suggests :(

[@IamusTheFox]

@@mCoding my bad. Just make it consteval? Lol.

[@cottawalla]

I did that in my very first programming assignment at uni back in 1980 and got marks taken off. Never again thereafter. Putting multiple statements on one line is pointless unless you want to make your code unreadable. Same with trying obscure syntax tricks. The compiler will do a better job than you optimising your code. Your job is to get the logic correct and make it readable (ie, reflect the logic clearly) so that others can more easily spot the errors that you're going to make.

[@IamusTheFox]

@@cottawalla In school they had you coding in youtube comments? Edit: That was a joke, and I don't mean to take away from anything you said. You're basically right in all counts.

[@cottawalla]

@@IamusTheFox The better example, assuming I get the joke, would have been Twitter comments. That, as they say, would have been "pure luxury" in a Yorkshire accent. We could only dream of 140 characters.

[@user-wv1in4pz2w]

really clever solution. The only thing i can think of to make it potentially faster is using parallelism.

[@mCoding]

I don't see how this algorithm could be parallelized since it jumps all around the array dependent on the data. Could you elaborate?

[@user-wv1in4pz2w]

@@mCoding this actually should not matter. At every point each element of the array is either the original number or its place. Each element only ever changes to be its place if at all. So if two parallel branches jump to the same place, one of them will take the number and modify it, and the other will see that the number is the same and stop. Then you just need to have a number that is points to the first number which no thread dealt with yet and then you can have a pool of however many threads you want doing the work.

[@user-wv1in4pz2w]

@@caedenw imma be honest, I don't have experience with low level parallelism, but isn't this what atomic operations are for?

[@leonardovegetti]

why would you make a class?

[@imulion668]

Is there a reason why this wouldn't work in python ? or why it would be slower then the original solution ?

[@quintium1]

This should also work in Python, maybe he just chose C++ because it's generally faster than Python.

[@mCoding]

The algorithm is fine in Python. But I already made that video, so I thought I would give viewers at least something new to look at since I already covered this problem in Python.

[@7minutesdead]

@@mCoding For what it's worth, I do come here for the python content haha.

[@eggmeister6641]

python bad. c good. nuff said

[@jullien191]

Que es el nombre de este algoritmo? Por que es el for i in range(1, n+1): If i not in nums: print(i); exit(0) más lento?

[@OmegaMusicYT]

El "i not in nums" tiene que buscar en la toda lista (coste n) n veces para saber si "i" está en ella. Lo que da un coste total de n^2

[@sahil8565]

what is that curr != (next=nums[curr-1]) ? could you please do the assignment annd comparison in 2 different statements , i can't understannd this

[@mCoding]

In C++ something like a=b doesnt just assign b to a, it also returns b, so c != (a=b) assigns the value of b to a and also checks if c != b at the same time. This is a common idiom in C++ that often confuses beginners, but it's an important feature of the language that one needs to learn.

[@beelzebub3920]

wouldnt it be faster if you just remove the negative numbers and then create an array that starts at 1 and finishes at the length of nums, then you sum that array, and then you just take the difference from the sum of the input array(with the negative numbers removed) and the sum of the other array maybe im just not getting something

[@Jyashintaan]

If there is only 1 missing integer then yes, in that case we can solve this using (1+num)*num/2 - (sum of input - value of the negative) and we will have desired number (num being the length of input).

[@mCoding]

Indeed, this assumes *only* one is missing and perhaps no duplicates as well.

[@michaelflynn6952]

is it forbidden to create an auxilliary array to store some kind of vector of indices? seems like this method does a lot of moving values around. I also don't know very much C++ so maybe what I propose is no faster.

[@mCoding]

Indeed, the problem had an O(1) space requirement.

[@OMGclueless]

And in practice, the actual runtime of an algorithm like this is likely to be dominated by cache misses. So adding an extra array of indices will almost certainly be slower.

[@michaelflynn6952]

@@mCoding love it, great work then

[@zoltankurti]

@@mCoding just hard code an uint32_max length vector, should only require 8 gigs and is O(1) in memory!

[@zoltankurti]

@@OMGclueless there is plenty of jumping around in this code. You could use a 1bit per number index vector, that would be 32 times smaller than the input one, and so maybe it would even be better from a cache perspective. Depending on the cache size the index vector could maybe stay cached during the entire run, and due to the predictable access pattern on the input vector the relevant parts of it could be very cache efficient even if it doesn't fit into the cache as a whole. Should also have less conditional jumps. If I had to bet, a 1bit/number index array would be faster.

[@rintepis9290]

Great video. However, technically speaking, modifying the input array does count as using additional space when the question doesn't ask for it. EDIT: That is what I learned in my algorithm analysis class. I guess it is not the case with LeetCode then.

[@bean_TM]

isnt this basically a modification to an insertion sort algorithm?

[@JNCressey]

I think it looks more like cycle sort. Insertion sort shifts the top elements of the partial result on every insertion. Cycle sort assumes you know the final index of the values, and moves each element only one or zero times.

[@atilacorreia]

Can't both of your "for loops" be done front (incrementing as you did) and backwards (decrementing)?

[@atilacorreia]

@flareragnarok Maybe you are misunderstanding my question. I'm asking if, for example, the last for loop could be done incrementing and decrementing at the same time, reducing the time to loop by half.

[@brunch.]

@@atilacorreia sure but you are still doing the same number of calculations.. so it doesnt improve looping time, only the number of loops. but the number of loops dont inherently matter especially because O(n/2) = O(n) anyways even if you could cut the calculations in half, which you havent. so youd just be adding unnecessary complexity

[@atilacorreia]

@@brunch. I asked if it "can be done", not if it would 'reduce the order of complexity of the algorithm'. The code would be faster (even tho a little more complex).

[@brunch.]

@@atilacorreia no it wouldnt be faster. Thats what im trying to explain to you. Going through 10 loops is not inherently faster than 20 loops if you do more things in the 10 loops than the 20 loops. If you looped through 20 times and did 1 thing each time, versus looping through 10 things doing double the amount of work each time, you are not saving yourself really any work. The order notation is still O(n/2) for the loop which is still O(n) in practice and the coefficients of your function will simply be higher. Be careful to not conflate stopping at the middle with doing half of the operations. Youre still doing all of them how you explained it.

[@liorbm1]

This is from leetcode ? Why didnt mention the problem number ?

[@mCoding]

I think search engines are good enough that you can find it :)

[@liorbm1]

@@mCoding Yeah, I found it in my first try... :-) cool channel !

[@shivanshshalabh]

Me trying to find int main()🧐

[@-dubu]

For 10k subs maybe you can get a mic that doesn't suck ;)

[@mCoding]

Last week I only had 100 subs but I get your drift! New mic shipping as we speak.

[@TheSaintsVEVO]

@@mCoding Damn, nice growth!

[@larsheyden4077]

Simpler and faster solution: just sum up the numbers in the array and subtract the result from N(N+1)/2 where N is the size of the array. For example: 3 + 4 + 1 + 5 = 13, 5*(5+1)/2 = 15; 15 - 13 = 2. If the difference is zero then the missing number is N + 1.

[@brunch.]

you are assuming there are no duplicates and only a single missing number, which we dont know for sure

[@Bodyja]

I guess it doesn't matter because this is just a competitive problem, but if this was production code your algorithm is kinda bad because you are modifying your input, so you should either take it as copy or as a move value, so the user of the function knows that his data will get consumed. Either way, it still is a algorithm that may be pretty useful on the future, so thanks 😊

[@mCoding]

Maybe I'm too pedantic about const-correctness, but the interface didn't specify the input is const, and to me that says please eat the input, I don't need it anymore.

[@somerandompersonintheinternet]

Indeed, non-const input is fair game in my book, so it's not really the algorithm's fault. Having said that, this interface is kinda bad for modern standards. A better one would be simply using a vector as a parameter, rather than a vector&. Then the user of the api could choose to either copy or move as they see fit. Again, just to make it clear, the interface is part of the problem description here, not of the actual submission, so it's not the fault of whoever is writing the algorithm.

[@noonari]

Code has bugs, Submitted your code on same problem on leetcode, it failed test cases.

[@mCoding]

I tried resubmitting it 2 times and mine still passes. Perhaps you copied it in incorrectly. Note that you need to include the vector header.

[@happygimp0]

A long long int is not necessarly bigger than int. Sizes should be stored in size_t not int, not long, not unsigned long not unsigned long long or any other crap. When N>INT_MAX, you get UB because i will overflow.

[@mCoding]

Your suggestion is not correct. This wasn't mentioned in the video, but the problem statement guarantees that -2^31 = 0. The implicit conversion of n-1 to a size_t when plugging it into the array index is also fine because we have guaranteed the value we are converting is nonnegative.

[@markcuello5]

HELP

[@neonzoff]

можно еще оптимизировать на 1 такт процессора!

[@janknoblich4129]

Something is wrong with the audio sadly.

[@jojojorisjhjosef]

Your mouth makes the sound, not your eyes.