Solution: Array Transformation

Grokking the Engineering Manager Coding Interview

Ask Author

Back to course home

0% completed

Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Complexity Analysis

Time Complexity

Space Complexity

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

Python3

. . . .

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: $O(n * 100) = O(n)$ .

Space Complexity

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

Mark as Completed

Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Complexity Analysis

Time Complexity

Space Complexity