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
:
- If an element is smaller than both its left neighbor and its right neighbor, then this element is incremented.
- If an element is bigger than both its left neighbor and its right neighbor, then this element is decremented.
- The first and last elements never change.
After some days, the array does not change. Return that final array.
Examples
Example 1:
|
|
Example 2:
|
|
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
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n^2)
in the worst case (each element can change up to O(n) times) - 🧺 Space complexity:
O(n)