2460. Apply Operations to an Array

EasyArraySimulation

Problem Description

In this problem, you are given an array of non-negative integers. Your task is to perform a series of operations on this array, specifically n - 1 operations where n is the size of the array. Each operation is performed on the ith element of the array (considering 0-indexing), following these rules:

Check if the ith element of the array (nums[i]) is equal to the next element (nums[i + 1]).
If they are equal, double the ith element (nums[i] = nums[i] * 2) and set the i + 1th element to 0.
If they are not equal, move on to the next operation without making changes to the current ith element.

After you have performed all the operations, you need to shift all the 0's in the array to the end, while preserving the order of the non-zero elements. The challenge is to perform these operations sequentially and then return the modified array.

Example: Given an array [1,0,2,0,0,1], after performing all the operations and shifting the 0's, the resulting array would be [1,2,1,0,0,0].

Intuition

The solution involves a two-step approach. First, we perform the n - 1 operations as specified, inspecting each pair of adjacent elements and applying the doubling and zeroing rules. After all operations are complete, we're left with an array with some elements set to 0 that now should be moved to the end.

The intuition behind the first step is straightforward: loop through the array, compare each element with its neighbor, and if they are the same, apply the operation. We have to remember that these operations should be applied sequentially, meaning the result of one operation may affect subsequent operations. Therefore, careful in-place manipulation of the array is necessary.

For the second step, the intuition is to keep track of where the next non-zero element should be placed. Essentially, this involves a second pass through the array, where we move each non-zero element leftwards to "fill in" the non-zero portion of the array. This is why a separate counter (i in the provided solution) is maintained to keep track of the index at which the next non-zero element should be inserted. Non-zero elements are placed in the array in their original order until all non-zero elements have been accounted for. Finally, the rest of the array is filled with 0s.

This two-pass approach ensures that the operations are applied correctly and that the output array maintains the proper order of non-zero elements, concluding with the zeros shifted to the end.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The provided solution follows a straightforward two-pass approach which efficiently addresses the requirements with simple array manipulation techniques. The key steps in this approach are as follows:

Doubling and Zeroing in Place: The first pass goes through the array from the start to the second-to-last element. At each index i, the algorithm checks if nums[i] equals nums[i + 1]. If they are equal, it doubles nums[i] using the left shift operator (<<= 1 is equivalent to multiplying by 2) and sets nums[i + 1] to 0. Using the bitwise shift here is a more efficient way of doubling integers.
Shifting Non-zero Elements: In the second pass, the algorithm traverses the array only once more and maintains a separate index i which keeps track of the position where the next non-zero element should go. Hence, for each element x in the array, if x is non-zero, it is placed at nums[i] and the index i is incremented. This effectively compacts all non-zero elements towards the beginning of the array.
Filling Remaining with Zeros: Because the original array is modified in place during step 1, and the non-zero elements are moved forward in step 2, the remaining elements in the array (from the current index i to the end) are already implicitly 0. If there was any need to explicitly set them to 0, it could be done in a final pass; however, the code efficiency is improved by realizing this step is not necessary given the initial array manipulation.

This approach takes O(n) time due to the two sequential passes through the array, where n is the number of elements in nums. No additional data structures are needed, so the space complexity is O(1) as the solution uses only a fixed amount of extra space to store the counters and temporary values.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayMerge sort does not use divide and conquer

I don’t know

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following array:

1Input array: [2, 2, 3, 3, 3]

Here is how the solution approach would be applied to this array:

Doubling and Zeroing in Place:

We start at the first element and compare it with the next element.

nums[0] is 2, and nums[1] is also 2. They are equal, so we double nums[0] (2 becomes 4) and set nums[1] to 0. Now the array looks like this: [4, 0, 3, 3, 3].
We move to the next non-zero pair. nums[2] is 3, and nums[3] is also 3. Doubling nums[2] we get 6, and set nums[3] to 0: [4, 0, 6, 0, 3].
nums[4] is the last element and doesn't have a pair to compare with, so the array remains [4, 0, 6, 0, 3] after the first pass.

Shifting Non-zero Elements:

Now, we make a second pass through the array and move all non-zero elements to the front.

We set up a separate index i starting at 0 to track where to place non-zero elements.
Starting from the beginning of the array, when we find a non-zero element, we move it to the nums[i] position and increment i.
For the first non-zero element, 4 stays in its original position, and i is incremented to 1.
Skipping over the zero, we come to 6. 6 is placed at nums[i] (which is nums[1] now), and i becomes 2.
Next, the 3 is placed at nums[i] (now nums[2]), and i is incremented to 3.

So, the non-zero part of the array is now [4, 6, 3]. Since the array's length is 5 and we already have the remaining elements implicitly set to 0 due to the first pass, we get:

1Output array: [4, 6, 3, 0, 0]

We have now successfully completed all operations as defined by the problem statement, and the zeros are shifted to the end of the array while preserving the order of the non-zero elements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def apply_operations(self, nums: List[int]) -> List[int]:
5        # Get the length of the list 'nums'.
6        length = len(nums)
7
8        # Iterate over the list elements, except for the last element.
9        for i in range(length - 1):
10            # If the current element is the same as the next element,
11            # double its value and set the next element to 0.
12            if nums[i] == nums[i + 1]:
13                nums[i] *= 2
14                nums[i + 1] = 0
15      
16        # Create a new list 'result' with the same size filled with zeros.
17        result = [0] * length
18      
19        # Initialize a pointer for the index of 'result'.
20        result_index = 0
21      
22        # Iterate over 'nums' to populate non-zero elements in the 'result'.
23        for num in nums:
24            # If the element is non-zero, put it in the next position of 'result'.
25            if num:
26                result[result_index] = num
27                result_index += 1
28      
29        # Return the 'result' list containing the processed numbers.
30        return result
31

1class Solution {
2
3    // Method to apply operations on an array of integers
4    public int[] applyOperations(int[] nums) {
5        int length = nums.length; // Get the length of the array
6
7        // Loop through each element, except the last one
8        for (int i = 0; i < length - 1; ++i) {
9            // Check if the current element is equal to the next element
10            if (nums[i] == nums[i + 1]) {
11                // If so, double the current element
12                nums[i] <<= 1; // Same as nums[i] = nums[i] * 2
13                // And set the next element to zero
14                nums[i + 1] = 0;
15            }
16        }
17
18        int[] result = new int[length]; // Create a new array to store the results
19        int index = 0; // Initialize result array index
20
21        // Iterate through the original array
22        for (int num : nums) {
23            // Copy non-zero elements to the result array
24            if (num > 0) {
25                result[index++] = num; // Assign and then increment the index
26            }
27        }
28
29        return result; // Return the resulting array
30    }
31}
32

1class Solution {
2public:
3    vector<int> applyOperations(vector<int>& nums) {
4        // Get the size of the nums array
5        int size = nums.size();
6      
7        // Loop through each pair of adjacent numbers
8        for (int idx = 0; idx < size - 1; ++idx) {
9            // If adjacent numbers are equal, double the current number and set next number to zero
10            if (nums[idx] == nums[idx + 1]) {
11                nums[idx] <<= 1; // double the number (same as nums[idx] *= 2)
12                nums[idx + 1] = 0; // set the next number to zero
13            }
14        }
15        // Create a new vector to store the resulting numbers after applying operations
16        vector<int> result(size);
17        int resultIndex = 0; // Initiate a result index to populate result vector with non-zero values
18      
19        // Iterate over the modified nums array to filter out the zeros
20        for (int& num : nums) {
21            // If the current number is non-zero, add it to the result vector
22            if (num) {
23                result[resultIndex++] = num; // Add to result and increment the position
24            }
25        }
26      
27        // Return the result vector (which doesn't contain zeros between non-zero numbers)
28        return result;
29    }
30};
31

1function applyOperations(nums: number[]): number[] {
2    const length = nums.length; // The total number of elements in the array 'nums'
3  
4    // Double the current number and set the next one to 0 if they're equal
5    for (let index = 0; index < length - 1; ++index) {
6        if (nums[index] === nums[index + 1]) {
7            nums[index] *= 2; // Double the current number
8            nums[index + 1] = 0; // Set the next number to 0
9        }
10    }
11
12    // Initialize a new array 'result' with the same length as 'nums' and fill it with 0s
13    const result: number[] = Array(length).fill(0);
14  
15    // Pointer to the position in 'result' where the next non-zero element will be placed
16    let resultIndex = 0;
17  
18    // Move all non-zero elements to the 'result' array
19    for (const number of nums) {
20        if (number !== 0) {
21            result[resultIndex++] = number; // Assign non-zero element and move to the next index
22        }
23    }
24  
25    return result; // Return the transformed array
26}
27

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

Time Complexity

The given function applyOperations consists of two separate for-loops that are not nested.

The first for-loop iterates through the list nums, except for the last element, performing constant-time operations. The iteration occurs exactly n - 1 times, where n is the length of nums. Since no other operations are nested inside this loop, the time complexity for this portion is O(n-1) which simplifies to O(n).

The second for-loop iterates through each element in nums once. It fills in the non-zero elements to the list ans. The assignment and increment operations are constant time operations, and since this loop iterates n times, the time complexity for this loop is also O(n).

Combining both loops, which are sequential and not nested, the overall time complexity of the function is O(n) + O(n) which simplifies to O(n).

Space Complexity

Regarding space complexity, a new list ans of the same size as the input list nums is created, which denotes the extra space used by the algorithm. This implies a space complexity of O(n).

No additional data structures are used that grow with the input size, hence the total space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2460. Apply Operations to an Array

Problem Description

Intuition

Solution Approach

Example Walkthrough

Doubling and Zeroing in Place:

Shifting Non-zero Elements:

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity