How do you solve Pass the Pillow on LeetCode?

Pass the Pillow (LeetCode #2582) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: The pillow's movement creates a repeating pattern that can be leveraged to calculate positions directly.

What is the brute force solution for Pass the Pillow?

The brute force approach for Pass the Pillow is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach simulates each second of passing the pillow. We simply iterate through each second and update the holder of the pillow based on the current direction until the time runs out. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Pass the Pillow?

Pass the Pillow uses the following concepts: Math, Simulation. The recommended patterns to study are: Simulation, Mathematical Patterns.

What are the interview tips for Pass the Pillow?

Always consider edge cases, such as the smallest and largest values for n and time. Think about patterns in the problem; they can often lead to more efficient solutions. Practice simulating problems first, then look for ways to optimize based on your observations.

What are common mistakes when solving Pass the Pillow?

Forgetting to handle the direction change correctly in the brute force approach. Not recognizing the periodic nature of the problem when trying to optimize.

#2582

Pass the Pillow

Easy

MathSimulationSimulationMathematical Patterns

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

Instead of simulating each second, we can calculate the final position directly using the properties of the movement. The pillow moves back and forth, creating a predictable pattern based on the total time and the number of people.

⚙️

Algorithm

2 steps

1Step 1: Calculate the effective time as time % (2 * (n - 1)) to account for complete back-and-forth cycles.
2Step 2: Determine the position based on the effective time: if it's less than n, the pillow is moving forward; otherwise, it's moving backward.

solution.py6 lines

1n, time = 4, 5
2effective_time = time % (2 * (n - 1))
3if effective_time < n:
4    print(effective_time + 1)
5else:
6    print(2 * n - effective_time - 1)

ℹ

Complexity note: The time complexity is O(1) because we are performing a constant number of operations regardless of the input size. The space complexity is also O(1) as we are using a fixed amount of extra space.

1The pillow's movement creates a repeating pattern that can be leveraged to calculate positions directly.
2Understanding the modulo operation helps in reducing unnecessary iterations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.