Problem of The Day: Apply Operations to an Array

Problem Statement

Intuition

The problem requires modifying an array based on adjacent equal elements and then shifting non-zero elements to the left. The first step is straightforward: if two consecutive elements are equal, we double the first one and set the second to zero. After that, we need to rearrange the array so that all non-zero elements come first while maintaining their relative order.

Approach

1. Modify the Array:

   • Iterate through the array and check for adjacent elements.
   • If two consecutive elements are the same, double the first one and set the second to zero.

2. Rearrange the Array:

   • Use two pointers (start and end) to move all non-zero elements to the left while maintaining their order.
   • Swap non-zero elements with zeros to shift them to the front.

Complexity

• Time complexity:

  • The first loop iterates through the array once, performing a constant-time operation for each element: \(O(n)\).
  • The second loop also iterates through the array once, making swaps in constant time: \(O(n)\).
  • Overall complexity: \(O(n)\).

• Space complexity:

  • The algorithm modifies the input array in place, using only a few extra variables: \(O(1)\).

Code

from typing import List

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        N = len(nums)
        for i, num in enumerate(nums):
            if i + 1 < N and nums[i] == nums[i + 1]:
                nums[i] *= 2
                nums[i + 1] = 0

        start, end = 0, 0
        for end in range(N):
            if nums[end] != 0:
                nums[end], nums[start] = nums[start], nums[end]
                start += 1
        return nums

Editorial

Approach 1: Brute Force Simulation

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n = len(nums)
        modified_nums = []

        # Step 1: Apply operations on the array
        for index in range(0, n - 1):
            if (nums[index] == nums[index + 1]) and (nums[index] != 0):
                nums[index] *= 2
                nums[index + 1] = 0

        # Step 2: Move non-zero elements to the front
        for num in nums:
            if num != 0:
                modified_nums.append(num)

        # Step 3: Append zeros to maintain the original size
        while len(modified_nums) < n:
            modified_nums.append(0)

        return modified_numsx

Approach 2: Memory Optimization

class Solution:
    def applyOperations(self, nums):
        n = len(nums)

        # Step 1: Apply operations on the array
        for index in range(n - 1):
            if nums[index] == nums[index + 1] and nums[index] != 0:
                nums[index] *= 2
                nums[index + 1] = 0

        # Step 2: Shift non-zero elements to the beginning
        non_zero_index = 0
        for iterate_index in range(n):
            if nums[iterate_index] != 0:
                nums[non_zero_index] = nums[iterate_index]
                non_zero_index += 1

        # Step 3: Fill the remaining positions with zeros
        while non_zero_index < n:
            nums[non_zero_index] = 0
            non_zero_index += 1

        return nums