Algorithm Time: Minimum Swaps

Today I'm going to dive into my solution to HackerRank's "New Year Chaos" problem, written in JavaScript.

I found this one rather challenging to wrap my head around, and none of the solutions in the 'discussions' section were as thorough as I wanted them to be. The closest is this one, but it was in a language I'm not as familiar with, and could use some more breaking down.

So here we go. The setup is like this: There are a bunch of people waiting in line, each assigned a number, beginning with 1 at the start of the queue, and so on. This can be represented simply with a row of numbers like this:
1 2 3 4 5 6

Before the event, each person can choose to bribe the person in front of them to swap spots, so that they can move up. Each person can do this up to 2 times. So say person 3 bribes person 2, the queue will now look like this:
1 3 2 4 5 6

That's the setup, here's the challenge. You are provided with a list of numbers representing a queue of people that has undergone this bribing process. Your job is to return the minimum number of swaps required to get the line to that state. Or, if that state is not possible, to return "Too Chaotic."

First let's handle the "Too Chaotic" condition, since that's simplest. If a person has ended up more than two spots closer to the front, you know it's too chaotic. They cannot bribe more than twice, and people can't bribe anyone behind them, so they can only move forward on their own bribes. Here's an example of an input that's too chaotic:

1 5 4 2 3 Person number 5 doesn't have enough bribes to get that far up!

Figuring out the minimum bribes is quite a bit trickier. Tallying how many people have moved won't work, because a single transaction moves two people. Counting how many bribes each person has made won't work for similar reasons. What you can do, however, is count how many times each person has been bribed, and add those up.

In 1 2 5 4 3 for example, 3 has received two bribes, 4 has received one, and none of the others have received any. We know this because among the people just to the left of 3, there are two numbers higher than 3. To the left of 4, only one number is higher. Adding up the counts, we get a minimum bribe count of 3.

It is possible that a couple more bribes than this happened, of course, and in the final standings you cannot see them. For instance, perhaps 2 bribed 1, but then 1 bribed 2. However, since we are only interested in the minimum number of swaps necessary, we don't need to worry about those circumstances.

So how do we turn this into code? Let's take it one step at a time. First, we'll initiate our bribe count at 0. Next, we know we'll need to loop through each person in the list to find their count, so let's set that up.

function minimumBribes(q) { // q is our... queue! In the form of an array.
    let minBribes = 0;
    for(let i=0; i < q.length; i++){ 

    }    
    return minBribes;
}

We will need to check each person to see if their position means our queue is too chaotic. If their number is more than 2 higher than their position, they've moved too far.

function minimumBribes(q) {
    let minBribes = 0;
    for(let i=0; i < q.length; i++){
        if (q[i] - 3 > i){ //It's -3 not -2 here because 
                           //our queue starts at 1
                           //while our array index starts at 0
            return "Too chaotic"
        }
    }    
    return minBribes
}

Next, we'll need to add one to our minimum bribes count for every time someone was overtaken. Once we add that in, the function is complete:

function minimumBribes(q) {
    let minBribes = 0;
    for(let i=0; i < q.length; i++){
        if (q[i] - 3 > i){
            console.log("Too chaotic")
            return
        } else {
            for (let j = Math.max(0, q[i]-2); j < i; j++){
                if (q[j] > q[i]){
                    minBribes++
                }
            }
        }
    }    
    return minBribes
}

But there's a lot going on there, so let's break it down. Here's just the internal loop:

for (let j = Math.max(0, q[i]-2); j < i; j++){
                if (q[j] > q[i]){
                    minBribes++
                }
            }

Remember that i is the position of the person we are currently considering, the one receiving bribes, the bribee. j represents where we begin examining the line to see who has bribed our bribee. The briber cannot move further than one position in front of the bribee's original position. On the first bribe, they take the bribee's position, on the second bribe, they move one past it. So, we only need to look two positions to the left of i. (Theoretically this would work with simply j=0, but that bumps our run time from O(n) up to O(n²). This cut saves us quite a bit of runtime.)

So what's this Math.max(0, q[i]-2) nonsense? Looks complicated, but all it's doing is protecting us from accidentally entering a negative index. j will be set to whichever is larger, 0 or 1 before the bribee's original position (it's -2 to account for the one-indexing).

The loops end condition is j < i. We only need to look at people to the bribee's left.

Now, if any of those people have a number higher than our bribee (if q[j] > q[i]), we know they must have bribed them to get there, so we add one to our minimum bribes count (minBribes++).

And that's it! This may still not be terribly clear, but I'm hoping that I've been able to explain each piece well. I really wanted to understand both how this worked, and why it worked, so I'm glad to have taken this time to write it out.