algoadvance

Leetcode 2460. Apply Operations to an Array

Problem Statement

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 (0 <= i < n - 1) operation, you will apply the following on the i-th element of nums:

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

Return the resulting array.

Clarifying Questions

  1. What should we do if the array is empty?
    • Since all elements are non-negative integers and the problem doesn’t specify any constraints about empty arrays, we can assume the array won’t be empty.
  2. Are we allowed to modify the input array directly?
    • Yes, modifying the input array directly is fine as we need to return the transformed array.
  3. How should we handle edge cases like a single-element array?
    • For a single-element array, no operations will be performed, and the output should be the same as the input.

Strategy

  1. Perform Pairwise Operations: Iterate through the array from left to right and apply the given operation (nums[i] == nums[i + 1]).
  2. Shift Non-Zeros: Create a new array to store non-zero elements first, followed by zeroes.
  3. Result Formation: Construct the resultant array by first adding non-zero numbers found and then adding the requisite number of zeroes at the end.

Here’s the implementation of the stated strategy:

Code

public class Solution {
    public int[] applyOperations(int[] nums) {
        int n = nums.length;
        
        // Apply operations (nums[i] == nums[i + 1])
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }

        // Create an array to store the result
        int[] result = new int[n];
        int index = 0; // Index for the result array
        
        // Add all non-zero elements from the modified nums to result
        for (int num : nums) {
            if (num != 0) {
                result[index++] = num;
            }
        }
        
        // The rest of the elements will be zero by default (as array initialized to zeros)
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Test example
        int[] nums = {1, 2, 2, 1, 1, 0};
        int[] result = sol.applyOperations(nums);
        
        // Print the result
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

Therefore, the overall time complexity is O(n), where n is the length of the input array. This is optimal given that we need to process each element at least once.

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