Skip to content

1243. Array Transformation

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<int> transformArray(vector<int>& arr) {
    if (arr.size() < 3)
      return arr;

    vector<int> ans(arr.size());

    while (ans != arr) {
      ans = arr;
      for (int i = 1; i < arr.size() - 1; ++i) {
        if (ans[i - 1] > ans[i] && ans[i] < ans[i + 1])
          ++arr[i];
        else if (ans[i - 1] < ans[i] && ans[i] > ans[i + 1])
          --arr[i];
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public List<Integer> transformArray(int[] arr) {
    if (arr.length < 3)
      return Arrays.stream(arr).boxed().toList();

    int[] ans = new int[0];

    while (!Arrays.equals(ans, arr)) {
      ans = arr.clone();
      for (int i = 1; i < arr.length - 1; ++i)
        if (ans[i - 1] > ans[i] && ans[i] < ans[i + 1])
          ++arr[i];
        else if (ans[i - 1] < ans[i] && ans[i] > ans[i + 1])
          --arr[i];
    }

    return Arrays.stream(ans).boxed().toList();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def transformArray(self, arr: list[int]) -> list[int]:
    if len(arr) < 3:
      return arr

    ans = []

    while ans != arr:
      ans = arr[:]
      for i in range(1, len(arr) - 1):
        if ans[i - 1] > ans[i] < ans[i + 1]:
          arr[i] += 1
        elif ans[i - 1] < ans[i] > ans[i + 1]:
          arr[i] -= 1

    return ans