1033. Moving Stones Until Consecutive

MediumBrainteaserMath

Problem Description

In this LeetCode problem, we are tasked with finding the minimum and maximum number of moves to position three stones into three consecutive positions along the X-axis. We are given three integers a, b, and c, which represent the current positions of the stones. A move consists of picking up a stone that is at one of the endpoints (not in the middle) and moving it to a new position that is between the current two endpoints but not currently occupied by another stone.

The game ends when the stones are in consecutive positions, meaning they occupy three positions that are next to each other, and no more moves can be made. We need to calculate two things:

The minimum number of moves required to reach the end state.
The maximum number of moves that can be played before reaching the end state.

Intuition

To solve this problem, we first need to identify the positions of the stones in sorted order since their given positions could be in any order. We'll denote the smallest position as x, the largest as z, and the middle one as y. Once we have the stones sorted, we can determine possible moves.

For the minimum moves (mi):

If the stones are already consecutive, no moves are required.
If there is only one gap of one space between the stones, just one move is required, moving the endpoint stone into the one gap.
If there are larger gaps, we may need two moves. One to move an outer stone next to the middle stone and another to fill in the remaining gap, unless one of the gaps is already just one space, in which case only one move is required.

For the maximum moves (mx):

Since the maximum number of moves is made by putting the stones next to each other one step at a time, the number of moves is equal to the distance between x and z, minus the two positions where y and the stone being moved can be positioned (since the end state is consecutive positions).

The solution code reflects this logic by first finding x, y, and z, and then determining the minimum and maximum number of moves based on the distances between the stones.

Learn more about Math patterns.

Solution Approach

The implementation of the given solution involves determining the starting positions of the stones and calculating the minimum and maximum number of moves required to place them in consecutive positions.

Here is a breakdown of the approach:

Firstly, we identify the minimum and maximum values among a, b, and c to establish which stones are at the endpoints. We use the built-in functions min() and max() to find these values, assigning them to the local variables x and z.
The middle value y is then found by calculating the sum of all three positions and subtracting the values of x and z. This gives us the sorted order of the stones on the X-axis without actually sorting them.
With the stones now in order, we consider two scenarios for calculating minimum moves mi:
- If z - x is less than or equal to 2, the stones are already in consecutive positions or only one move away from it. Therefore, we need either 0 or 1 move.
- If z - x is greater than 2, we must consider the positions of y. If y is within one position of x or z (y - x < 3 or z - y < 3), then only one move is required. Otherwise, we might need two moves: one to move an endpoint stone closer and another move to place it in the right position.
For maximum moves mx, if z - x is less than or equal to 2 again, we cannot make any moves, so mx is 0. If there is a bigger gap, then the maximum number of moves is the total distance between x and z minus 2 (for x and z themselves), since we are trying to fill this distance with consecutive positions.
At the end of this process, we return [mi, mx], which represents the minimum and maximum number of moves respectively.

The algorithm uses constant space and operates in constant time, as all operations are basic arithmetic calculations. There are no complex data structures or patterns in use; it’s straight-forward analysis of the positions of the stones.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take three stones at positions a = 1, b = 2, and c = 5.

First, we determine the minimum (x) and maximum (z) positions of the stones using the min() and max() functions. In our case, x = 1 and z = 5.
We then find the middle position y by subtracting x and z from the sum (a + b + c). That gives us y = (1 + 2 + 5) - (1 + 5) = 8 - 6 = 2.
Now we have the stones in sorted order: x = 1, y = 2, z = 5. To calculate the minimum number of moves (mi):
- We check the distance between x and z. Since z - x = 5 - 1 = 4, which is more than 2, the stones are not consecutive yet.
- We look at the gaps between x, y and y, z. Here, y - x = 2 - 1 = 1 and z - y = 5 - 2 = 3. The gap between x and y is 1, which is less than 3, so moving the stone from position z to y + 1 (3) will make them consecutive. Thus, only one move is needed.
To find the maximum number of moves (mx):
- We have a larger gap so, mx = z - x - 2 = 5 - 1 - 2 = 2. This is the number of moves that can be played moving the stone from z to y + 1 and then moving the stone from x to x + 1 (or vice versa), making them consecutive one step at a time.
Finally, we return the calculated minimum and maximum moves as the output of the algorithm: [mi, mx] = [1, 2].

Through this walkthrough with the example values, the stones would achieve consecutive positions in 1 minimum move and up to 2 maximum moves.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
5        # Find the minimum and maximum values among a, b, and c to identify
6        # the positions of the leftmost (min_stone) and rightmost (max_stone) stones.
7        min_stone, max_stone = min(a, b, c), max(a, b, c)
8      
9        # The middle stone will be the sum of a, b, c minus the leftmost and rightmost stones.
10        middle_stone = a + b + c - min_stone - max_stone
11      
12        # Initializing the minimum and maximum moves to 0.
13        min_moves = max_moves = 0
14      
15        # If the largest gap between the end stones is more than 2,
16        # then moves are required.
17        if max_stone - min_stone > 2:
18            # If the gap between either the middle stone and one of the end stones
19            # is less than 3, only one move is required (to move the middle stone).
20            # Otherwise, two moves are required.
21            min_moves = 1 if middle_stone - min_stone < 3 or max_stone - middle_stone < 3 else 2
22          
23            # The maximum moves are the largest gap minus two, because moving a stone
24            # into either end of the gap will always reduce the remaining gap by one.
25            max_moves = max_stone - min_stone - 2
26      
27        # Returning the minimum and maximum number of moves as a list.
28        return [min_moves, max_moves]
29

1class Solution {
2    public int[] numMovesStones(int a, int b, int c) {
3        // Find the smallest value among a, b, c and assign it to minStone
4        int minStone = Math.min(a, Math.min(b, c));
5      
6        // Find the largest value among a, b, c and assign it to maxStone
7        int maxStone = Math.max(a, Math.max(b, c));
8      
9        // The middle stone is always the sum minus the smallest and largest
10        int middleStone = a + b + c - minStone - maxStone;
11      
12        // Initialize the minimum and maximum moves to 0
13        int minimumMoves = 0, maximumMoves = 0;
14      
15        // If the stones are not already consecutive
16        if (maxStone - minStone > 2) {
17            // If the gap between any two stones is less than 3, a single move is needed,
18            // otherwise 2 moves are needed (move one stone next to an end stone and the other stone in between them)
19            minimumMoves = (middleStone - minStone < 3 || maxStone - middleStone < 3) ? 1 : 2;
20          
21            // The maximum number of moves is the total gap minus the two spaces occupied by the two end stones
22            maximumMoves = maxStone - minStone - 2;
23        }
24      
25        // Return an array with the minimum and maximum moves
26        return new int[] {minimumMoves, maximumMoves};
27    }
28}
29

1class Solution {
2public:
3    vector<int> numMovesStones(int a, int b, int c) {
4        // Find the smallest and largest of the three stones.
5        int minStone = min({a, b, c});
6        int maxStone = max({a, b, c});
7      
8        // Calculate the middle stone by subtracting the smallest and largest from the sum.
9        int midStone = a + b + c - minStone - maxStone;
10      
11        // Initialize the minimum and maximum moves to 0.
12        int minMoves = 0, maxMoves = 0;
13      
14        // If the largest and smallest stone are not next to each other
15        if (maxStone - minStone > 2) {
16            // If either gap between min and mid or mid and max is less than 3, 
17            // one move is sufficient to place a stone in a position that bridges the gap.
18            // Otherwise, two moves are needed (one for each gap).
19            minMoves = (midStone - minStone < 3 || maxStone - midStone < 3) ? 1 : 2;
20          
21            // The maximum number of moves is the total span minus two (since two positions will be occupied
22            // by the outer stones) which gives us the total number of free spots between them.
23            maxMoves = maxStone - minStone - 2;
24        }
25      
26        // Return a vector with the minimum and maximum number of moves.
27        return {minMoves, maxMoves};
28    }
29};
30

1function numMovesStones(a: number, b: number, c: number): number[] {
2    // First, find the minimum (left) value among a, b, and c.
3    const left = Math.min(a, Math.min(b, c));
4    // Next, find the maximum (right) value among a, b, and c.
5    const right = Math.max(a, Math.max(b, c));
6    // Calculate the middle value by subtracting the known left and right from the sum of all.
7    const middle = a + b + c - left - right;
8
9    let minMoves = 0; // To store the minimum number of moves.
10    let maxMoves = 0; // To store the maximum number of moves.
11
12    // If the stones are not consequtive (having at least two places gap).
13    if (right - left > 2) {
14        // If the gap from left to middle or middle to right is less than 3,
15        // only one move is required as a stone can be placed in between the other two directly.
16        // Otherwise, two moves are needed.
17        minMoves = (middle - left < 3 || right - middle < 3) ? 1 : 2;
18        // Maximum number of moves is the total gap between the outer stones minus the positions
19        // occupied by the middle stone, as we can move one stone per turn.
20        maxMoves = right - left - 2;
21    }
22
23    // Return an array of two numbers: minimum and maximum number of moves.
24    return [minMoves, maxMoves];
25}
26

Time and Space Complexity

The provided code is determining the minimum and maximum number of moves to position three stones (with unique positions a, b, and c) consecutively. For understanding the complexity, let's analyze the code step by step:

The min and max functions are used to find the smallest (x) and largest (z) of the three stones' positions. This operation is O(1) because it deals with only three elements.
Calculating y is done by summing the positions and subtracting x and z to find the remaining middle value. This is also O(1).
Setting mi and mx to zero is a constant operation, O(1).
The condition if z - x > 2: checks if the stones are not already consecutive. This comparison is O(1).
Inside the if statement, the code performs two further checks: y - x < 3 and z - y < 3, each being O(1). Based on these checks, mi is either set to 1 or 2 and mx is set to z - x - 2.
The operation z - x - 2 is also O(1) since it involves constant-time arithmetic operations.
Returning the list [mi, mx] is O(1) as it simply packages two integers into a list.

Given that all operations are constant-time, the overall time complexity of the provided code is O(1).

The space complexity is the amount of additional space or temporary space one needs to allocate in order to execute the code. Since the provided code only uses a fixed number of integer variables (x, y, z, mi, mx) and does not utilize any data structures that grow with input size:

The overall space complexity of the provided code is also O(1) as it allocates a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: