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.
Simulate each day. For each element, if it is greater than its left and right neighbors, it decreases by 1, otherwise, it increases by 1. If the array no longer changes on a certain day, return that array.
The time complexity is O(n times m), and the space complexity is O(n). Where n is the length of the array, and m is the maximum value in the array.
| 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 |
LeetCode 1243: Array Transformation - Interview Prep Ep 14 • Fisher Coder • 1,169 views views
Watch 3 more video solutions →Practice Array Transformation with our built-in code editor and test cases.
Practice on FleetCode