Pass the Pillow solution and explanation
Google
9 more videos on this problem
Pass the Pillow | 2 Approaches | Easy Explanations | Leetcode 2582 | codestorywithMIKcodestorywithMIK · 24:09 · 5K views
Pass the Pillow || Maths & Logic || Leetcode-2582Aryan Mittal · 10:17 · 4K views
Pass the Pillow (LeetCode 2582) (Maths)CodeWithARB · 21:34 · 658 views
2582. Pass the Pillow (Leetcode Easy)Programming Live with Larry · 3:14 · 641 views
Leetcode 2582 Pass the Pillow (Java) - Leetcode Weekly Contest 335 - Beats 100%TheAnalyticGuy · 5:31 · 374 views
Leetcode 2582: Pass the PillowAlgorithms Casts · 12:38 · 275 views
2582 Pass the Pillow LeetcodeCodeFlix · 3:38 · 222 views
Leetcode 2582. Pass the PillowElite Code · 21:28 · 188 views
2582. Pass the Pillow | Leetcode Weekly contest 335 | Approach with example | Pythoncodingwithme · 1:14 · 145 views
LeetCode 2582 - Pass the Pillow - JavaAlpha-Code · 7:23 · 91 views
The problem
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.
def pass_the_pillow(n, time):
position = 1
direction = 1
for _ in range(time):
position += direction
if position == 0:
position = 2
direction = 1
elif position == n + 1:
position = n - 1
direction = -1
return position
n, time = 4, 5
print(pass_the_pillow(n, time))public class Main {
public static int passThePillow(int n, int time) {
int position = 1;
int direction = 1;
for (int t = 0; t < time; ++t) {
position += direction;
if (position == n + 1) {
direction = -1;
position = n - 1;
} else if (position == 0) {
direction = 1;
position = 2;
}
}
return position;
}
public static void main(String[] args) {
int n = 4, time = 5;
System.out.println(passThePillow(n, time));
}
}#include <iostream>
using namespace std;
int passThePillow(int n, int time) {
int position = 1, direction = 1;
for (int i = 0; i < time; ++i) {
position += direction;
if (position == 0) {
position = 2;
direction = 1;
} else if (position == n + 1) {
position = n - 1;
direction = -1;
}
}
return position;
}
int main() {
int n = 4, time = 5;
cout << passThePillow(n, time) << endl;
return 0;
}function passThePillow(n, time) {
let position = 1;
let direction = 1;
for (let t = 0; t < time; t++) {
position += direction;
if (position === n + 1) {
direction = -1;
position = n - 1;
} else if (position === 0) {
direction = 1;
position = 2;
}
}
return position;
}
console.log(passThePillow(4, 5));#include <stdio.h>
int passThePillow(int n, int time) {
int position = 1;
int direction = 1;
for (int t = 0; t < time; ++t) {
position += direction;
if (position == n + 1) {
direction = -1;
position = n - 1;
} else if (position == 0) {
direction = 1;
position = 2;
}
}
return position;
}
int main() {
int n = 4, time = 5;
printf("%d\n", passThePillow(n, time));
return 0;
}using System;
public class Program {
public static int PassThePillow(int n, int time) {
int position = 1;
int direction = 1;
for (int t = 0; t < time; ++t) {
position += direction;
if (position == n + 1) {
direction = -1;
position = n - 1;
} else if (position == 0) {
direction = 1;
position = 2;
}
}
return position;
}
public static void Main() {
int n = 4, time = 5;
Console.WriteLine(PassThePillow(n, time));
}
}This Python code simulates a loop iterating over each second, updating the position variable, and reversing direction when reaching either end of the line of people.
Time Complexity: O(time)
Space Complexity: O(1)
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.
def pass_the_pillow(n, time):
cycles = time // (n - 1)
remainder = time % (n - 1)
if cycles % 2 == 0:
return 1 + remainder
else:
return n - remainder
n, time = 4, 5
print(pass_the_pillow(n, time))public class Main {
public static int passThePillow(int n, int time) {
int cycles = time / (n - 1);
int remainder = time % (n - 1);
if (cycles % 2 == 0) {
return 1 + remainder;
} else {
return n - remainder;
}
}
public static void main(String[] args) {
int n = 4, time = 5;
System.out.println(passThePillow(n, time));
}
}#include <iostream>
using namespace std;
int passThePillow(int n, int time) {
int cycles = time / (n - 1);
int remainder = time % (n - 1);
if (cycles % 2 == 0) {
return 1 + remainder;
} else {
return n - remainder;
}
}
int main() {
int n = 4, time = 5;
cout << passThePillow(n, time) << endl;
return 0;
}function passThePillow(n, time) {
let cycles = Math.floor(time / (n - 1));
let remainder = time % (n - 1);
if (cycles % 2 === 0) {
return 1 + remainder;
} else {
return n - remainder;
}
}
console.log(passThePillow(4, 5));#include <stdio.h>
int passThePillow(int n, int time) {
int cycles = time / (n - 1);
int remainder = time % (n - 1);
if (cycles % 2 == 0) {
return 1 + remainder;
} else {
return n - remainder;
}
}
int main() {
int n = 4, time = 5;
printf("%d\n", passThePillow(n, time));
return 0;
}using System;
public class Program {
public static int PassThePillow(int n, int time) {
int cycles = time / (n - 1);
int remainder = time % (n - 1);
if (cycles % 2 == 0) {
return 1 + remainder;
} else {
return n - remainder;
}
}
public static void Main() {
int n = 4, time = 5;
Console.WriteLine(PassThePillow(n, time));
}
}This Python function calculates the number of complete cycles and uses modulo arithmetic to determine the position, offering a clear and efficient solution.
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.
function passThePillow(n: number, time: number): number {
let ans = 1,
k = 1;
while (time-- > 0) {
ans += k;
if (ans === 1 || ans === n) {
k *= -1;
}
}
return ans;
}func passThePillow(n int, time int) int {
ans, k := 1, 1
for ; time > 0; time-- {
ans += k
if ans == 1 || ans == n {
k *= -1
}
}
return ans
}impl Solution {
pub fn pass_the_pillow(n: i32, time: i32) -> i32 {
let mut ans = 1;
let mut k = 1;
for i in 1..=time {
ans += k;
if ans == 1 || ans == n {
k *= -1;
}
}
ans
}
}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).
function passThePillow(n: number, time: number): number {
const k = time / (n - 1);
const mod = time % (n - 1);
return (k & 1) == 1 ? n - mod : mod + 1;
}func passThePillow(n int, time int) int {
k, mod := time/(n-1), time%(n-1)
if k&1 == 1 {
return n - mod
}
return mod + 1
}impl Solution {
pub fn pass_the_pillow(n: i32, time: i32) -> i32 {
let mut k = time / (n - 1);
let mut _mod = time % (n - 1);
if (k & 1) == 1 {
return n - _mod;
}
_mod + 1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate the Passage of Pillow | Time Complexity: O(time) |
| Calculate the Final Position using Modulo Arithmetic | Time Complexity: O(1) |
| Simulation | – |
| Math | – |
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 |
Frequently asked questions
Is Pass the Pillow easy or hard?
Pass the Pillow is classified as an Easy problem on LeetCode with an acceptance rate around 56%. The main challenge is recognizing the repeating forward and backward cycle and converting the simulation into a constant-time math formula.
Pass the Pillow Python/Java solution
Both Python and Java implementations are straightforward. The simulation version iterates for time steps and flips direction at the ends, while the optimized version calculates time % (2 * (n - 1)) and derives the final index using simple arithmetic.
How to solve Pass the Pillow in O(1)?
Observe that the pillow's movement repeats every 2 * (n - 1) seconds. Compute remainder = time % (2 * (n - 1)). If remainder < n, the pillow is moving forward and the holder is 1 + remainder. Otherwise it is moving backward and the holder becomes n - (remainder - (n - 1)).
What is the best approach for Pass the Pillow?
The optimal approach uses modulo arithmetic to detect the repeating movement cycle. The pillow travels forward and backward in a cycle of length 2 * (n - 1). By computing time % cycle, you can directly determine the final holder in O(1) time and O(1) space.
Is Pass the Pillow asked at Google/Amazon/Meta?
Pass the Pillow is a common easy-level interview problem focused on pattern recognition and simulation. Variants of cyclic movement and direction reversal appear in interviews at large tech companies when evaluating basic algorithmic thinking.
What data structure is used in Pass the Pillow?
The problem does not require complex data structures. The simulation approach uses simple variables to track the current position and direction, while the optimized solution relies purely on mathematical computation and modulo operations.
What is the time complexity of Pass the Pillow?
The simulation solution runs in O(time) because it updates the holder once per second. The optimized mathematical approach runs in O(1) time by computing the position using modulo arithmetic and a constant number of operations.