[
array
math
two pointers
sort
greedy
]
Leetcode 1040. Moving Stones Until Consecutive II
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:
- 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 between1, 3
and10, 20
: on the first step we have only this choice. Then on each step we can reduce difference between biggest and smallest element by1
. - 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 havex, x+1, x+2, ... x + n - 1, > x + n + 1
, then we need to make2
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