We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The key observation is the person cannot bribe and move ahead more than two spots.
At position i, the person originally at this spot (with value i+1) can now be at index [i-2, n-1] inclusive. The person can only be ahead at most two spot, but can be behind without limit. This observation forces us to iterate in the reverse order.
The idea behind the implementation is to swap the values to undo the bribes so that the array is sorted. This is somewhat like a bubble sort, but remember that we will iterate in reverse order and only have to swap from i to i-2. The runtime is therefore O(N*2) = O(N)
I'm optimizing the code for readability and understandability. You may be able to optimize this so that you don't have to do the swaping.
New Year Chaos
You are viewing a single comment's thread. Return to all comments →
The key observation is the person cannot bribe and move ahead more than two spots.
At position
i
, the person originally at this spot (with valuei+1
) can now be at index [i-2, n-1] inclusive. The person can only be ahead at most two spot, but can be behind without limit. This observation forces us to iterate in the reverse order.The idea behind the implementation is to swap the values to undo the bribes so that the array is sorted. This is somewhat like a bubble sort, but remember that we will iterate in reverse order and only have to swap from
i
toi-2
. The runtime is therefore O(N*2) = O(N)I'm optimizing the code for readability and understandability. You may be able to optimize this so that you don't have to do the swaping.
Kotlin: