LeetCode 2582 - Pass the Pillow

LeetCode Problem 2582

Difficulty: 🟢 Easy
Topics: Math, Simulation

Solution

Problem Understanding

The problem describes a line of n people, numbered sequentially from 1 to n. Initially, person 1 holds a pillow. Every second, the pillow is passed to the adjacent person. The direction of passing changes whenever the pillow reaches either end of the line.

In other words, the pillow moves forward from person 1 toward person n, then reverses direction and moves backward toward person 1, repeating this pattern indefinitely.

We are given two integers:

• n, representing the number of people standing in line.
• time, representing the number of seconds that have passed.

The goal is to determine which person is holding the pillow after exactly time seconds.

To better understand the movement, consider n = 4:

• Start: 1
• After 1 second: 2
• After 2 seconds: 3
• After 3 seconds: 4
• After 4 seconds: 3
• After 5 seconds: 2
• After 6 seconds: 1
• After 7 seconds: 2

Notice that the movement repeats in a cycle.

The constraints are small:

• 2 <= n <= 1000
• 1 <= time <= 1000

Since both values are at most 1000, even a direct simulation would be fast enough. However, the repeating nature of the movement suggests that we can derive the answer mathematically in constant time.

An important observation is that the pillow moves back and forth in a repeating cycle of length 2 × (n - 1):

• Moving from 1 to n takes n - 1 seconds.
• Moving back from n to 1 takes another n - 1 seconds.

This repeating structure is the key insight for an optimal solution.

Some edge cases are important to consider upfront. When time is smaller than n - 1, the pillow has not yet reached the end and simply moves forward. When time is exactly n - 1, the pillow is at person n. When time exceeds one full cycle, we must correctly account for repeated movement using modular arithmetic. The problem guarantees valid positive inputs, so we never need to handle invalid values such as n = 1 or negative time.

Approaches

Brute Force Simulation

The most straightforward approach is to simulate the pillow passing second by second.

We maintain two variables:

• The current person holding the pillow.
• The direction of movement, either forward (+1) or backward (-1).

At every second:

1. Move the pillow to the next person.
2. If the pillow reaches either end of the line, reverse the direction.

This approach works because it faithfully reproduces the exact behavior described in the problem statement. After simulating time seconds, the current holder is the answer.

Although this method is correct, it performs one operation per second, resulting in linear time complexity relative to time.

Optimal Mathematical Observation

The better solution comes from recognizing that the pillow movement forms a repeating cycle.

A full cycle consists of:

• Moving from 1 to n, which takes n - 1 seconds.
• Moving back from n to 1, which takes another n - 1 seconds.

Therefore, the cycle length is:

$$2 \times (n - 1)$$

Instead of simulating every second, we compute where within the cycle the current time falls.

First, compute:

$$cycle = n - 1$$

Then determine:

• fullRounds = time // cycle
• remaining = time % cycle

If fullRounds is even, we are moving forward, so the answer is:

$$1 + remaining$$

If fullRounds is odd, we are moving backward, so the answer is:

$$n - remaining$$

This eliminates the need for simulation and gives the result in constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(time)	O(1)	Simulates every pillow pass step by step
Optimal	O(1)	O(1)	Uses cycle math and modular arithmetic

Algorithm Walkthrough

1. Compute the one-way distance between ends.

Since moving from person 1 to person n takes n - 1 passes, we define:

cycle = n - 1

This represents half of the repeating movement pattern. 2. Determine how many complete directional segments have passed.

Compute:

fullRounds = time // cycle

If this number is even, the pillow is moving forward. If odd, it is moving backward. 3. Determine the remaining movement within the current segment.

Compute:

remaining = time % cycle

This tells us how many additional passes occur after the completed directional movements. 4. Check the current direction.

If fullRounds is even, the pillow moves from left to right:

answer = 1 + remaining

If fullRounds is odd, the pillow moves from right to left:

answer = n - remaining

5. Return the result.

The computed person index is exactly who holds the pillow after time seconds.

Why it works

The pillow movement is periodic. Every n - 1 seconds, the direction flips. By dividing time into blocks of length n - 1, we know whether the pillow is moving forward or backward. The remainder tells us how far along the current direction the pillow has moved. Since every possible state repeats predictably, modular arithmetic guarantees the correct answer.

Python Solution

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        cycle = n - 1
        full_rounds = time // cycle
        remaining = time % cycle

        if full_rounds % 2 == 0:
            return 1 + remaining

        return n - remaining

The implementation directly follows the mathematical observation.

First, we calculate cycle, which represents the number of seconds needed to travel from one end of the line to the other. Then, full_rounds determines how many directional segments have passed, while remaining represents how many steps remain in the current segment.

If full_rounds is even, the pillow is moving from left to right, so we simply move forward from person 1. Otherwise, the pillow is moving from right to left, so we count backward from person n.

Because the algorithm relies only on arithmetic operations, it runs in constant time and uses constant memory.

Go Solution

func passThePillow(n int, time int) int {
	cycle := n - 1
	fullRounds := time / cycle
	remaining := time % cycle

	if fullRounds%2 == 0 {
		return 1 + remaining
	}

	return n - remaining
}

The Go implementation is almost identical to the Python version. Since Go uses integer division automatically for integers, time / cycle behaves exactly as needed.

There are no concerns about integer overflow because the constraints are very small, with values capped at 1000. No additional data structures are required, and only a few integer variables are used.

Worked Examples

Example 1

Input: n = 4, time = 5

First compute the cycle length:

cycle = n - 1 = 3

Variable	Value
cycle	3
full_rounds	5 // 3 = 1
remaining	5 % 3 = 2

Since full_rounds = 1 is odd, the pillow is moving backward.

Compute:

answer = n - remaining
       = 4 - 2
       = 2

Result: 2

Movement visualization:

Second	Holder
0	1
1	2
2	3
3	4
4	3
5	2

Final answer: 2

Example 2

Input: n = 3, time = 2

First compute the cycle length:

cycle = n - 1 = 2

Variable	Value
cycle	2
full_rounds	2 // 2 = 1
remaining	2 % 2 = 0

Since full_rounds = 1 is odd, the pillow is moving backward.

Compute:

answer = n - remaining
       = 3 - 0
       = 3

Movement visualization:

Second	Holder
0	1
1	2
2	3

Final answer: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic operations are performed
Space	O(1)	No extra memory proportional to input size is used

The algorithm uses simple division, modulo, and parity checking, regardless of the size of n or time. Since no loops or additional data structures are involved, both time and space remain constant.

Test Cases

solution = Solution()

# Provided examples
assert solution.passThePillow(4, 5) == 2  # Example 1
assert solution.passThePillow(3, 2) == 3  # Example 2

# Minimum n value
assert solution.passThePillow(2, 1) == 2  # First pass reaches end
assert solution.passThePillow(2, 2) == 1  # Direction reverses

# Time smaller than first turnaround
assert solution.passThePillow(5, 2) == 3  # Still moving forward

# Exact turnaround point
assert solution.passThePillow(5, 4) == 5  # Reaches last person

# Immediately after turnaround
assert solution.passThePillow(5, 5) == 4  # Starts moving backward

# Full cycle completion
assert solution.passThePillow(5, 8) == 1  # Back to start

# Multiple cycles
assert solution.passThePillow(4, 10) == 3  # Several repetitions

# Large constraint values
assert solution.passThePillow(1000, 1000) == 999  # Stress test

# Odd and even round behavior
assert solution.passThePillow(6, 7) == 3  # Backward movement
assert solution.passThePillow(6, 3) == 4  # Forward movement

Test	Why
(4, 5)	Verifies provided example with backward motion
(3, 2)	Verifies provided example ending at boundary
(2, 1)	Smallest valid n
(2, 2)	Ensures direction reversal works
(5, 2)	Checks simple forward movement
(5, 4)	Tests exact endpoint arrival
(5, 5)	Verifies movement immediately after reversal
(5, 8)	Confirms full cycle behavior
(4, 10)	Tests repeated cycles
(1000, 1000)	Validates upper constraint handling
(6, 7)	Confirms backward traversal
(6, 3)	Confirms forward traversal

Edge Cases

Minimum Number of People

When n = 2, the pillow alternates between only two people. This case can expose off by one errors because the cycle length becomes 1. A naive implementation might incorrectly assume movement is more complex. Our formula works correctly because cycle = n - 1 = 1, so every second flips direction predictably.

Exact Endpoint Arrival

When time equals n - 1, the pillow lands exactly on the last person. This is a common source of bugs because some implementations mistakenly reverse direction too early. Our approach handles this naturally because remaining = 0 after one full directional segment, and the odd parity correctly places the pillow at person n.

Multiple Full Cycles

When time is much larger than n, repeatedly simulating movement may be inefficient or introduce logic mistakes in direction switching. Since the movement repeats every 2 × (n - 1) seconds, our implementation avoids unnecessary work by relying on division and modulo operations to jump directly to the correct state.

Immediate Direction Reversal

When the pillow has just reached an endpoint and needs to reverse direction, implementations may accidentally double count the endpoint or skip a person. For example, with n = 5 and time = 5, the pillow should move from 5 back to 4. The parity check combined with the remainder calculation ensures the reversal is handled precisely.