2460. Apply Operations to an Array
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 i
th element of the array (considering 0-indexing), following these rules:
- Check if the
i
th element of the array (nums[i]
) is equal to the next element (nums[i + 1]
). - If they are equal, double the
i
th element (nums[i] = nums[i] * 2
) and set thei + 1
th element to0
. - If they are not equal, move on to the next operation without making changes to the current
i
th 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 0
s.
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.
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 ifnums[i]
equalsnums[i + 1]
. If they are equal, it doublesnums[i]
using the left shift operator (<<= 1
is equivalent to multiplying by 2) and setsnums[i + 1]
to0
. 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 elementx
in the array, ifx
is non-zero, it is placed atnums[i]
and the indexi
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 implicitly0
. If there was any need to explicitly set them to0
, 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following array:
Input 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, andnums[1]
is also 2. They are equal, so we doublenums[0]
(2 becomes 4) and setnums[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, andnums[3]
is also 3. Doublingnums[2]
we get 6, and setnums[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 incrementi
. - For the first non-zero element,
4
stays in its original position, andi
is incremented to 1. - Skipping over the zero, we come to
6
.6
is placed atnums[i]
(which isnums[1]
now), andi
becomes 2. - Next, the
3
is placed atnums[i]
(nownums[2]
), andi
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:
Output 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
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.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!