HackerRank Interview Prep - Problem 7: New Year Chaos

Solution at:
Hello, my name is Brian Dyck, I am a full-time software engineer and a Computer Science graduate walking through HackerRank problems for new and old programmers alike. My goal is to help programmers build up skills and not just see the solutions to problems, but to learn how to think through the problems. Many new videos to come, so stay tuned!
Problem Arrays: New Year Chaos
Description:
It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to n at the back.
Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n = 8 and Person 5 bribes Person 4, the queue will look like this: 1, 2, 3, 5, 4, 6, 7, 8.
Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

[@astroswell]

Thanks for the solution! It's the best one I've seen so far. Explanation for those who don't understand it:
Let's say we have a sequence 1 2 5 3 7 8 6 4.
Values p1, p2, p3 represents a 3 values window(I'll call it just "P" for shortness) that we “slide” through the sequence and check if it matches our expectations of what the current 3 values of the sequence should be.
At the beginning P is [1,2,3] because at the beginning of the sequence we expect 1,2,3;
We start looping through the sequence:
at 1: we see that it's at the 1 slot of the P where it is supposed to be. Then we're "sliding" P right 1 item, now we expect that the next 3 values of the sequence is [2,3,4]
at 2: again, 2 matches our expectation, at it's the first value of P; we "slide" right again, now we expect P to point at [3,4,5]
at 5: we see that it's not matching p1, neither does it matches p2, but it matches p3. It means that 5 is too positions ahead of what we expected so it means it bribed 2 people in front of him. Now after “sliding” we expect that we P is pointing to [3,4,6] because we know if 5 jumped 2 people ahead then after 4 should go 6
at 3: indeed 3 is where it is supposed to be. Sliding further we expect [4,6,7]
at 7: we see that 7 is 2 spots ahead of where we expect it to be. Means bribed 2 people. Sliding right one slot we now expect [4,6,8]
at 8: again, 8 is 2 spots ahead. Bribed 2 people. We now expect the next three values be [4,6,9]
at 6: something new. 6 is one place ahead of where we expect it(bribed 1 person) meaning that the next values should be [4,9,10]
at 4: 4 is where we expect it to be. No bribes
End of the loop.
Total of 7 bribes.
If you have further questions let me know ;)

[@animemusicvideo105]

you summed it up really well! Thanks a lot!

[@prithvib8662]

Excellent video! Best solution for this problem I've seen by far.
Just wanted to add some explanations for some unspoken assumptions/code you wrote that viewers might be confused on:
Hypothetical Question: Why are there only p1,p2,p3? Why not p4,p5,... as well?
Answer: We only need to track 3 variables because any given person can only bribe someone in front of them twice. This leaves us with the initial position, the position in front of us, and the position two spots in front of us.

[@codingbru]

The solution seems pretty simple now compare to what I was doing! I subtracted all the values of p by one so it matched with index 0 and was adding the difference between loop variable 'i' and q[i]. Your method covers the edge cases also. However I don't really think I could have come up with your solution on my own. Can you explain a little more of your thought process on how you came to the logic you used. I get the logic but I want to learn how to make such logic myself. Thanks!

[@mcaddit6802]

Awesome way to explain bro.
Result: You have added 1 Subscriber Successfully!!

[@briandyck8828]

Thank you so much 🙂

[@paulepstein9739]

Hi Brian, Thanks. this is the best algo I've seen for this solution. However, there's an important error in your presentation for C++ specialists. Omitting unsigned does not and should not give a compile error -- just a warning. for(int i = 0; i < vec.size(); ++i) is a perfectly standard C++ idiom. I would ignore such a warning. That warning is there for this kind of situation which is quite different:
std::vector v;
if (-1 > v.size())
std::cout

[@sadiqali1831]

wow bro how did you get to that solution! so beautiful and elegant!

[@briandyck8828]

Thanks! I had to do a lot of these types of problems in school, so I just got used to it I suppose.

[@ashisenchoudhury162]

You are awesome! I am not familiar with C++ at all but I understood your algorithm and coding. Thanks.

[@briandyck8828]

Glad it was able to help you out! That's the beauty of object oriented programming languages, the logic naturally flows to other OOP languages just changing of syntax.

[@ashisenchoudhury162]

@@briandyck8828 Yes actually 😊... Thanks a lot

[@cyngtr]

fucken genius, i almost shat my pants watching this

[@paulepstein9739]

Hi Brian, you said (something like) "I don't understand what this means about 60% for n less than 1000 and 100% for n < 100,000". I do understand this. 60% credit for solutions that work but are suboptimal in terms of big O. Full credit for optimal solutions. A correct solution is assumed not to time out for n

[@hemanthvemuluri9997]

Thanks for the simple and efficient code.

[@cuongme626]

Awesome! Much simpler than my solution and well explained!

[@caliber9250]

Great Videos!!!

[@briandyck8828]

Thank you!

[@imanmohamadi2827]

Hey bro, Nice job. Do you know the name of most similar algorithm? I'd like to study a little bit more around this topic and solve more similar problems.

[@briandyck8828]

Not off the top of my head, but I can see if I can find it. Sorry, I did not see this sooner.

[@imanmohamadi2827]

@@briandyck8828 no worries, I don't expect you to answer all the comments 😄👍🏼

[@jasonguo3095]

@@briandyck8828 Isn't it Sliding Window pattern with three pointers + Dynamic Programing (bottom-up approach) pattern? We use three integers to memorize the current solution and slide the three pointers to right by one position.

[@coderluffy6387]

very hard to understand the logic, graphics and slow pace could help

[@mcaddit6802]

Sorry to say but it only pass test 3, could you pls help me. i got your logic but it passes only 3rd test case

[@briandyck8828]

Are you solving in C++ or a different language? And did you copy the code exactly, or did you change something and simply followed the logic?

[@mcaddit6802]

@@briandyck8828yes used C++. used your logic same code, pls check the code problem of mine
Thanks

[@briandyck8828]

@@mcaddit6802 Well, I just made a new account, and passed again.. here is the code I used:
// Complete the minimumBribes function below.
void minimumBribes(vector q)
{
int swap = 0;
int bribes;
int pos = 0;
for (int i = q.size() - 1; i >= 0; --i)
{
int j = 0;
bribes = q[pos] - (pos + 1);
if(bribes > 2)
{
cout

[@briandyck8828]

Try using that, and let me know if that works...

[@mcaddit6802]

@@briandyck8828 It worked, but i confuse that why that code is not working as that code seems easier than this one.

[@林千凯]

I don't understand.

[@briandyck8828]

I’m sorry 😅 perhaps if you elaborate on what part is confusing I can help you