Scale Engineer

Apply Operations to an Array

Easy
#2244Time: O(n) - The first loop runs `n-1` times, and the second loop runs `n` times. This gives a total time complexity of O(n-1 + n) which simplifies to O(n).Space: O(n) - We use an additional array `result` of size `n` to store the final arrangement.
Patterns
Two Pointers
Data structures
Array

Prompt

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 ith operation (0-indexed), you will apply the following on the ith 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.

 

Example 1:

Input: nums = [1,2,2,1,1,0]
Output: [1,4,2,0,0,0]
Explanation: We do the following operations:
- i = 0: nums[0] and nums[1] are not equal, so we skip this operation.
- i = 1: nums[1] and nums[2] are equal, we multiply nums[1] by 2 and change nums[2] to 0. The array becomes [1,4,0,1,1,0].
- i = 2: nums[2] and nums[3] are not equal, so we skip this operation.
- i = 3: nums[3] and nums[4] are equal, we multiply nums[3] by 2 and change nums[4] to 0. The array becomes [1,4,0,2,0,0].
- i = 4: nums[4] and nums[5] are equal, we multiply nums[4] by 2 and change nums[5] to 0. The array becomes [1,4,0,2,0,0].
After that, we shift the 0's to the end, which gives the array [1,4,2,0,0,0].

Example 2:

Input: nums = [0,1]
Output: [1,0]
Explanation: No operation can be applied, we just shift the 0 to the end.

 

Constraints:

  • 2 <= nums.length <= 2000
  • 0 <= nums[i] <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the problem statement in two distinct phases. First, it applies all the operations on the input array. Second, it creates a new array and populates it with the non-zero elements from the modified input array, effectively shifting all zeros to the end.

Algorithm

    1. Iterate from i = 0 to n-2 on the nums array.
    1. If nums[i] equals nums[i+1], update nums[i] = nums[i] * 2 and nums[i+1] = 0.
    1. Create a new integer array result of size n.
    1. Initialize a writeIndex to 0.
    1. Iterate through the modified nums array.
    1. If the current element num is not 0, set result[writeIndex] = num and increment writeIndex.
    1. Return the result array.

Walkthrough

Phase 1: Apply Operations

We iterate through the nums array from the first element up to the second-to-last element (i from 0 to n-2). In each iteration, we check if nums[i] is equal to nums[i+1]. If they are equal, we double nums[i] and set nums[i+1] to zero. This is done in-place on the original nums array.

Phase 2: Shift Zeros

We create a new array, result, of the same size n, which is by default initialized with zeros in Java. We use a pointer, writeIndex, initialized to 0, to keep track of the next position to fill in the result array. We iterate through the modified nums array. For each element, if it's not zero, we copy it to result[writeIndex] and increment writeIndex. After iterating through all elements of nums, the result array will contain all non-zero elements at the beginning, followed by zeros.

class Solution {    public int[] applyOperations(int[] nums) {        int n = nums.length;         // Phase 1: Apply operations        for (int i = 0; i < n - 1; i++) {            if (nums[i] == nums[i + 1]) {                nums[i] *= 2;                nums[i + 1] = 0;            }        }         // Phase 2: Shift zeros to the end using an extra array        int[] result = new int[n];        int writeIndex = 0;        for (int num : nums) {            if (num != 0) {                result[writeIndex++] = num;            }        }                return result;    }}

Complexity

Time

O(n) - The first loop runs `n-1` times, and the second loop runs `n` times. This gives a total time complexity of O(n-1 + n) which simplifies to O(n).

Space

O(n) - We use an additional array `result` of size `n` to store the final arrangement.

Trade-offs

Pros

  • Simple to understand and implement as it directly follows the problem description's two steps.

Cons

  • Uses extra space proportional to the input size, which is inefficient for large arrays.

Solutions

class Solution {public  int[] applyOperations(int[] nums) {    int n = nums.length;    for (int i = 0; i < n - 1; ++i) {      if (nums[i] == nums[i + 1]) {        nums[i] <<= 1;        nums[i + 1] = 0;      }    }    int[] ans = new int[n];    int i = 0;    for (int x : nums) {      if (x > 0) {        ans[i++] = x;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem