Duplicate Zeros - Practice Coding Problems

Duplicate Zeros - Problem

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note: Elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Input & Output

Example 1 — Basic Duplication

$ Input: arr = [1,0,2,3,0,4,5,0]

› Output: [1,0,0,2,3,0,0,4]

💡 Note: Each zero is duplicated, shifting remaining elements right. Elements 5,0 are dropped as they exceed array length.

Example 2 — No Zeros

$ Input: arr = [1,2,3]

› Output: [1,2,3]

💡 Note: No zeros to duplicate, array remains unchanged.

Example 3 — All Zeros

$ Input: arr = [0,0,0]

› Output: [0,0,0]

💡 Note: First zero is duplicated, second zero pushes remaining elements out of bounds.

Constraints

1 ≤ arr.length ≤ 10⁴
0 ≤ arr[i] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with zeros to duplicate

Duplicate Process

Each zero creates a copy, elements shift right

Final Result

Modified array with excess elements dropped

Key Takeaway

🎯 Key Insight: Work backwards to avoid overwriting elements before they're processed

Asked in

🍎 Apple 15 Ⓜ️ Microsoft 12

The key insight is to work backwards to avoid overwriting unprocessed elements. Best approach is the two-pass method: first count duplicable zeros, then place elements from right to left. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Extra Array	O(n)	O(n)	Create a new array and copy elements with zero duplication
Two-Pass Approach	O(n)	O(1)	First count zeros, then place elements from right to left

Brute Force - Extra Array — Algorithm Steps

Create auxiliary array of same size
Iterate through original array copying elements
When zero found, add it twice to auxiliary array
Copy auxiliary array back to original

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Start with input array

Copy with Duplication

Create temp array, duplicate zeros

Copy Back

Copy result back to original array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* arr, int size) {
    int* temp = (int*)malloc(size * sizeof(int));
    int tempSize = 0;
    
    for (int i = 0; i < size && tempSize < size; i++) {
        temp[tempSize++] = arr[i];
        if (arr[i] == 0 && tempSize < size) {
            temp[tempSize++] = 0;
        }
    }
    
    // Copy back to original array
    for (int i = 0; i < tempSize; i++) {
        arr[i] = temp[i];
    }
    
    free(temp);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int arr[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    solution(arr, size);
    
    // Print result
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array to copy elements

✓ Linear Growth

Space Complexity

O(n)

Auxiliary array of size n for temporary storage

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Extra Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler