Domain 1EasyCORE

Array Transformation

The problem requires transforming an array based on specific rules until no further changes can be made. The input is an array of integers where the first and last elements remain unchanged. For each element in between, if it is smaller than both its neighbors, it is incremented; if it is larger than both its neighbors, it is decremented. The process continues until the array stabilizes (no more changes occur).

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1243. Array Transformation

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 50.0%


Problem Breakdown

The problem requires transforming an array based on specific rules until no further changes can be made. The input is an array of integers where the first and last elements remain unchanged. For each element in between, if it is smaller than both its neighbors, it is incremented; if it is larger than both its neighbors, it is decremented. The process continues until the array stabilizes (no more changes occur).

Inputs:

  • An array arr of integers with a length between 3 and 100.
  • Each element in the array is between 1 and 100.

Outputs:

  • The final stable array after transformations.

Implicit Constraints/Edge Cases:

  • The first and last elements never change.
  • Arrays with all identical elements will remain unchanged.
  • Arrays with a single peak or trough may stabilize quickly.

Intuition

A brute-force approach would involve repeatedly iterating through the array, applying the transformation rules, and checking if any changes occurred. This could be inefficient due to repeated scans of the array. A better approach is to recognize that each element’s value can only change by at most 1 per day, leading to a maximum of n days of transformations (where n is the length of the array). Thus, we can limit our iterations to this number.

Approach

  1. Initialize Variables:

    • Create a copy of the input array to track changes.
    • Use a flag to indicate if any changes were made during an iteration.
  2. Iterate Until No Changes:

    • For each element in the array (excluding the first and last), check its neighbors.
    • If the current element is smaller than both neighbors, increment it.
    • If the current element is larger than both neighbors, decrement it.
    • Update the flag if any changes are made.
  3. Return the Result:

    • Once no more changes occur, return the transformed array.

Complexity Analysis

  • Time Complexity: O(n^2) in the worst case, where n is the length of the array. This is because we may need to iterate up to n times, and each iteration involves scanning the entire array.
  • Space Complexity: O(n) due to the storage of a copy of the input array.

Solution

def transformArray(arr):
    n = len(arr)
    while True:
        changed = False
        new_arr = arr[:]
        for i in range(1, n - 1):
            if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
                new_arr[i] += 1
                changed = True
            elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
                new_arr[i] -= 1
                changed = True
        if not changed:
            return new_arr
        arr = new_arr

# Example usage:
print(transformArray([6, 2, 3, 4]))  # Output: [6, 3, 3, 4]
print(transformArray([1, 6, 3, 4, 3, 5]))  # Output: [1, 4, 4, 4, 4, 5]

Edge Cases Handled

  • All Identical Elements: The array remains unchanged.
  • Single Peak or Trough: The transformation stabilizes quickly.
  • Mixed Values: The algorithm correctly applies the transformation rules until stability is reached.