Move Zeroes

📋

Problem

Imagine organizing a shelf where all empty boxes (zeroes) need to be moved to the end without disturbing the order of the other items.

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.

1 ≤ nums.length ≤ 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1

Edge cases: All elements are zero → output is the same arrayNo zero elements → array remains unchangedSingle element array with zero → array remains the same

</>

IDE

def moveZeroes(nums: list[int]) -> None:public void moveZeroes(int[] nums)void moveZeroes(vector<int>& nums)function moveZeroes(nums)

def moveZeroes(nums):
    # Write your solution here
    pass

class Solution {
    public void moveZeroes(int[] nums) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void moveZeroes(vector<int>& nums) {
    // Write your solution here
}

function moveZeroes(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [0,1,3,12,0]Swapping zero with next non-zero element without preserving order causes misplaced zeroes.✅ Use two-pointer overwrite approach instead of swapping to maintain order.

Wrong: [1,3,12,0,0,0]Output length longer than input due to extra elements added mistakenly.✅ Ensure in-place modification without changing array size.

Wrong: [0]Single element zero array changed or code crashes on empty or single element input.✅ Add checks for empty or single element arrays to avoid errors or unnecessary changes.

Wrong: [1,2,3,4,5,0]Appending zeroes even when none exist in input, increasing array size.✅ Do not add extra zeroes beyond original array length.

Wrong: Solution exceeds time limit on large inputs due to inefficient algorithm.✅ Implement O(n) two-pointer in-place solution to avoid TLE.

✓

Test Cases

Try testing your solution on empty and single-element arrays to catch base case bugs.

Consider tricky inputs with multiple zeroes interspersed to catch order preservation bugs.

Test your solution on large inputs to ensure it runs efficiently within time limits.

t1_01basic

Input{"nums":[0,1,0,3,12]}

Expected[1,3,12,0,0]

⏱ Performance - must finish in 2000ms

All zeroes are moved to the end, and the order of non-zero elements (1,3,12) is preserved.

💡 Try using two pointers to track positions for non-zero elements.

💡 Use one pointer to iterate and another to place non-zero elements in order.

💡 Overwrite non-zero elements at the front and fill remaining positions with zeroes.

Why it failed: Output does not preserve order or zeroes are not moved correctly. Fix by ensuring non-zero elements are copied in order and zeroes appended after.

✓ Correctly moves zeroes to the end while preserving order.

t1_02basic

Input{"nums":[4,2,4,0,0,3,0,5,1,0]}

Expected[4,2,4,3,5,1,0,0,0,0]

⏱ Performance - must finish in 2000ms

All zeroes moved to the end; non-zero elements (4,2,4,3,5,1) keep original order.

💡 Focus on maintaining relative order of non-zero elements.

💡 Track the position to place next non-zero element while iterating.

💡 After placing all non-zero elements, fill the rest with zeroes.

Why it failed: Zeroes not all moved to the end or order of non-zero elements changed. Fix by using a pointer to place non-zero elements sequentially.

✓ Correctly partitions zero and non-zero elements preserving order.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array remains unchanged.

💡 Consider what happens when the input array is empty.

💡 Your code should handle zero-length arrays without errors.

💡 Return immediately or handle empty input gracefully.

Why it failed: Code crashes or modifies empty array incorrectly. Fix by adding a check for empty input or ensuring loops handle zero length.

✓ Handles empty input without errors.

t2_02edge

Input{"nums":[0]}

Expected[0]

⏱ Performance - must finish in 2000ms

Single element zero array remains unchanged.

💡 Test behavior with single element arrays.

💡 Ensure no unnecessary swaps or changes occur.

💡 Return early or handle single element correctly.

Why it failed: Single zero element changed or code errors. Fix by handling single element arrays without modification.

✓ Correctly handles single zero element.

t2_03edge

Input{"nums":[7]}

Expected[7]

⏱ Performance - must finish in 2000ms

Single element non-zero array remains unchanged.

💡 Check single element non-zero input.

💡 No zeroes to move, array should remain same.

💡 Avoid unnecessary operations on single element.

Why it failed: Single non-zero element changed or code errors. Fix by skipping unnecessary operations for single element arrays.

✓ Correctly handles single non-zero element.

t3_01corner

Input{"nums":[0,0,1,0,3,0,12,0,0]}

Expected[1,3,12,0,0,0,0,0,0]

⏱ Performance - must finish in 2000ms

Multiple zeroes interspersed; order of non-zero elements preserved.

💡 Beware of swapping zeroes with non-zero elements multiple times.

💡 Use a single pointer to track position for next non-zero element.

💡 Avoid swapping zeroes unnecessarily; overwrite non-zero elements first.

Why it failed: Incorrect order due to swapping zeroes multiple times. Fix by using overwrite approach instead of swapping.

✓ Correctly handles multiple zeroes interspersed.

t3_02corner

Input{"nums":[1,2,3,4,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

No zero elements; array remains unchanged.

💡 Check if code unnecessarily modifies arrays without zeroes.

💡 Ensure zero count or pointer logic does not alter array.

💡 Return early or skip zero moving if none found.

Why it failed: Array changed despite no zeroes present. Fix by skipping zero moving if zero count is zero.

✓ Correctly leaves no-zero array unchanged.

t3_03corner

Input{"nums":[0,1,0,0,2,0,3,0,4,0]}

Expected[1,2,3,4,0,0,0,0,0,0]

⏱ Performance - must finish in 2000ms

Zeros interleaved with non-zero elements; order preserved.

💡 Avoid greedy swaps that move zeroes forward incorrectly.

💡 Use two pointers moving in same direction to partition array.

💡 Overwrite non-zero elements at front, then fill zeroes after.

Why it failed: Greedy swap approach fails to preserve order or moves zeroes incorrectly. Fix by using two-pointer overwrite method.

✓ Correctly partitions zero and non-zero elements preserving order.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000; O(n) time complexity required to complete within 2 seconds.

💡 Aim for a single pass O(n) solution.

💡 Avoid nested loops or extra space proportional to n.

💡 Use two pointers to move zeroes in-place efficiently.

Why it failed: Solution exceeds time limit due to O(n^2) or extra space usage. Fix by implementing O(n) two-pointer in-place approach.

✓ Solution runs within time limit using O(n) two-pointer approach.

Practice

1. Consider the following Python code that counts pairs with absolute difference at most K using binary search. What is the final output when the input is nums = [1, 2, 5] and K = 3?

import bisect

def count_pairs_binary_search(nums, K):
    count = 0
    n = len(nums)
    for i in range(n - 1):
        target = nums[i] + K
        j = bisect.bisect_right(nums, target, i + 1) - 1
        if j > i:
            count += j - i
    return count

print(count_pairs_binary_search([1, 2, 5], 3))

easy

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Trace iteration i=0

   nums[0] = 1, target = 1 + 3 = 4. bisect_right(nums, 4, 1) returns index 2 (nums[2]=5 >4), so j = 2 - 1 = 1. Count += 1 - 0 = 1.

2. Step 2: Trace iteration i=1

   nums[1] = 2, target = 2 + 3 = 5. bisect_right(nums, 5, 2) returns 3 (end of list), so j = 3 - 1 = 2. Count += 2 - 1 = 1. Total count = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Pairs are (1,2) and (2,5) with differences 1 and 3 respectively [OK]

Hint: Check bisect_right returns and subtract 1 carefully [OK]

Common Mistakes:

• Off-by-one error in bisect index adjustment
• Counting pairs where i >= j
• Miscomputing target as nums[i] - K

2. You are given an array representing heights of bars where water can be trapped between bars after raining. Which approach guarantees an optimal O(n) time and O(1) space solution to calculate the total trapped water?

easy

A. Use two pointers starting from opposite ends, updating left_max and right_max while moving inward.

B. Use a greedy approach that always fills the lowest bar first without considering future bars.

C. Use dynamic programming with a 2D table storing water trapped between every pair of bars.

D. Use a brute force nested loop to find max heights on left and right for each bar.

Solution

1. Step 1: Understand problem constraints

   The problem requires calculating trapped water efficiently in linear time and constant space.

2. Step 2: Identify approach matching constraints

   The two pointers approach moves inward from both ends, updating left_max and right_max, allowing O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers approach is known optimal for trapping rain water [OK]

Hint: Two pointers from ends -> O(n) time, O(1) space [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing DP with 2D tables for this problem
• Thinking greedy fill lowest bar always works

3. Suppose the 4Sum problem is modified so that elements can be reused multiple times in quadruplets (i.e., indices can repeat). Which modification to the optimal hash map approach correctly handles this variant?

hard

A. Remove the index overlap check and allow all pairs to combine freely.

B. Use the same hash map approach but skip sorting the array to allow duplicates.

C. Modify the pair combination step to allow pairs with overlapping indices and remove index checks, but ensure quadruplets are sorted and unique.

D. Switch to brute force four nested loops since hash map approach cannot handle reuse.

Solution

1. Step 1: Understand reuse means indices can repeat

   Index overlap check must be removed or relaxed to allow repeated elements.

2. Step 2: Adjust pair combination logic

   Allow pairs with overlapping indices but still sort quadruplets and use a set to avoid duplicates.

3. Step 3: Evaluate other options

   Removing sorting breaks duplicate handling; brute force is inefficient; simply removing checks without sorting leads to duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Allow index overlap but keep sorting and deduplication [OK]

Hint: Allow index overlap but keep sorting and deduplication [OK]

Common Mistakes:

• Removing sorting causes duplicates
• Assuming brute force is only solution

4. Suppose the problem is extended so that the backspace character '#' can be repeated multiple times consecutively, and you want to optimize the algorithm to handle very long sequences of '#' efficiently. Which modification to the two-pointer forward approach is most appropriate?

hard

A. Process the strings from the end with two pointers, skipping characters affected by consecutive backspaces on the fly.

B. Modify the algorithm to skip over consecutive '#' characters by counting them and adjusting the write pointer accordingly in one step.

C. Use a stack to push characters and pop for each '#' to handle multiple backspaces efficiently.

D. Preprocess the strings by removing all '#' characters before comparison.

Solution

1. Step 1: Understand the challenge with consecutive backspaces

   Multiple consecutive '#' characters can cause multiple deletions, which can be inefficient if processed one by one in a forward pass.

2. Step 2: Identify the best approach

   Processing from the end with two pointers allows skipping over characters affected by multiple backspaces efficiently without reconstructing strings or counting '#' explicitly.

3. Step 3: Why other options fail

   Counting '#' forward is complex and error-prone; stacks use extra space; preprocessing removes needed info and breaks order.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backward two-pointer approach handles consecutive backspaces efficiently [OK]

Hint: Backward two-pointer skips multiple backspaces efficiently [OK]

Common Mistakes:

• Trying to count '#' forward complicates logic
• Using stacks increases space unnecessarily
• Preprocessing removes order and breaks correctness

5. If the problem changes so that elements equal to val can appear multiple times and must be removed, but the array is read-only and cannot be modified in-place, which approach is correct?

hard

A. Use the two pointers swap approach to modify the array in-place

B. Use the brute force nested loop shifting approach

C. Create a new array and copy only elements not equal to val, returning its length

D. Sort the array and then remove val elements by slicing

Solution

1. Step 1: Understand read-only constraint

   Cannot modify input array in-place, so approaches that swap or shift in-place are invalid.

2. Step 2: Choose correct approach

   Creating a new array copying only allowed elements respects read-only constraint and removes val elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   New array creation is necessary when input is immutable [OK]

Hint: Read-only input -> must copy to new array [OK]

Common Mistakes:

• Trying to modify read-only array in-place
• Using inefficient nested loops unnecessarily