DSA SheetEasy
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Apply Operations to an Array

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 28

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe operation phase and the zero-shifting phase have different jobs

The first part of the problem is a left-to-right simulation. At index i, you must compare the current value with the value immediately to its right. If they match, the left value changes and the right value becomes zero. That new zero is part of the array state seen by the next operation, so the scan must use the modified array rather than the original values.

After every adjacent operation has happened, no more merging is allowed. The remaining task is stable compaction: read the array from left to right, copy each non-zero value into the next available position, and leave all positions after that filled with zero. Because values are copied in their original order, the non-zero order is preserved.

A left-to-right merge scan followed by stable zero compactionThe picture shows an array being handled in two passes. In the first pass, a merge pointer moves from the leftmost index toward index n - 2, comparing each value with its neighbor; an equal pair becomes a doubled value followed by zero. In the second pass, a write pointer starts at the left and receives each non-zero value as the array is read from left to right, leaving a suffix of zeros. The key observation is that merging is ordered simulation, while shifting zeros is stable compaction.224050404050404050445000in-place: 2,2 → 4,0merge scanequal pairinputafter merge012345ii visits 0 through n − 2stable zero compactionafter mergepacked outputw = 3, next writezero suffixnon-zero values move forward in their original order; remaining slots become zero

Approach

  1. Store n, the array length, so both passes use the same fixed boundary and the last comparison stops at index n - 2.
  2. Scan i from 0 to n - 2 and compare nums[i] with nums[i + 1]. The operation is sequential, so each comparison must see changes made by earlier comparisons.
  3. When the adjacent values are equal, double nums[i] and set nums[i + 1] to zero. The zero prevents the newly doubled value from being merged again with the next position during this pass.
  4. Create a result array of n zeros. Starting with zeros means every position not reached by a non-zero value already has its required final value.
  5. Scan nums from left to right and maintain idx as the next result position. Copy each non-zero x into result[idx] and increment idx, because skipping zeros is exactly the required shift and this order keeps non-zero values stable.
  6. Return result after the scan. Every original slot contributes either one copied non-zero value or one zero in the untouched suffix, so the returned length remains n.

Complexitytwo linear passes and output-sized storage

MEASUREBOUNDWHY
TimeO(n)The merge pass performs one comparison per adjacent pair, and the compaction pass reads each element once. The passes are separate but each touches at most n positions, so their total work is still linear.
SpaceO(1) extraThe result array uses O(n) space, but it is the required returned output and is excluded. Apart from that output, the algorithm stores only n, i, idx, and x; the bound does not worsen for any input shape.
Here n denotes nums.length. The returned array is required output storage and is excluded from the extra-space bound.

Annotated solutionC++ · two passes · simulation followed by stable compaction

CPPApply all adjacent operations in order, then copy non-zero values into a zero-filled result.
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }

        vector<int> result(n, 0);
        int idx = 0;
        for (int x : nums) {
            if (x != 0) {
                result[idx++] = x;
            }
        }

        return result;
    }
};

The boundary n - 1 is essential because nums[i + 1] must exist. The second pass does not try to move each zero individually; it only records where the next useful value belongs. Since result starts entirely at zero, the part after idx needs no separate shifting loop.

The in-place alternativean allocation-saving arrangement that reuses nums

You can avoid the separate result array by compacting the modified nums itself. This is a genuine space optimisation: the required output remains the same, but the algorithm uses no output-sized auxiliary vector. It also makes the input array hold the final answer, so use this version only when mutating nums is acceptable.

CPPReuse nums as the destination: write non-zero values forward, then fill the remaining suffix with zeros.
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }

        int write = 0;
        for (int read = 0; read < n; ++read) {
            if (nums[read] != 0) {
                nums[write++] = nums[read];
            }
        }

        while (write < n) {
            nums[write++] = 0;
        }

        return nums;
    }
};

The read pointer always moves forward, while write never moves ahead of read because each copied value occupies the earliest unused position. That makes the compaction stable. The final loop restores zeros in every remaining slot; without it, old non-zero values could remain at the end after being overwritten earlier.

Common mistakesthe two lines that change the meaning of the scan

Previous · Rotate Array