Skip to main content
Talentd

Array Transformation - Solution & Explanation

EasyPremiumFree on FleetCodeArraySimulation6 min readAsked at: Virtu
Practice this problem

Problem Statement

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.

 

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

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Simulation (copy each round)O(n * k)O(n)General case where updates must happen simultaneously
Simulation with Change TrackingO(n * k)O(n)Preferred implementation that stops early once the array stabilizes

Video Solution

LeetCode 1243: Array Transformation - Interview Prep Ep 14 • Fisher Coder • 1,191 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Array Transformation easy or hard?
Array Transformation is classified as an Easy problem. The logic is straightforward once you recognize that the task is a simulation problem and that updates must be applied simultaneously using a separate array.
Array Transformation Python/Java solution
Implement a loop that repeatedly scans indices 1 through n-2 and writes updates into a new array. After each pass, replace the original array with the updated one and continue until no values change. The same logic works in Python, Java, C++, and Go.
How to solve Array Transformation in O(n)?
The entire process cannot be guaranteed in strict O(n) time because multiple transformation rounds may occur. The optimal strategy is O(n * k) simulation, where each round scans the array once. Early termination when no changes occur keeps the number of rounds small in practice.
What is the best approach for Array Transformation?
The best approach is simulation. Iterate through the array, compute a new array for the next state, and update values that are local minima or maxima. Because all updates must occur simultaneously, using a copied array is required. The process repeats until a full pass produces no changes.
Is Array Transformation asked at Google/Amazon/Meta?
Array Transformation represents a common interview pattern involving simulation and state transitions. Variations of array stabilization and iterative updates appear in interviews at large tech companies. The problem tests careful handling of simultaneous updates and array traversal logic.
What data structure is used in Array Transformation?
The solution primarily uses a standard array along with an auxiliary copy of the array for the next state. The copy ensures that all updates are applied simultaneously without affecting comparisons during the same iteration.
What is the time complexity of Array Transformation?
The time complexity is O(n * k), where n is the array length and k is the number of transformation rounds before the array stabilizes. Each round scans the array once. Space complexity is O(n) because a copy of the array is used to apply simultaneous updates.

Ready to solve this problem?

Practice Array Transformation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays