problemeasyalgorithmsleetcode-1243leetcode 1243leetcode1243

Array Transformation

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Given an initial array arr, every day you produce a new array using the array of the previous day.

On the i-th day, you do the following operations on the array of day i-1 to produce the array of day i:

  1. If an element is smaller than both its left neighbor and its right neighbor, then this element is incremented.
  2. If an element is bigger than both its left neighbor and its right neighbor, then this element is decremented.
  3. The first and last elements never change.

After some days, the array does not change. Return that final array.

Examples

Example 1:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]
Explanation:
On the first day, the array is changed from [6,2,3,4] to [6,3,3,4].
No more operations can be done to this array.

Example 2:

Input: arr = [1,6,3,4,3,5]
Output: [1,4,4,4,4,5]
Explanation:
On the first day, the array is changed from [1,6,3,4,3,5] to [1,5,4,3,4,5].
On the second day, the array is changed from [1,5,4,3,4,5] to [1,4,4,4,4,5].
No more operations can be done to this array.

Constraints:

  • 3 <= arr.length <= 100
  • 1 <= arr[i] <= 100

Solution

Method 1 – Simulation Until Stable

Intuition

Simulate the transformation day by day, updating the array according to the rules, until no changes occur.

Approach

Repeat the transformation process: for each element (except the first and last), increment or decrement as per the rules. Stop when the array no longer changes.

Code

Java
class Solution {
    public int[] transformArray(int[] arr) {
        int n = arr.length;
        boolean changed = true;
        int[] res = arr.clone();
        while (changed) {
            changed = false;
            int[] next = res.clone();
            for (int i = 1; i < n - 1; ++i) {
                if (res[i] < res[i-1] && res[i] < res[i+1]) {
                    next[i]++;
                    changed = true;
                } else if (res[i] > res[i-1] && res[i] > res[i+1]) {
                    next[i]--;
                    changed = true;
                }
            }
            res = next;
        }
        return res;
    }
}
Python
class Solution:
    def transformArray(self, arr: list[int]) -> list[int]:
        n = len(arr)
        res = arr[:]
        changed = True
        while changed:
            changed = False
            nxt = res[:]
            for i in range(1, n-1):
                if res[i] < res[i-1] and res[i] < res[i+1]:
                    nxt[i] += 1
                    changed = True
                elif res[i] > res[i-1] and res[i] > res[i+1]:
                    nxt[i] -= 1
                    changed = True
            res = nxt
        return res

Complexity

  • ⏰ Time complexity: O(n^2) in the worst case (each element can change up to O(n) times)
  • 🧺 Space complexity: O(n)

Comments