Modify the Array

Given an array arr. Return the modified array in such a way that if the current and next numbers are valid numbers and are equal then double the current number value and replace the next number with 0. After the modification, rearrange the array such that all 0’s are shifted to the end.

Note:

1. Assume ‘0’ as the invalid number and all others as a valid number.
2. The sequence of the valid numbers is present in the same order.

Example:

Input: arr[] = [2, 2, 0, 4, 0, 8] 
Output: [4, 4, 8, 0, 0, 0] 
Explanation: At index 0 and 1 both the elements are the same. So, we will change the element at index 0 to 4 and the element at index 1 is 0 then we will shift all the zeros to the end of the array. So, the array will become [4, 4, 8, 0, 0, 0].

Input: arr[] = [0, 2, 2, 2, 0, 6, 6, 0, 0, 8] 
Output: [4, 2, 12, 8, 0, 0, 0, 0, 0, 0]
Explanation: At index 5 and 6 both the elements are the same. So, we will change the element at index 5 to 12 and the element at index 6 is 0. We will change the element at index 1 to 4 and the element at index 2 is 0. Then we shift all the zeros to the end of the array. So, array will become [4, 2, 12, 8, 0, 0, 0, 0, 0, 0].

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1 ≤ arr.size() ≤ 10⁵
1 ≤ arr[i] ≤ 10⁶

Approach 01:

class Solution {
public:
    vector<int> modifyAndRearrangeArray(vector<int>& arr) {
        int arraySize = arr.size();
        if (arraySize == 1) 
            return arr;

        // Modify the array by doubling adjacent equal elements
        for (int index = 1; index < arraySize; index++) {
            if (arr[index - 1] == arr[index] && arr[index] != 0) {
                arr[index - 1] = 2 * arr[index];
                arr[index] = 0;
            }
        }

        // Rearrange the array by moving all non-zero elements to the front
        int nonZeroIndex = 0, currentIndex = 0;
        while (currentIndex < arraySize) {
            if (arr[currentIndex] != 0) {
                swap(arr[nonZeroIndex], arr[currentIndex]);
                nonZeroIndex++;
            }
            currentIndex++;
        }

        return arr;
    }
};

class Solution:
    def modifyAndRearrangeArr (self, arr) : 
        arraySize = len(arr)
        if arraySize == 1:
            return arr

        # Modify the array by doubling adjacent equal elements
        for index in range(1, arraySize):
            if arr[index - 1] == arr[index] and arr[index] != 0:
                arr[index - 1] = 2 * arr[index]
                arr[index] = 0

        # Rearrange the array by moving all non-zero elements to the front
        nonZeroIndex = 0
        currentIndex = 0
        while currentIndex < arraySize:
            if arr[currentIndex] != 0:
                arr[nonZeroIndex], arr[currentIndex] = arr[currentIndex], arr[nonZeroIndex]
                nonZeroIndex += 1
            currentIndex += 1

        return arr

Time Complexity

• First Loop (Modifying the array):

  The first loop runs through the array once, comparing adjacent elements and modifying them if necessary. This loop runs \(O(n)\) times, where n is the size of the array.

• Second Loop (Rearranging the array):

  The second loop also goes through the array once to move all non-zero elements to the front. This operation is done in \(O(n)\) time.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the number of elements in the array, as both loops perform linear passes.

Space Complexity

• In-Place Modification:

  The function modifies the input array in-place, meaning no additional space is used for a new array. The space required for this operation is constant, \(O(1)\), excluding the input array.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\) (constant extra space), as no extra storage proportional to the input size is needed.