Funcia
Lv.1arraytwo-pointers

Move Zeros to the End

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A bookshelf is given as shelf: each slot holds a book number, and an empty slot is 0. Move every book to the front keeping the books in their original order, with all empty slots at the back, and return the resulting shelf.

Examples

shelfresult
[0, 1, 0, 3, 12][1, 3, 12, 0, 0]
[0, 0, 0][0, 0, 0]
[4, 2, 0, 2, 0, 7][4, 2, 2, 7, 0, 0]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(shelf: int[]) → int[]

Constraints

  • 1≤1 \le shelf.length ≤200,000\le 200{,}000
  • 0≤0 \le shelf[i] ≤109\le 10^9 (0 is an empty slot)

Expected complexity

Time
O(N)
Space
O(1) extra

Examples

shelfExpected
[0,1,0,3,12][1,3,12,0,0]
[0,0,0][0,0,0]
[4,2,0,2,0,7][4,2,2,7,0,0]

Hint

Hint

Keep a write pointer w. Scan left to right; for every non-zero value, write it to shelf[w] and advance w. Then fill from w to the end with 0. Shifting the rest of the array (or swapping a zero step by step to the end) for every empty slot is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251308 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.