3
\$\begingroup\$

Similar to this question but this is for Python

Original problem with description on hacker rank

I am currently trying to iterate through a large number of arrays and count how many times numbers have been swapped.

A sorted array looks like this: [1,2,3,4,5] and a number can be swapped only towards the front (counting down to 0) twice.

If a number is more than 2 out of order the array is deemed 'Too chaotic' and the process should stop.

Instead of bubble sorting I am simply going through and counting the actual swaps. As a sorted array is not actually required, my code works except for a couple of the tests where it times out due to large arrays.

Any ideas on how to speed this process up?

function minimumBribes(q) {
console.log(sort(q));

    function sort(items) {
     let bribes = 0;

     for (let i = 0; i < items.length; i++) {
         if (items[i] - (i + 1) > 2) return "Too chaotic";
         for (let j = 0; j < i; j++) {
             if (items[j] > items[i]) bribes++;
         }
     } 
     return bribes;
   }
}
\$\endgroup\$
2
\$\begingroup\$

Reduce the inner loops iteration count.

The problem is the inner loop is looping over too many items. The result is that you spend too much time processing data you know is irrelevant.

As the function should exit if it detects a position has made over 2 bribes, you need only have the inner loop check positions down 2 from the item you are checking, and not from the start of the line.

Quicker solution

It only requires a slight modification of your code, but as you have complicated the situation by calling an inner function sort the example has just removed the inner function.

The line for (j = pos-2; j < i; j++) { is where the improvement is with pos being item[i] in your function.

function minBribe(queue) {
    var bribes = 0, i, j;
    for (i = 0; i < queue.length; i++) {
        const pos = queue[i], at = i + 1;
        if (pos - i + 1 > 2) { return "Too chaotic" } 
        for (j = pos-2; j < i; j++) {
            if (queue[j] > pos) { bribes++ }
        }
    } 
    return bribes;
}

This brings the solution down from \$O(n^2)\$ to near \$O(n)\$ however the number of bribes is a factor so its closer to \$O(n + (m^{0.5}/2))\$ where \$m\$ is the number of bribes. (this is only an approximation)

\$\endgroup\$
3
\$\begingroup\$

You don't need to compare any two elements. Just compare the array values (the sticker) with the index of the array. Keep in mind that the sticker is one-based and the index is zero-based.

minimumBribes = q => {
    const bribes = q.reduce( (bribes, assigned, actual, too_chaotic) => { 
        const distance = assigned - 1 - actual
        if (distance>2) too_chaotic=true
        else return bribes + distance*(distance>0)
    }, 0);
    return isNaN(bribes) ? "Too chaotic" : bribes;
}

The break-out-of-reduce trick is taken from this highly informative post.

\$\endgroup\$
  • \$\begingroup\$ Do you only set too_chaotic to true so you would not have an empty if bracket? From what I can tell it doesn't change the code.. Also never knew about this hack, very interesting \$\endgroup\$ – Roland Apr 22 at 11:25
  • \$\begingroup\$ FYI this answer is actually a little off, array [1, 2, 5, 3, 7, 8, 6, 4] is meant to return 7, your solution returns 6. Works for several other use cases though \$\endgroup\$ – Roland Apr 22 at 11:38
  • 1
    \$\begingroup\$ 4th argument to reduce is source array q. Changing it terminates reduce immediately. If you simply return nothing (without changing q), the reduce runs to completion instead (slower). You could name it orderly, set false on chaos, then the final condition would be return q ? bribes : "Too chaotic", as q-the-array is always true while your assigned value is always false. I see what you mean that someone who pays bribes but accepts more than paid will be uncounted. You can still avoid comparisons: when you get to 6 you know you're supposed to be seeing 4 and thus there's another bribe. \$\endgroup\$ – Oh My Goodness Apr 22 at 12:22
  • \$\begingroup\$ Your break out does not work. You need to mutate the array. too_chaotic is a reference, assigning a new value to it does not mutate the array, it just overwrites the reference. To breakout you can change the array size to <= actual (also the sign of distance is neg) Thus to break out you need to mutate the array with if(distance <= -2) { too_chaotic.length = 0 } Also very poor name selection for array reference, random semicolon use, and the fact the function fails to return the correct result and I would -1 if the answer was not to be corrected \$\endgroup\$ – Blindman67 Apr 22 at 15:44
  • \$\begingroup\$ -1, your approach is incorrect for 1 2 5 3 7 8 6 4, it should return 7 but returns 6 \$\endgroup\$ – konijn Apr 23 at 17:42

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.