Leetcode 1033: Moving Stones Until Consecutive
You are given three stones located at different positions on the X-axis. The positions are represented by three distinct integers
a, b, and c. In one move, you can pick a stone from either of the two endpoints (the smallest or the largest position) and move it to any unoccupied position between the two endpoints. The game ends when all three stones are positioned at three consecutive spots on the X-axis. Your task is to determine the minimum and maximum number of moves required to reach this configuration.Problem
Approach
Steps
Complexity
Input: You are given three distinct integers `a`, `b`, and `c` representing the positions of the stones.
Example: a = 3, b = 6, c = 10
Constraints:
• 1 <= a, b, c <= 100
• a, b, and c have different values.
Output: Return an array of length 2 where the first element represents the minimum number of moves and the second element represents the maximum number of moves required to make the stones occupy three consecutive positions.
Example: Output: [1, 2]
Constraints:
• The answer must include both the minimum and maximum number of moves.
Goal: The goal is to calculate the minimum and maximum number of moves to position the stones at three consecutive positions.
Steps:
• 1. Sort the positions of the stones to identify the smallest, middle, and largest values.
• 2. If the difference between the largest and smallest values is 2, no moves are needed (i.e., the stones are already in consecutive positions).
• 3. To find the minimum moves, check if the middle stone is already adjacent to one of the endpoints (this would require only one move). Otherwise, two moves are needed.
• 4. To find the maximum moves, subtract 2 from the difference between the largest and smallest stone positions, as that will give the number of available positions between them.
Goal: Ensure that the solution is efficient, given the problem constraints.
Steps:
• The positions of the stones are always distinct.
• The number of moves must be computed accurately for both the minimum and maximum cases.
Assumptions:
• The positions of the stones are provided in distinct integers and are guaranteed to be within the specified bounds.
• Input: Input: a = 1, b = 3, c = 7
• Explanation: In this case, the stones are at positions 1, 3, and 7. The minimum number of moves is 1: move the stone from position 7 to 4. The maximum number of moves is 2: move the stone from position 7 to 5, then move the stone from position 5 to 4.
• Input: Input: a = 4, b = 5, c = 6
• Explanation: In this case, the stones are already at consecutive positions, so no moves are needed. The minimum and maximum number of moves are both 0.
Approach: The solution involves sorting the stone positions and then checking the differences between them to determine the possible moves.
Observations:
• Sorting the positions of the stones is a good first step to simplify the calculation of the number of moves.
• After sorting, we can quickly determine if the stones are already in consecutive positions or if any moves are necessary.
Steps:
• 1. Sort the positions of the stones to easily identify the smallest, middle, and largest positions.
• 2. If the difference between the largest and smallest positions is 2, return [0, 0] as no moves are needed.
• 3. For the minimum number of moves, check the distance between the middle stone and the endpoints to determine if only one move is needed, otherwise, two moves.
• 4. For the maximum number of moves, subtract 2 from the difference between the largest and smallest positions.
Empty Inputs:
• There will always be three distinct positions given, so empty inputs are not possible.
Large Inputs:
• The solution should handle the constraints efficiently, but the problem size is small (only 3 positions).
Special Values:
• If the positions are already consecutive, the result will be [0, 0].
Constraints:
• The problem guarantees distinct positions, so no need to handle repeated values.
vector<int> numMovesStones(int a, int b, int c) {
vector<int> s {a, b, c};
sort(s.begin(), s.end());
if(s[2]-s[0] == 2) return {0, 0};
return {min(s[1]- s[0], s[2]-s[1]) <= 2? 1 : 2, s[2] - s[0] - 2 };
}
1 : Function Definition
vector<int> numMovesStones(int a, int b, int c) {
Define the function `numMovesStones` that calculates the minimum and maximum moves to align stones.
2 : Initialize Vector
vector<int> s {a, b, c};
Initialize a vector `s` to store the stone positions.
3 : Sort Vector
sort(s.begin(), s.end());
Sort the vector `s` to arrange stone positions in ascending order.
4 : Check Consecutive Case
if(s[2]-s[0] == 2) return {0, 0};
Check if the stones are already consecutive. If so, return {0, 0} as no moves are needed.
5 : Calculate Moves
return {min(s[1]- s[0], s[2]-s[1]) <= 2? 1 : 2, s[2] - s[0] - 2 };
Return the minimum and maximum moves required based on the distances between the stones.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is O(1) as sorting three elements is constant time.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we are only using a constant amount of extra space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus