Watch 4 video solutions for Array Transformation, a easy level problem involving Array, Simulation. This walkthrough by Fisher Coder has 1,169 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
After some days, the array does not change. Return that final array.
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 <= 1001 <= arr[i] <= 100Problem Overview: You repeatedly transform an integer array based on its neighbors. For each index i (excluding the first and last), increase arr[i] by 1 if it is strictly smaller than both neighbors, or decrease it by 1 if it is strictly larger than both neighbors. All updates happen simultaneously in each round. The process stops when a full pass makes no changes.
Approach 1: Direct Simulation (O(n * k) time, O(n) space)
This problem maps naturally to simulation. Iterate through the array day by day and compute the next state using the rules for local minima and local maxima. Because all updates must happen simultaneously, you cannot modify the array in place while scanning. Instead, create a copy of the array for the next state, apply updates based on the previous state, then replace the original array.
During each iteration, scan indices 1 to n-2. If arr[i] < arr[i-1] and arr[i] < arr[i+1], increment it. If arr[i] > arr[i-1] and arr[i] > arr[i+1], decrement it. Otherwise leave it unchanged. Track whether any value changed in the current round. If an entire pass finishes with no updates, the array has stabilized and the process stops.
The algorithm works because each step only depends on immediate neighbors, making it a straightforward pass over the array. If the array length is n and the transformation stabilizes after k rounds, the runtime is O(n * k). In practice, k is small due to the limited value range and the fact that values move toward equilibrium.
A small implementation detail improves clarity: keep a boolean flag like changed. After building the next array state, compare or track updates during the pass. If no position changed, exit the loop early. This avoids unnecessary extra iterations once the configuration becomes stable.
Recommended for interviews: The expected solution is the direct simulation approach. Interviewers want to see that you correctly handle the “simultaneous update” requirement using a copied array and that you detect when the process stabilizes. A brute-force in-place attempt often produces incorrect results because earlier updates influence later comparisons in the same round. The clean simulation demonstrates careful reasoning about state transitions and edge handling.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Simulation (copy each round) | O(n * k) | O(n) | General case where updates must happen simultaneously |
| Simulation with Change Tracking | O(n * k) | O(n) | Preferred implementation that stops early once the array stabilizes |