Problem statement

https://leetcode.com/problems/moving-stones-until-consecutive-ii/

Solution

Actually this is more difficult version of problem 2009. Minimum Number of Operations to Make Array Continuous, and this is medium difficult and that problem is hard, it is not very honest. This problem can be splitted into two separate problems:

  1. Find maximum number of steps: for this we can use the following strategy: sort numbers, say we have [1, 3, 6, 7, 10, 20]. Then choose the minimum value between 1, 3 and 10, 20: on the first step we have only this choice. Then on each step we can reduce difference between biggest and smallest element by 1.
  2. To find minimum number of steps we use problem 2009 but with some remarks. There are two cases, when we can not make number of steps predicted by this problem. If we have x, x+1, x+2, ... x + n - 1, > x + n + 1, then we need to make 2 steps, not one. Another case is reversed. Why though we can always do these steps is a good question to prove.

Complexity

It is O(n log n) for time and space.

Code

class Solution:
    def numMovesStonesII(self, A):
        A, n = sorted(A), len(A)    
        
        ans = [n, 0]
        for i, start in enumerate(A):
            ans[0] = min(ans[0], n - bisect_right(A, start + n - 1) + i)
            
        ans[1] = A[-1] - A[0] - min(A[1] - A[0], A[-1] - A[-2]) - n + 2
            
        if ans[0] == 1 and (A[-1] - A[0] >= n + 1) and (A[n-2] - A[0] == n - 2 or A[n-1] - A[1] == n - 2):
            ans[0] = 2
            
        return ans