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\$

3 Answers 3

5
\$\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 - at > 2) { return "Too chaotic" } 
        for (j = Math.max(0, 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\$
1
  • \$\begingroup\$ Adding one clarification why J will start from j = Math.max(0, pos - 2) is that, in any case numbers which are greater to current one can jump only two position ahead of actual position of current number. \$\endgroup\$ Mar 5, 2021 at 20:11
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\$
6
  • \$\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, 2019 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, 2019 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\$ Apr 22, 2019 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, 2019 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, 2019 at 17:42
-1
\$\begingroup\$

The input array is: [1 2 5 3 7 8 6 4], which means that:

  • 5 jumps 2 positions, so increment counter by 2 (c = 2)
  • 7 jumps 2 positions, so increment counter by 2 (c = 4)
  • 8 jumps 2 positions, so increment counter by 2 (c = 6)
  • Then, 6 is ahead of 4, but it is at index 5, so it had to jump at least one position. So, counter should be incremented 1 (c = 7), BUT the logic in the reduce method doesn't catch it, bc the value is greater than the index it is at.

Additional logic to catch the edge case where a value was pushed backwards, but also swaps places needs to be considered.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ On the code review site we are generally trying to help improve coding ability. We do this by making insightful observations about the code rather than providing new algorithms. \$\endgroup\$
    – pacmaninbw
    May 4 at 15:21
  • \$\begingroup\$ Are you suggesting that my comment provides the algorithm? It is just a note about stepping through the logic with an example. Confused by your note. Thank you! \$\endgroup\$
    – caro_codes
    May 6 at 14:58
  • 4
    \$\begingroup\$ Your post is not a comment but an answer. This thing that I'm writing now is a comment. Your answer seems some what disjunct from the code that it is supposedly reviewing. At best, it might be considered the beginnings of a proposal to make an alternative solution. But what's really wanted is an observation about the original code. With such an observation, you might then follow up with your observations about how the code could work. \$\endgroup\$
    – mdfst13
    May 6 at 15:34

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