Moving Stones Until Consecutive II - Practice Coding Problems

Moving Stones Until Consecutive II - Problem

There are some stones in different positions on the X-axis. You are given an integer array stones where stones[i] represents the position of the i-th stone.

Call a stone an endpoint stone if it has the smallest or largest position. In one move, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.

For example, if the stones are at positions [1,2,5], you cannot move the endpoint stone at position 5 to position 3 or 4 because it would still be an endpoint stone.

The game ends when you cannot make any more moves (i.e., the stones are in consecutive positions). Return an integer array answer of length 2 where:

answer[0] is the minimum number of moves you can play
answer[1] is the maximum number of moves you can play

Input & Output

Example 1 — Basic Case

$ Input: stones = [7,4,9]

› Output: [1,2]

💡 Note: We can move 4 to 8 to get [7,8,9] in 1 move (minimum). For maximum, we can move 4 to 6, then 7 to 8 to get [6,8,9] then [8,9,10], taking 2 moves total.

Example 2 — Already Consecutive

$ Input: stones = [6,5,4,3,10]

› Output: [2,3]

💡 Note: For minimum: move 3 to 7 and 10 to 8 to get [4,5,6,7,8]. For maximum: avoid the larger gap by keeping either [3,4,5,6] or [5,6,7,8,9,10] pattern.

Example 3 — Large Gaps

$ Input: stones = [1,3,8]

› Output: [1,2]

💡 Note: Minimum: move 1 to 7 to get [3,7,8], then move endpoint to make consecutive. Maximum: move 8 to 2, then 3 to get larger sequence.

Constraints

3 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Stones at positions [7,4,9] on number line

Rules

Only endpoint stones (smallest/largest position) can be moved

Goal

Make all stones consecutive with minimum and maximum moves

Key Takeaway

🎯 Key Insight: Use sliding window for minimum moves and gap analysis for maximum moves

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is using sliding window for minimum moves and gap analysis for maximum moves. The optimal approach uses mathematical analysis: minimum moves found by sliding window technique to find the best consecutive position, maximum moves calculated by choosing the strategy that avoids the larger gap. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window for Minimum	O(n log n)	O(n)	Use sliding window to find minimum moves, mathematical analysis for maximum
Mathematical Analysis	O(n log n)	O(1)	Direct mathematical calculation of minimum and maximum moves
Brute Force Simulation	O(2ⁿ)	O(2ⁿ)	Try all possible move sequences to find minimum and maximum moves

Sliding Window for Minimum — Algorithm Steps

Step 1: Sort stones and remove duplicates
Step 2: Use sliding window to find minimum stones to move
Step 3: Calculate maximum moves by avoiding the larger gap

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Stones

Remove duplicates and sort positions

Sliding Window

Find window of size n with most stones

Calculate Moves

Min moves = n - stones_in_best_window

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* stones, int stonesSize, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    // Sort stones
    for (int i = 0; i < stonesSize-1; i++) {
        for (int j = i+1; j < stonesSize; j++) {
            if (stones[i] > stones[j]) {
                int temp = stones[i];
                stones[i] = stones[j];
                stones[j] = temp;
            }
        }
    }
    
    // Remove duplicates
    int n = 1;
    for (int i = 1; i < stonesSize; i++) {
        if (stones[i] != stones[n-1]) {
            stones[n++] = stones[i];
        }
    }
    
    if (n <= 2) {
        result[0] = 0;
        result[1] = 0;
        return result;
    }
    
    // Calculate maximum moves
    int leftGap = stones[n-1] - stones[1] - (n - 2);
    int rightGap = stones[n-2] - stones[0] - (n - 2);
    int maxMoves = (leftGap > rightGap) ? leftGap : rightGap;
    
    // Calculate minimum moves using sliding window
    int minMoves = n;
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j < n && stones[j] - stones[i] + 1 <= n) {
            j++;
        }
        
        int moves;
        if (j - i == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
            moves = 2;
        } else {
            moves = n - (j - i);
        }
        
        if (moves < minMoves) {
            minMoves = moves;
        }
    }
    
    result[0] = minMoves;
    result[1] = maxMoves;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int stones[100];
    int count = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL && count < 100) {
        stones[count++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int returnSize;
    int* result = solution(stones, count, &returnSize);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), sliding window takes O(n)

⚡ Linearithmic

Space Complexity

O(n)

Space for unique stones array

⚡ Linearithmic Space

18.8K Views

Medium Frequency

~35 min Avg. Time

425 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window for Minimum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler