Problem

It is New Year’s Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n. Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others.

Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print Too chaotic.

See full description and example input & output in the HackerRank page.

Solution

A person, wearing the number q[i], was initally at position q[i] - 1 (e.g. a person with number 3 was at the index 2 at first). The person can bribe others at most twice, so the person can move left at most 2 positions. When inspect the list, we compare each person’s original position, i.e. q[i] - 1, with the current position i, if (q[i] - 1) - i is greater than 2, then this person bribes too many people. Our program prints Too chaotic in this case.

Next, we calculate how many bribes happen. Say, the initial list is:

  1 2 3 4 5

And, its current state is:

  1 2 5 3 4

For every person X, we check people in the left of this person, if any of them’s number is greater than X’s, then that person must bribe X.

Below is a Java version solution.

public static void minimumBribes(List<Integer> q) {
    int bribes = 0;
    for (int i = 0; i < q.size(); i++) {
        if (q.get(i) - 1 - i > 2) { // this person has done too many bribes
            System.out.println("Too chaotic");
            return;
        } else {
            for (int j = 0; j < i; j++) {
                // for every person in the left of "person q[i]", 
                // if that person's number is greater, 
                // than "person q[i]" got bribed by that person.
                if (q.get(j) > q.get(i)) {
                    bribes++;
                }
            }
        }
    }
    System.out.println(bribes);
}

Time complexity is O(n^2).

An Optimization

When calculate bribes, the above solution has done many unnecessary checks. A person X, wearing the number q[i], was initally at position q[i] - 1. People, who were in the right of X, can do bribe to be positioned at q[i] - 1 or q[i] - 2. The bribe limit is 2, it’s impossible for people who were in the right of X to be at index less than q[i] - 2. So we can improve the previous solution to let j start with q[i] - 2. The value q[i] - 2 may be negative, to avoid the out-of-bound exception, let j start with 0 when q[i] - 2 is negative.

public static void minimumBribes(List<Integer> q) {
    int bribes = 0;
    for (int i = 0; i < q.size(); i++) {
        if (q.get(i) - 1 - i > 2) {
            System.out.println("Too chaotic");
            return;
        } else {
            int j = Math.max(0, q.get(i) - 2);
            while (j < i) {
                if (q.get(j) > q.get(i)) {
                    bribes++;
                }
                j++;
            }
        }
    }
    System.out.println(bribes);
}

Note that, you can add another check, q.get(i) - 1 == i. In this case, the person hasn’t change the position, so no bribe happens on this person. We can skip bribe calculation in this case.

Problem

You are given an unordered array consisting of consecutive integers [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

See full description and example input & output in the HackerRank page.

Solution

Starting with 1, try to put each number in correct position. If a number is not at the correct position, a swap is needed. For example, with the following input,

4 3 1 2

1 is not in correct position (correct position is index 0). Therefore, swap 1 with the element at index 0, which is 4. After 1 is positioned correctly, check the next number, i.e. 2.

We can use hash map for the lookup of current position of a number.

Below is a Java version solution.

    static int minimumSwaps(int[] arr) {
        // the value space is [1, n], so we can use array to 
        // store the mapping between number and its position
        int[] posMap = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            posMap[arr[i]] = i;
        }
        
        int swapCount = 0;
        for (int num = 1; num <= arr.length; num++) {
            int correctPos = num - 1;
            int currentPos = posMap[num];
            if (currentPos != correctPos) {
                int tmp = arr[correctPos];
                arr[correctPos] = num;
                arr[currentPos] = tmp;
                
                // update 'pos map'
                posMap[num] = correctPos;
                posMap[tmp] = currentPos;
                
                swapCount++;
            }
        }
        return swapCount;
    }

Time complexity is O(n).