Moving Stones Until Consecutive II

Moving Stones Until Consecutive II

What is this problem about?

The Moving Stones Until Consecutive II problem generalizes the three-stone problem to n stones. You move an endpoint stone to any unoccupied position (not necessarily between stones), and the goal is to make all stones consecutive. Find the minimum and maximum number of moves. This coding problem uses sliding window for the minimum and a formula for the maximum.

Why is this asked in interviews?

Meta asks this medium problem because it extends the brainteaser into a more algorithmic challenge requiring sliding window techniques. The maximum moves formula is straightforward but the minimum requires carefully finding the longest window already containing a run of consecutive positions. The array, math, sorting, and sliding window interview pattern is applied.

Algorithmic pattern used

Sorting + maximum formula + sliding window for minimum.

• Maximum: Remove the two extreme-end stones separately. Max = max(stones[-1] - stones[-2] - 1, stones[1] - stones[0] - 1) + n - 2. (Move either the leftmost or rightmost stone optimally.)
• Minimum: Sort stones. Use a sliding window of size n. For each window that fits exactly n stone positions stones[j] - stones[i] ≤ n-1, count how many stones are already in the window. Minimum moves = n - max(stones in any window). Special case: when the window is n-1 long (almost full) but has one gap, min might need +1.

Example explanation

Stones: [7, 4, 9]. Sorted: [4, 7, 9]. n=3.

• Max = max(9-7-1, 7-4-1) + 1 = max(1, 2) + 1 = 3.
• Min: window [4,7,9] spans 5 positions (9-4=5 > n-1=2). Window [4,7]: span 3 > 2. Window [7,9]: span 2 = n-1=2, stones in window = 2. Min = 3-2 = 1.

Common mistakes candidates make

• Not sorting before computing max or applying sliding window.
• Incorrect max formula (off by one when counting positions between endpoints).
• Missing the special case in minimum where the window has a "hole."
• Using n instead of the actual stones count in the formula.

Interview preparation tip

Two-complexity problems (min and max) often require independent algorithms for each part. Practice them separately: compute max with the formula, then tackle min with sliding window. The sliding window minimum count approach — find the window of n positions containing the most existing stones — generalizes to other "pack n items into the smallest window" problems. Practice both formulas until they become second nature.