Pass the Pillow - Solution & Explanation
Problem Statement
There are n people standing in a line labeled from 1 to n. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.
- For example, once the pillow reaches the
nthperson they pass it to then - 1thperson, then to then - 2thperson and so on.
Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.
Example 1:
Input: n = 4, time = 5 Output: 2 Explanation: People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2. After five seconds, the 2nd person is holding the pillow.
Example 2:
Input: n = 3, time = 2 Output: 3 Explanation: People pass the pillow in the following way: 1 -> 2 -> 3. After two seconds, the 3rd person is holding the pillow.
Constraints:
2 <= n <= 10001 <= time <= 1000
Note: This question is the same as 3178: Find the Child Who Has the Ball After K Seconds.
Approach Overview
Problem Overview: n people stand in a line and pass a pillow every second. The pillow moves left to right until it reaches the last person, then reverses direction. Given time, determine which person holds the pillow after exactly that many seconds.
Approach 1: Simulate the Passage of Pillow (O(time) time, O(1) space)
This approach directly models the process. Start with person 1 holding the pillow and track the direction of movement using a variable (either +1 or -1). For each second, move the pillow to the next person by adding the direction value. When the current holder becomes 1 or n, flip the direction to simulate the bounce at the ends of the line. The algorithm performs a simple iteration for time steps and updates the position each time. This method mirrors the real behavior of the game and is easy to implement using basic simulation.
Approach 2: Calculate the Final Position using Modulo Arithmetic (O(1) time, O(1) space)
The movement follows a repeating pattern. Passing from person 1 to n takes n-1 steps, and returning from n back to 1 takes another n-1. This creates a cycle of length 2 * (n - 1). Instead of simulating every second, compute time % (2 * (n - 1)) to find the position within the current cycle. If the remainder is less than n, the pillow is still moving forward and the holder is 1 + remainder. Otherwise, the pillow is moving backward and the holder becomes n - (remainder - (n - 1)). This converts the bouncing motion into simple arithmetic using math patterns and avoids iteration entirely.
Recommended for interviews: The modulo arithmetic approach is what interviewers typically expect because it reduces the simulation to constant time. Showing the simulation first demonstrates that you understand the mechanics of the problem. Recognizing the repeating cycle and converting it into a mathematical formula shows stronger problem-solving skills and pattern recognition.
Approach 1: Simulate the Passage of Pillow
This approach involves simulating the process of passing the pillow using a loop. We start from the first person in the line and traverse it based on the time parameter. When we reach the end, we simply reverse the direction and continue until the given time is exhausted.
This C solution simulates the passage of the pillow by updating the position with a direction variable to track when the end of the line is reached. Once the last person receives the pillow, the direction is inverted. This continues until 'time' iterations are exhausted.
Complexity
Time Complexity: O(time), since we simulate each passing of the pillow individually.
Space Complexity: O(1), as we only utilize a few integer variables for tracking state.
Approach 2: Calculate the Final Position using Modulo Arithmetic
This approach employs modulo arithmetic to determine the position of the pillow. By calculating the rounds of back-and-forth transfers based on time, we can derive the final position without directly simulating each second.
This C code calculates how many complete cycles of passing are done using time / (n - 1). Depending on whether the cycle count is even or odd, the remainder updates the position in forward or backward direction.
Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Approach 3: Simulation
We can simulate the process of passing the pillow, and each time the pillow is passed, if the pillow reaches the front or the end of the queue, the direction of the pillow will change, and the queue will continue to pass the pillow along the opposite direction.
The time complexity is O(time) and the space complexity is O(1), where time is the given time.
Approach 4: Math
We notice that there are n - 1 passes in each round. Therefore, we can divide time by n - 1 to get the number of rounds k that the pillow is passed, and then take the remainder of time modulo n - 1 to get the remaining passes mod in the current round.
Then we judge the current round k:
- If
kis odd, then the current direction of the pillow is from the end of the queue to the front, so the pillow will be passed to the person with the numbern - mod. - If
kis even, then the current direction of the pillow is from the front of the queue to the back, so the pillow will be passed to the person with the numbermod + 1.
The time complexity is O(1) and the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simulate the Passage of Pillow | Time Complexity: O(time), since we simulate each passing of the pillow individually. |
| Calculate the Final Position using Modulo Arithmetic | Time Complexity: O(1) |
| Simulation | — |
| Math | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate the Passage of Pillow | O(time) | O(1) | Good for understanding the mechanics or when time is small |
| Modulo Arithmetic Cycle Calculation | O(1) | O(1) | Preferred for large time values and interview-optimized solutions |
Video Solution
Pass the Pillow | 2 Approaches | Easy Explanations | Leetcode 2582 | codestorywithMIK • codestorywithMIK • 5,304 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Pass the Pillow easy or hard?
Pass the Pillow Python/Java solution
How to solve Pass the Pillow in O(1)?
What is the best approach for Pass the Pillow?
Is Pass the Pillow asked at Google/Amazon/Meta?
What data structure is used in Pass the Pillow?
What is the time complexity of Pass the Pillow?
Ready to solve this problem?
Practice Pass the Pillow with our built-in code editor and test cases.
Practice on FleetCode