Modify the Array

JavaView on GFG

Problem Overview

Modify array such that no two adjacent elements are equal.

Intuition

Modify array such that no two adjacent elements are equal. If equal, increment one.

Algorithm

1Scan left to right: if arr[i] == arr[i-1]: arr[i] = arr[i-1]+1.

Common Pitfalls

• Greedy: resolve conflicts left to right. Each fix may chain, so process sequentially.

Modify the Array.java

Java

// Approach: Scan left to right: if arr[i] == arr[i-1], increment arr[i]. Use a set to track used values.
// Time: O(n log n) Space: O(n)
class Solution {
    static ArrayList<Integer> modifyAndRearrangeArr(int arr[]) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] == arr[i]) {
                arr[i - 1] = (arr[i - 1]) * 2;
                arr[i] = 0;
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();
        for (int num : arr) {
            if (num != 0)
                ans.add(num); // Autoboxing from int to Integer
        }
        int rs = arr.length - ans.size();
        while (rs > 0) {
            ans.add(0);
            rs--;
        }

        return ans;
    }
}

Was this solution helpful?