Home › DSA › Advanced Patterns

easy Array Transformation

Problem Statement

Given an array arr, you transform it daily based on the following rules:

If an element is smaller than both its left and right neighbors, increment it by 1.
If an element is larger than both its left and right neighbors, decrement it by 1.
The first and last elements of the array do not change.

Continue transforming the array until no more changes occur. Return the final state of the array.

Examples

Example 1

Input: arr = [5, 2, 8, 1, 6]
Expected Output: [5, 5, 5, 5, 6]
Justification:
- On the first day, 2 is incremented to 3, 8 is decremented to 7, and 1 is incremented to 2. The first and last elements remain unchanged. The final state of the array after the first day is [5, 3, 7, 2, 6].
- After second day: [5, 4, 6, 3, 6].
- After third day: [5, 5, 5, 4, 6].
- After forth day: [5, 5, 5, 5, 6].

Example 2

Input: arr = [3, 7, 1, 5, 2]
Expected Output: [3,3,3,3,2]
Justification:
- After first day: [3, 6, 2, 4, 2].
- After second day: [3, 5, 3, 3, 2].
- After third day: [3, 4, 3, 3, 2].
- After forth day: [3, 3, 3, 3, 2].

Example 3

Input: arr = [9, 9, 9, 9, 9]
Expected Output: [9, 9, 9, 9, 9]
Justification: All elements are the same. So, arr remains unchanged.

Constraints:

3 <= arr.length <= 100
1 <= arr[i] <= 100

Try it yourself

Try solving this question here:

✅ Solution Array Transformation

Problem Statement

Given an array arr, you transform it daily based on the following rules:

If an element is smaller than both its left and right neighbors, increment it by 1.
If an element is larger than both its left and right neighbors, decrement it by 1.
The first and last elements of the array do not change.

Continue transforming the array until no more changes occur. Return the final state of the array.

Examples

Example 1

Input: arr = [5, 2, 8, 1, 6]
Expected Output: [5, 5, 5, 5, 6]
Justification:
- On the first day, 2 is incremented to 3, 8 is decremented to 7, and 1 is incremented to 2. The first and last elements remain unchanged. The final state of the array after the first day is [5, 3, 7, 2, 6].
- After second day: [5, 4, 6, 3, 6].
- After third day: [5, 5, 5, 4, 6].
- After forth day: [5, 5, 5, 5, 6].

Example 2

Input: arr = [3, 7, 1, 5, 2]
Expected Output: [3,3,3,3,2]
Justification:
- After first day: [3, 6, 2, 4, 2].
- After second day: [3, 5, 3, 3, 2].
- After third day: [3, 4, 3, 3, 2].
- After forth day: [3, 3, 3, 3, 2].

Example 3

Input: arr = [9, 9, 9, 9, 9]
Expected Output: [9, 9, 9, 9, 9]
Justification: All elements are the same. So, arr remains unchanged.

Constraints:

3 <= arr.length <= 100
1 <= arr[i] <= 100

Solution

To solve this problem, we simulate the transformation process of the array until it stabilizes. We iterate through the array, adjusting elements based on their neighbors. If an element is smaller than both its neighbors, we increment it. If it is larger, we decrement it. This process continues until no more changes occur, meaning the array has stabilized. This approach is effective as it directly follows the problem constraints and guarantees that the array reaches a stable state.

Step-by-Step Algorithm

Initialize Variables:
- changed = true: This flag will be used to determine if any changes were made during an iteration.
Loop Until No Changes Occur:
- While changed is true:
  - Set changed to false at the start of each iteration.
  - Initialize prev, curr, and next to the first three elements of the array for comparison. Here, prev will store the left neighbor of the curr elements, and next will store the right neighbor of the curr element.
Iterate Through the Array:
- For each element from the second to the second last element:
  - If the current element curr is less than both its neighbors (prev and next), increment it.
    - Set changed to true to indicate a change was made.
  - If the current element curr is greater than both its neighbors (prev and next), decrement it.
    - Set changed to true to indicate a change was made.
Update Elements for Next Iteration:
- Move to the next set of elements:
  - Update prev to the value of curr.
  - Update curr to the value of next.
  - Update next to the value of the element two positions ahead (arr[i + 2]), if within bounds.
- These updates ensure that the comparisons in the next iteration use the original values from the array, maintaining the correct sequence of comparisons.
Return the Transformed Array:
- After the loop exits (when no changes occur), return the transformed array arr.

Algorithm Walkthrough

Let's use the input: arr = [5, 2, 8, 1, 6].

Initialize Variables:
- changed = true
First Iteration of While Loop:
- changed = false
- Initialize prev = 5, curr = 2, next = 8
- For Loop (i = 1):
  - 2 < 5 and 2 < 8 -> increment arr[1] to 3
  - arr = [5, 3, 8, 1, 6]
  - changed = true
  - (i = 1) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 2, curr = 8, next = 1
- For Loop (i = 2):
  - 8 > 2 and 8 > 1 -> decrement arr[2] to 7
  - changed = true
  - arr = [5, 3, 7, 1, 6]
  - (i = 2) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 8, curr = 1, next = 6
- For Loop (i = 3):
  - 1 < 8 and 1 < 6 -> increment arr[3] to 2
  - arr = [5, 3, 7, 2, 6]
  - changed = true
  - (i = 3) !< (arr.length - 2 = 3). No further iterations.
Second Iteration of While Loop:
- changed = false
- Initialize prev = 5, curr = 3, next = 7
- For Loop (i = 1):
  - 3 < 5 and 3 < 7 -> increment arr[1] to 4
  - arr = [5, 4, 7, 2, 6]
  - changed = true
  - (i = 1) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 3, curr = 7, next = 2
- For Loop (i = 2):
  - 7 > 3 and 7 > 2 -> decrement arr[2] to 6
  - arr = [5, 4, 6, 2, 6]
  - changed = true
  - (i = 2) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 7, curr = 2, next = 6
- For Loop (i = 3):
  - 2 < 7 and 2 < 6 -> increment arr[3] to 3
  - arr = [5, 4, 6, 3, 6]
  - changed = true
  - (i = 3) !< (arr.length - 2 = 3). No further iterations.
Third Iteration of While Loop:
- changed = false
- Initialize prev = 5, curr = 4, next = 6
- For Loop (i = 1):
  - 4 < 5 and 4 < 6 -> increment arr[1] to 5
  - arr = [5, 5, 6, 3, 6]
  - changed = true
  - (i = 1) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 4, curr = 6, next = 3
- For Loop (i = 2):
  - 6 > 4 and 6 > 3 -> increment arr[1] to 5
  - arr = [5, 5, 5, 3, 6]
  - changed = true
  - (i = 2) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 6, curr = 3, next = 6
- For Loop (i = 3):
  - 3 < 6 and 3 < 6 -> increment arr[3] to 4
  - arr = [5, 5, 5, 4, 6]
  - changed = true
  - (i = 3) !< (arr.length - 2 = 3). No further iterations.
Fourth Iteration of While Loop:
- changed = false
- Initialize prev = 5, curr = 5, next = 5
- For Loop (i = 1):
  - No change (5 is not less than both neighbors or greater than both)
  - (i = 1) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 5, curr = 5, next = 4
- For Loop (i = 2):
  - No change (5 is not less than both neighbors or greater than both)
  - (i = 2) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 5, curr = 4, next = 6
- For Loop (i = 3):
  - 4 < 5 and 4 < 6 -> increment arr[3] to 5
  - arr = [5, 5, 5, 5, 6]
  - changed = true
  - (i = 3) !< (arr.length - 2 = 3). No further iterations.
Fifth Iteration of While Loop:
- changed = false
- Initialize prev = 5, curr = 5, next = 5
- For Loop (i = 1):
  - No change (5 is not less than both neighbors or greater than both)
  - (i = 1) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 5, curr = 5, next = 5
- For Loop (i = 2):
  - No change (5 is not less than both neighbors or greater than both)
  - (i = 2) < (arr.length - 2 = 5 - 2 = 3). So, move to next elements.
    - Update prev = 5, curr = 5, next = 6
- For Loop (i = 3):
  - No change (5 is not less than both neighbors or greater than both)
  - (i = 3) !< (arr.length - 2 = 3). No further iterations.
- Array After Fifth Iteration:
  - arr = [5, 5, 5, 5, 6]
Termination:
- The loop exits as changed remains false, indicating no further changes.
The final state of the array is [5, 5, 5, 5, 6].

java

import java.util.Arrays;

class Solution {

  public int[] transformArray(int[] arr) {
    boolean changed = true;

    // Continue transforming until no changes occur
    while (changed) {
      changed = false;
      // Store the first three elements for comparison
      int prev = arr[0],
        curr = arr[1],
        next = arr[2];

      // Loop through the array starting from the second element to the second last element
      for (int i = 1; i < arr.length - 1; i++) {
        // If current element is less than both its neighbors, increment it
        if (curr < prev && curr < next) {
          arr[i]++;
          changed = true;
        }
        // If current element is greater than both its neighbors, decrement it
        else if (curr > prev && curr > next) {
          arr[i]--;
          changed = true;
        }
        // Move to the next set of elements
        if (i == arr.length - 2) break;
        prev = curr;
        curr = next;
        next = arr[i + 2];
      }
    }
    return arr;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Test the method with different inputs
    int[] arr1 = { 5, 2, 8, 1, 6 };
    int[] arr2 = { 3, 7, 1, 5, 2 };
    int[] arr3 = { 9, 9, 9, 9, 9 };

    System.out.println(Arrays.toString(sol.transformArray(arr1))); // [5, 5, 5, 5, 6]
    System.out.println(Arrays.toString(sol.transformArray(arr2))); // [3, 3, 3, 3, 2]
    System.out.println(Arrays.toString(sol.transformArray(arr3))); // [9, 9, 9, 9, 9]
  }
}

Complexity Analysis

Time Complexity

The outer loop can run up to 100 times, given the constraint 3 <= arr[i] <= 100.
The inner loop runs n-2 times per iteration.
So, the time complexity is: .

Space Complexity

The space complexity of this algorithm is , excluding the input array itself. Since the array is being transformed in-place, no extra space proportional to the input size is needed.

🤖 Don't fully get this? Learn it with Claude

Stuck on Array Transformation? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Array Transformation** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Array Transformation** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Array Transformation**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Array Transformation**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Maximum Population Year Water Bottles →