hackerrank new year chaos code optimization
<p>I'm trying to optimize my solution for <a href="https://www.hackerrank.com/challenges/new-year-chaos/problem" rel="noreferrer">Hackerranks's 'New Year Chaos' problem</a>. The gist of the problem goes like this</p>
<blockquote>
<p>There's a queue of n people, labeled 1 through n, and each person can bribe the person directly in front of them to swap places and get closer to the front of the queue (in this case, index 0 of the list/array). Each person can only bribe a maximum of two times (and they cannot bribe someone who has already bribed them)</p>
<p>You are given the order of the people after all of the bribes have taken place and your job is to determine how many bribes took place to get to that point. For example, if you were given [3, 2, 1] then the answer would be 3 bribes (person 3 bribed person 1, 2 and person 2 bribed person 1).</p>
</blockquote>
<p>My solution was, for each person I, count the number of people to the left of I that have a label greater than I (they would've had to bribe person I to get to the left of them). To complicate things (slightly), some of the test cases given would only be possible if someone bribed more than 2 times (i.e. [4, 1, 2, 3] - person 4 bribed person 3, then 2, then 1 to get to the front). If this is the case, simply output &quot;Too chaotic&quot;</p>
<p>Anyway here's the code:</p>
<pre><code># n is the number of people in the list
# q is the order of the people after the bribery has taken place ex. [1, 3, 2, 5, 4]

for I in range(1, n + 1): # for each person I in the list
    index = q.index(I)
    if I - index &gt; 3: # more than two bribes
        bribes = &quot;Too chaotic&quot;
        break
    for j in range(index): # for each number to the left of I, if greater than I, count it as a bribe
        if q[j] &gt; I: 
            bribes = bribes + 1
print bribes
</code></pre>
<p>My problem is that the code times out with some of the larger test cases (you're only given so much time for each test case to run). How can I optimize the algorithm so that it doesn't time out? Should I be trying this problem in another language?</p>