Moving Stones Until Consecutive II

Problem Description

There are some stones in different positions on the X-axis. You are given an integer array stones, the positions of the stones. 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. The game ends when you cannot make any more moves (i.e., the stones are in three consecutive positions). Return an integer array answer of length two where answer[0] is the minimum number of moves you can play, and answer[1] is the maximum number of moves you can play.

Key Insights

• The endpoint stones are the smallest and largest values in the stones array.
• The game ends when there are three consecutive positions occupied by stones.
• The minimum moves can be calculated by determining how far the stones are from forming three consecutive positions.
• The maximum moves involve moving stones to create gaps, allowing for multiple moves until only three consecutive positions are left.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the stones. Space Complexity: O(1) - since we are using a constant amount of space.

Solution

To solve the problem, we first sort the array of stone positions. The minimum number of moves is determined by checking the gaps between the smallest and largest stones and their neighboring stones. If there are at least three stones between the smallest and largest stone, we can minimize the moves by moving the endpoint stones into the gaps created by the consecutive stones. The maximum moves can be calculated by moving stones to create the largest gaps until only three consecutive stones remain.

1. Sort the stones array.
2. Calculate the minimum moves based on the distances to the nearest stones.
3. Calculate the maximum moves based on the total number of stones minus two (the remaining stones after creating three consecutive positions).

Code Solutions