LeetCode 2460. Apply Operations to an Array Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Simulation

We can directly simulate according to the problem description.

First, we traverse the array nums. For any two adjacent elements nums[i] and nums[i+1], if nums[i] = nums[i+1], then we double the value of nums[i] and change the value of nums[i+1] to 0.

Then, we create an answer array ans of length n, and put all non-zero elements of nums into ans in order.

Finally, we return the answer array ans.

The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer, the space complexity is O(1).

PythonJavaC++GoTypeScriptRust

class Solution: def applyOperations(self, nums: List[int]) -> List[int]: n = len(nums) for i in range(n - 1): if nums[i] == nums[i + 1]: nums[i] <<= 1 nums[i + 1] = 0 ans = [0] * n i = 0 for x in nums: if x: ans[i] = x i += 1 return ans(code-box)

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; } }(code-box)

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

func applyOperations(nums []int) []int { n := len(nums) for i := 0; i < n-1; i++ { if nums[i] == nums[i+1] { nums[i] <<= 1 nums[i+1] = 0 } } ans := make([]int, n) i := 0 for _, x := range nums { if x > 0 { ans[i] = x i++ } } return ans }(code-box)

function applyOperations(nums: number[]): number[] { const n = nums.length; for (let i = 0; i < n - 1; ++i) { if (nums[i] === nums[i + 1]) { nums[i] <<= 1; nums[i + 1] = 0; } } const ans: number[] = Array(n).fill(0); let i = 0; for (const x of nums) { if (x !== 0) { ans[i++] = x; } } return ans; }(code-box)

impl Solution { pub fn apply_operations(nums: Vec<i32>) -> Vec<i32> { let mut nums = nums; for i in 0..nums.len() - 1 { if nums[i] == nums[i + 1] { nums[i] <<= 1; nums[i + 1] = 0; } } let mut cur = 0; for i in 0..nums.len() { if nums[i] != 0 { nums.swap(i, cur); cur += 1; } } nums } }(code-box)