Apply Operations to an Array - Practice Coding Problems

Apply Operations to an Array - Problem

You are given a 0-indexed array nums of size n consisting of non-negative integers.

You need to apply n - 1 operations to this array where, in the i^th operation (0-indexed), you will apply the following on the i^th element of nums:

If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation.

After performing all the operations, shift all the 0's to the end of the array.

For example, the array [1,0,2,0,0,1] after shifting all its 0's to the end, is [1,2,1,0,0,0].

Return the resulting array.

Note that the operations are applied sequentially, not all at once.

Input & Output

Example 1 — Basic Doubling

$ Input: nums = [2,2,1,1,0]

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

💡 Note: First operation: nums[0] == nums[1] so 2*2=4, nums becomes [4,0,1,1,0]. Second operation: nums[2] == nums[3] so 1*2=2, nums becomes [4,0,2,0,0]. After shifting zeros: [4,2,0,0,0]

Example 2 — No Matching Pairs

$ Input: nums = [0,1]

› Output: [1,0]

💡 Note: First operation: nums[0] != nums[1] (0 != 1), so no change. Array remains [0,1]. After shifting zeros to end: [1,0]

Example 3 — Multiple Operations

$ Input: nums = [1,2,2,1,1,0]

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

💡 Note: Operation at index 1: nums[1] == nums[2] so 2*2=4, becomes [1,4,0,1,1,0]. Operation at index 3: nums[3] == nums[4] so 1*2=2, becomes [1,4,0,2,0,0]. After shifting zeros: [1,4,2,0,0,0]

Constraints

2 ≤ nums.length ≤ 2000
0 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

[2,2,1,1,0] - array with adjacent equal pairs

Apply Operations

Double equal adjacent pairs: 2,2→4,0 and 1,1→2,0

Move Zeros

[4,2,0,0,0] - all zeros moved to end

Key Takeaway

🎯 Key Insight: Sequential operations create zeros that need to be moved to the end efficiently

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to process operations sequentially since each change affects subsequent comparisons, then efficiently move zeros to the end. The optimal approach uses in-place two-pointer technique after applying operations. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Two Pass Approach	O(n)	O(n)	Apply operations sequentially, then shift all zeros to end
Optimized - In-Place Two Pointers	O(n)	O(1)	Apply operations then use two pointers to move zeros in-place

Brute Force - Two Pass Approach — Algorithm Steps

Step 1: Apply n-1 operations sequentially, doubling when nums[i] == nums[i+1]
Step 2: Create result array by collecting non-zero elements first
Step 3: Fill remaining positions with zeros

Visualization

Tap to expand

Step-by-Step Walkthrough

Apply Operations

Process each adjacent pair sequentially

Collect Non-zeros

Gather all non-zero elements

Add Zeros

Fill remaining positions with zeros

Code -

solution.c — C

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

int* solution(int* nums, int numsSize, int* returnSize) {
    // Apply n-1 operations sequentially
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            nums[i] *= 2;
            nums[i + 1] = 0;
        }
    }
    
    // Create result array
    int* result = (int*)malloc(numsSize * sizeof(int));
    int writePos = 0;
    
    // Collect non-zero elements
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 0) {
            result[writePos++] = nums[i];
        }
    }
    
    // Fill remaining with zeros
    while (writePos < numsSize) {
        result[writePos++] = 0;
    }
    
    *returnSize = numsSize;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int nums[100];
    int size = 0;
    char* ptr = line + 1; // Skip [
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass for operations (O(n)) plus single pass to collect non-zeros (O(n))

✓ Linear Growth

Space Complexity

O(n)

Extra array to store the result with non-zeros and zeros separated

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

245 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 - Two Pass Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler