Array Transformation Python Solution

LeetCode 1243, Easy. Topics: Array, Simulation. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 26 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1243   # by problem number
lcpy gen -s array_transformation   # by problem name

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

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.

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, it 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

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n * m) where n = len(arr), m = max value range span
    # Space: O(n)
    def transform_array(self, arr: list[int]) -> list[int]:
        result = arr[:]
        while True:
            prev = result[:]
            changed = False
            for i in range(1, len(prev) - 1):
                if prev[i] > prev[i - 1] and prev[i] > prev[i + 1]:
                    result[i] -= 1
                    changed = True
                elif prev[i] < prev[i - 1] and prev[i] < prev[i + 1]:
                    result[i] += 1
                    changed = True
            if not changed:
                return result

Complexity

Time	Space
O(n * m) where n = len(arr), m = max value range span	O(n)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Array Transformation Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags