Array Transformation

easy array simulation

Problem

Given an initial array arr, transform it daily by the following rules. For every interior element (not the first or last): if it is strictly smaller than both neighbors, increment it by 1; if it is strictly larger than both neighbors, decrement it by 1. All comparisons in a single day use the values from the start of that day. Keep transforming until no value changes, then return the final array.

Inputarr = [6, 2, 3, 4]

Output[6, 3, 3, 4]

On day 1, index 1 (value 2) is a local min between 6 and 3, so it becomes 3. No other interior element changes, and day 2 produces no change, so the array is stable.

arr (comma-separated)

def transform_array(arr):
    changed = True
    while changed:
        changed = False
        prev = arr[:]
        for i in range(1, len(arr) - 1):
            if prev[i] < prev[i - 1] and prev[i] < prev[i + 1]:
                arr[i] += 1
                changed = True
            elif prev[i] > prev[i - 1] and prev[i] > prev[i + 1]:
                arr[i] -= 1
                changed = True
    return arr

function transformArray(arr) {
  let changed = true;
  while (changed) {
    changed = false;
    const prev = arr.slice();
    for (let i = 1; i < arr.length - 1; i++) {
      if (prev[i] < prev[i - 1] && prev[i] < prev[i + 1]) {
        arr[i]++;
        changed = true;
      } else if (prev[i] > prev[i - 1] && prev[i] > prev[i + 1]) {
        arr[i]--;
        changed = true;
      }
    }
  }
  return arr;
}

class Solution {
    public int[] transformArray(int[] arr) {
        boolean changed = true;
        while (changed) {
            changed = false;
            int[] prev = arr.clone();
            for (int i = 1; i < arr.length - 1; i++) {
                if (prev[i] < prev[i - 1] && prev[i] < prev[i + 1]) {
                    arr[i]++;
                    changed = true;
                } else if (prev[i] > prev[i - 1] && prev[i] > prev[i + 1]) {
                    arr[i]--;
                    changed = true;
                }
            }
        }
        return arr;
    }
}

vector<int> transformArray(vector<int>& arr) {
    bool changed = true;
    while (changed) {
        changed = false;
        vector<int> prev = arr;
        for (int i = 1; i < (int)arr.size() - 1; i++) {
            if (prev[i] < prev[i - 1] && prev[i] < prev[i + 1]) {
                arr[i]++;
                changed = true;
            } else if (prev[i] > prev[i - 1] && prev[i] > prev[i + 1]) {
                arr[i]--;
                changed = true;
            }
        }
    }
    return arr;
}

Explanation

This is a simulation: we just keep applying the daily rule until a full day passes with no changes. The one subtle requirement is that within a single day, every comparison must use the values from the start of that day, not values we just updated.

To honor that, at the top of each day we take a snapshot prev = arr[:]. We then decide every interior cell's new value by looking only at prev, while writing results into arr. This stops one cell's change from leaking into its neighbor's decision on the same day.

For each interior index i: if prev[i] is smaller than both neighbors (a local min) we add 1; if it is larger than both (a local max) we subtract 1; otherwise it stays. We flip a changed flag whenever anything moves, and the outer while loop repeats only while changed is true.

Example: arr = [6, 2, 3, 4]. On day 1, index 1 holds 2, which is below both 6 and 3, so it rises to 3. Nothing else qualifies. Day 2 produces no change, so the stable result is [6, 3, 3, 4].

Time: O(n · m) Space: O(n)