Modify the Array

JavaView on GFG

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?