2
\$\begingroup\$

I am trying to solve the HackerRank New Year Chaos problem where the aim is as follows:

A vector of size n is having values [1,2,3,...,(n-1),n] with no repetition. A kth element can switch only with the (k-1)th element. An element can maximum switch 2 times with its predecessor.

Thus we can say that any kth element should find its place at minimum (k-2)th index

Now, The vector given to the below given function minimumBribes() is the unordered / unsorted one, and I need to find the minimum switched occurred to the sorted vector.

NOTE: If the any element makes more than 2 switches, only print "Too chaotic"

void minimumBribes(vector<int> q) {
  int count = 0;

  for (int p_number = 0; p_number < q.size() - 1; p_number++) {

    if ((p_number+1) != q[p_number]) {
      vector<int>::iterator it = find(q.begin(), q.end(), (p_number+1));
        int index = distance(q.begin(), it);

        for (; index > p_number; index--) {
          if (q[index - 1] - index > 2) {
            cout << "Too chaotic" << endl;
            return;
          } else {
            q[index] = q[index - 1];
            count++;
          }
        }

        q[p_number] = (p_number+1);
    }
  }

  cout << count << endl;
}

The above solution works. but fails for 2 testcases with timeout error.

How to bring down the run time here?

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you please show us the rest of the program? There is not enough code here to review or to offer suggestions for performance improvements. \$\endgroup\$ – pacmaninbw May 14 at 22:57
  • \$\begingroup\$ @pacmaninbw The code running the tests is not up for review, since it's written by HackerRank, not the OP. The rest can be found with the challenge, but I'm not sure including it would be appropriate. \$\endgroup\$ – Mast May 18 at 8:09
2
\$\begingroup\$

Good attempt, but unfortunately the nested loop brings the time complexity to O(n2). Keep in mind that .find performs a linear search on the vector, inspecting up to the entire array to find an element. We can arrive at a O(n) solution by exploiting the fact that no more than 2 swaps can be performed by any given element, which is a red flag in the problem statement that your solution ignores. In other words, we can transform the linear operation inside the array to constant time.

Here's the approach I used:

Start at the back of the array and move forward. For each element q[i] not in its original location, check only q[i-1] and q[i-2] to see if it moved to one of those locations. If the element is in q[i-1], then it must have used only one bribe. If at q[i-2], it must have taken two bribes to get there. Either way, perform an un-swap to return it to its original location. If it's not at either element, the array is "Too chaotic".

Let's try this algorithm on the input examples:

Example 1

initial state: 
[2, 1, 5, 3, 4]

[2, 1, 5, 3, 4]
             ^-- This element should be a 5. Let's look for 5 at index 3 or 2.
[2, 1, 5, 3, 4]
       ^-------- Found 5 at index 2. It must have swapped twice; set `bribes = 2`.
[2, 1, 3, 4, 5]
             ^-- Put 5 where it belongs by undoing the swaps it made.

[2, 1, 3, 4, 5]
          ^-- Moving to the next element, we see 4 is OK.

[2, 1, 3, 4, 5]
       ^-- Moving to the next element, we see 3 is OK.

[2, 1, 3, 4, 5]
    ^-- Moving to the next element, this element should be 2.
[2, 1, 3, 4, 5]
 ^----- Found 2. It must have swapped once; set `bribes = 3`.
[1, 2, 3, 4, 5]
    ^-- Put 2 where it belongs by undoing the swap it made.

Outcome: 3 bribes in total must have happened.

Example 2

initial state:
[2, 5, 1, 3, 4]

[2, 5, 1, 3, 4]
             ^-- This element should be 5. Let's find 5.
[2, 5, 1, 3, 4]
          ^----- This element, q[i-1], is not 5.
[2, 5, 1, 3, 4]
       ^-------- This element, q[i-2], is not 5, either.

Outcome: Too chaotic! 5 must have used more than 2 
         bribes to get any further than index 2.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.