Zero Shifter — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, move all occurrences of 0 to the end while maintaining the relative order of the non‑zero elements. The operation must be performed in‑place using O(1) additional memory. Return the modified array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Zero Shifter"
WHY DOES IT MATTER?
This pattern is essential for in-place array manipulation problems where you need to partition elements based on a condition. It is a foundational technique for more complex problems like 'Dutch National Flag' (sorting 0s, 1s, and 2s) and 'Move Zeroes' variants. Mastering this ensures you can solve a wide range of array partitioning problems efficiently.
OPTIMIZATION CHALLENGE
The key insight is that you don't need to swap elements immediately. Instead, you can overwrite zeros with non-zero elements as you find them. This avoids the overhead of swapping and ensures that the relative order of non-zero elements is preserved. The challenge is to correctly manage the write pointer so that you don't overwrite non-zero elements that haven't been processed yet.
REAL-WORLD CONNECTION
Think of this as cleaning up a log file where '0' represents a corrupted or empty entry. You want to move all valid entries to the top of the log for easier processing, while pushing the corrupted entries to the end. This is analogous to data compaction in databases, where valid records are moved to the front of a page, and deleted or invalid records are marked or moved to the end for later cleanup.
In an interview, explicitly state that you are using a two-pointer approach with a 'write' index. Emphasize that this approach is stable (preserves order) and runs in linear time. If asked about edge cases, mention empty arrays and arrays with all zeros or all non-zeros.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The 'Zero Shifter' problem is a classic application of the Two-Pointer technique, specifically the 'Slow-Fast' or 'Write-Index' pattern. The core theoretical challenge is to partition an array into two segments—non-zero elements and zero elements—without using extra memory. A naive approach might involve creating a new array to store non-zero elements and then appending zeros, but this violates the O(1) space constraint. The optimal paradigm relies on the observation that we only need to track where the next non-zero element should be placed. By maintaining a 'write' pointer that starts at the beginning of the array, we can overwrite zeros with non-zero values as we scan through the array with a 'read' pointer. This effectively compacts the non-zero elements to the front while preserving their relative order.
Interview Questions on This Problem
Q1How would you modify the Zero Shifter algorithm to move all occurrences of a specific value (e.g., 5) to the end instead of 0?
The logic remains identical. You simply change the condition in the loop. Instead of checking if nums[i] != 0, you check if nums[i] != targetValue. The write pointer still tracks the position for the next valid (non-target) element. This demonstrates that the pattern is generic for any 'partition by value' problem.
Q2In a distributed system, if this array represented a queue of tasks where '0' means 'null task', how would you handle this in-place if the array was too large to fit in memory?
If the array is too large for memory, you cannot perform a true in-place operation on the entire dataset simultaneously. You would need to process it in chunks (streaming). However, for the in-memory constraint, the two-pointer approach is optimal. If the question implies external sorting or disk-based processing, you would read chunks, filter out zeros, write non-zeros to a temporary buffer, and then append zeros. But for standard interview constraints, the in-place two-pointer is the expected answer.
Q3What is the time complexity of the Zero Shifter algorithm, and why is it optimal?
The time complexity is O(n), where n is the length of the array. This is optimal because every element must be inspected at least once to determine if it is zero or non-zero. The space complexity is O(1) because we only use a constant number of extra variables (the write pointer and loop counter). No other algorithm can do better than O(n) time since we must look at every element.
Examples
Input
[0,1,0,3,12]
Output
[1,3,12,0,0]
Explanation: Start with two pointers i and j at the beginning. i scans each element; when a non‑zero is found it is written at position j and j is incremented. After the scan, positions j…end are filled with 0. The resulting order is 1,3,12 followed by two zeros.
Input
[4,0,5,0,0,3,2]
Output
[4,5,3,2,0,0,0]
Explanation: Non‑zero values 4,5,3,2 are collected in their original order and placed at the front. The remaining three slots are set to 0, giving the final array.
Input
[0,0,0,7]
Output
[7,0,0,0]
Explanation: Only one non‑zero (7) is moved to the first position; the three trailing positions become 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The algorithm must run in O(n) time
- Only O(1) extra space may be used
Optimal Approach & Strategy
Use a two-pointer technique where a 'write' pointer tracks the position for the next non-zero element. Iterate through the array with a 'read' pointer, and whenever a non-zero element is found, write it to the 'write' pointer's position and increment the 'write' pointer. After the loop, fill the remaining positions with zeros.
Brute Force Approach
Create a new array to store all non-zero elements in their original order, then append zeros to the end of this new array. Finally, copy the contents of the new array back into the original array.
Verified Code Solutions
// In‑place two‑pointer solution.
function moveZeroes(nums){
let insertPos = 0;
for(let i=0;i<nums.length;i++){
if(nums[i]!==0){
nums[insertPos++] = nums[i];
}
}
while(insertPos<nums.length){
nums[insertPos++] = 0;
}
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
let nums = [];
if(input.length>0){
try{ nums = JSON.parse(input); }catch(e){ nums = input.split(/\s+/).map(Number); }
}
moveZeroes(nums);
process.stdout.write(JSON.stringify(nums));#include <bits/stdc++.h>
using namespace std;
// Two‑pointer approach: keep a position for the next non‑zero element.
void moveZeroes(vector<int>& nums){
size_t insertPos = 0;
for(size_t i=0;i<nums.size();++i){
if(nums[i]!=0){
nums[insertPos++] = nums[i];
}
}
while(insertPos<nums.size()) nums[insertPos++] = 0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int &x:nums) cin>>x;
moveZeroes(nums);
for(int i=0;i<n;++i){
if(i) cout<<' ';
cout<<nums[i];
}
cout<<"\n";
return 0;
}import java.io.*;
import java.util.*;
public class Main {
// Two‑pointer in‑place algorithm.
public static void moveZeroes(int[] nums) {
int insertPos = 0;
for (int num : nums) {
if (num != 0) {
nums[insertPos++] = num;
}
}
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.trim().isEmpty()) {
System.out.println("[]");
return;
}
line = line.trim();
int[] nums;
if (line.startsWith("[")) {
line = line.replaceAll("\\[|\\]|\\s", "");
if (line.isEmpty()) {
nums = new int[0];
} else {
String[] parts = line.split(",");
nums = new int[parts.length];
for (int i = 0; i < parts.length; i++) nums[i] = Integer.parseInt(parts[i]);
}
} else {
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
nums = new int[n];
int idx = 0;
while (st.hasMoreTokens() && idx < n) {
nums[idx++] = Integer.parseInt(st.nextToken());
}
while (idx < n) {
String extra = br.readLine();
if (extra == null) break;
StringTokenizer st2 = new StringTokenizer(extra);
while (st2.hasMoreTokens() && idx < n) {
nums[idx++] = Integer.parseInt(st2.nextToken());
}
}
}
moveZeroes(nums);
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 0; i < nums.length; i++) {
if (i > 0) sb.append(',');
sb.append(nums[i]);
}
sb.append(']');
System.out.println(sb.toString());
}
}def move_zeroes(nums):
"""In‑place two‑pointer solution moving zeros to the end."""
insert_pos = 0
for num in nums:
if num != 0:
nums[insert_pos] = num
insert_pos += 1
while insert_pos < len(nums):
nums[insert_pos] = 0
insert_pos += 1
if __name__ == "__main__":
import sys, json
data = sys.stdin.read().strip()
if not data:
arr = []
else:
try:
arr = json.loads(data)
except json.JSONDecodeError:
arr = list(map(int, data.split()))
move_zeroes(arr)
print(json.dumps(arr))// In‑place two‑pointer solution.
function moveZeroes(nums){
let insertPos = 0;
for(let i=0;i<nums.length;i++){
if(nums[i]!==0){
nums[insertPos++] = nums[i];
}
}
while(insertPos<nums.length){
nums[insertPos++] = 0;
}
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
let nums = [];
if(input.length>0){
try{ nums = JSON.parse(input); }catch(e){ nums = input.split(/\s+/).map(Number); }
}
moveZeroes(nums);
process.stdout.write(JSON.stringify(nums));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.