MediumNo. 1040

Moving Stones Until Consecutive II — LeetCode 1040 Python Solution

Topics
Array, Math, Sorting, Sliding Window
Reading time
3 min

The problem

There are some stones in different positions on the X-axis. You are given an integer array stones, the positions of the stones.

Example

Input
stones = [7,4,9]
Output
[1,2]
Explanation
We can move 4 -> 8 for one move to finish the game.

Python solution

PythonSolution
class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()
        mi = n = len(stones)
        mx = max(stones[-1] - stones[1] + 1, stones[-2] - stones[0] + 1) - (n - 1)
        i = 0
        for j, x in enumerate(stones):
            while x - stones[i] + 1 > n:
                i += 1
            if j - i + 1 == n - 1 and x - stones[i] == n - 2:
                mi = min(mi, 2)
            else:
                mi = min(mi, n - (j - i + 1))
        return [mi, mx]

Complexity

Time
O(n)
Space · auxiliary
O(1) to O(n)

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1040. Moving Stones Until Consecutive II is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 1040. Moving Stones Until Consecutive II?

LeetCode 1040. Moving Stones Until Consecutive II is rated Medium on LeetCode.

What topics does LeetCode 1040. Moving Stones Until Consecutive II cover?

LeetCode 1040. Moving Stones Until Consecutive II is tagged Array, Math, Sorting and Sliding Window on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.