algoadvance

Leetcode 2460. Apply Operations to an Array

Problem Statement

Given an array nums of size n, you need to apply the following operations:

  1. For each index i from 0 to n-2 (inclusive), check if nums[i] is equal to nums[i+1]. If they are equal, set nums[i] to 2 * nums[i] and nums[i+1] to 0.
  2. After completing the first step, you need to move all 0s to the end of the array while maintaining the relative order of the non-zero elements.

Return the resulting array after the operations have been applied.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the array?
    • What are the possible ranges for the values within the array?
  2. Expected Outputs:
    • Should we modify the array in place or return a new array?
  3. Example Cases:
    • Can provide sample inputs and outputs to ensure understanding.

Example

Given input nums = [1, 2, 2, 1, 1, 0]:

  1. After step 1, the array will transform to: [1, 4, 0, 2, 0, 0]
  2. After step 2, moving all zeros to the end, the final array will be: [1, 4, 2, 0, 0, 0]

Strategy

  1. Iterate through the array and apply the operation described in step 1.
  2. Create a new array or use a two-pointer technique to move all zeros to the end while maintaining the relative order of non-zero elements.

Time Complexity

The overall time complexity is O(n):

Code

#include <vector>

std::vector<int> applyOperations(std::vector<int>& nums) {
    int n = nums.size();
    
    // Step 1: Apply the operations to combine equal elements.
    for (int i = 0; i < n - 1; ++i) {
        if (nums[i] == nums[i + 1]) {
            nums[i] = nums[i] * 2;
            nums[i + 1] = 0;
        }
    }
    
    // Step 2: Move all zeros to the end.
    std::vector<int> result;
    result.reserve(n);

    // Add non-zero elements first.
    for (int i = 0; i < n; ++i) {
        if (nums[i] != 0) {
            result.push_back(nums[i]);
        }
    }

    // Add zeros at the end.
    while (result.size() < n) {
        result.push_back(0);
    }

    return result;
}

Explanation

  1. Step 1: Iterate over the array from the beginning to the second last element. For each pair of consecutive elements that are equal, double the first element and set the second to zero.
  2. Step 2: Use a secondary array result to put all non-zero elements in their original relative order and then append zeros until the array has the same length as the original nums.

This approach ensures that we efficiently transform and rearrange the elements within the given array while maintaining a linear time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI