Bakery Tray Gaps
A bakery's display tray is one long row of slots. Each slot holds a pastry, written as its product number, or is empty, written as 0. As customers buy things during the morning, gaps open up all over the tray.
Before the lunch rush, the baker slides every pastry toward the front of the tray so the gaps collect at the back, where the new batch will go. The pastries must stay in the same order as before, because the labels on the glass follow that order.
Your task
Write compactTray(tray). Rearrange tray in place so all non-zero numbers come first, in their original order, followed by all the zeros. Return nothing.
Do not create a second list. The length of tray stays the same.
compactTray(tray: int[]) → void (changes tray in place)
Examples
tray = [0, 41, 0, 7, 12]
[41, 7, 12, 0, 0]
The pastries are 41, 7, 12, in that order. They move to the front and keep that order. The two gaps end up at the back.
tray = [9, 3, 0, 0, 5]
[9, 3, 5, 0, 0]
9 and 3 are already in place. Only 5 has to move forward, past the two gaps. Sorting would give a different, wrong answer: the order 9, 3, 5 must be kept.
Constraints
- 0 ≤ tray.length ≤ 10,000
- 0 ≤ tray[i] ≤ 999
Start with brute force
Each time you find a gap, delete it from the list and add a 0 at the end. Or, scan for the first gap and shift everything after it one place left, again and again.
Both are correct, but each delete or shift moves every later slot. A tray of 10,000 slots that is half gaps does about 5,000 shifts of up to 10,000 slots each: tens of millions of moves. Each pastry only needs to move once, straight to its final slot.
Hints
0 of 4 shown- Hint 1
In
[0, 41, 0, 7, 12], which slot should 41 end up in? Which slot should 7 end up in? Can you tell just by counting pastries you have already seen? - Hint 2
The k-th pastry you meet from the left always ends up in slot k-1. So as you scan, you always know the next slot that should receive a pastry.
- Hint 3
Use two indexes. One scans every slot. The other points at the next slot to fill with a pastry. It moves only when a pastry is placed.
- Hint 4
Scan with
r, and keepw= next slot to fill, starting at 0. Whentray[r]is not 0, swaptray[w]andtray[r], then add 1 tow. The swap carries a gap backwards at the same time as it moves the pastry forwards.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The first pastry you meet goes to slot 0, the second to slot 1, and so on. So keep a write index w for the next slot that should hold a pastry, and scan every slot with a read index r.
Trace [0, 41, 0, 7, 12]:
r= 0 is a gap. Do nothing.wstays 0.r= 1 is 41. Swap slots 0 and 1:[41, 0, 0, 7, 12].w= 1.r= 2 is a gap. Do nothing.r= 3 is 7. Swap slots 1 and 3:[41, 7, 0, 0, 12].w= 2.r= 4 is 12. Swap slots 2 and 4:[41, 7, 12, 0, 0].w= 3.
Everything between w and r is always a gap, so each swap moves a pastry forward and a gap backward. Pastries are placed in the order they are met, which keeps their order.
function compactTray(tray) {
let w = 0; // next slot that should get a pastry
for (let r = 0; r < tray.length; r++) {
if (tray[r] !== 0) {
[tray[w], tray[r]] = [tray[r], tray[w]];
w++;
}
}
}def compact_tray(tray):
w = 0 # next slot that should get a pastry
for r in range(len(tray)):
if tray[r] != 0:
tray[w], tray[r] = tray[r], tray[w]
w += 1Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.