Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1243.html

1243. Array Transformation

Level

Easy

Description

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:

1. If an element is smaller than both its left neighbor and its right neighbor, then this element is incremented.
2. If an element is bigger than both its left neighbor and its right neighbor, then this element is decremented.
3. The first and last elements never change.

After some days, the array does not change. Return that final array.

Example 1:

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.

Example 2:

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, the array 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:

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

Solution

Do the operations on the array directly. On each day, calculate whether the numbers at each index in the array should be incremented or decremented or remain unchanged, and do the modification to the array accordingly. If on one day the array is unchanged, then return the final array, which needs to be converted to a list.

• Java
• C++
• Python
• Go

• class Solution {
      public List<Integer> transformArray(int[] arr) {
          int length = arr.length;
          boolean flag = true;
          while (flag) {
              flag = false;
              int[] change = new int[length];
              for (int i = 1; i < length - 1; i++) {
                  if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                      change[i] = 1;
                      flag = true;
                  } else if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                      change[i] = -1;
                      flag = true;
                  }
              }
              if (flag) {
                  for (int i = 1; i < length - 1; i++)
                      arr[i] += change[i];
              }
          }
          List<Integer> finalList = new ArrayList<Integer>();
          for (int i = 0; i < length; i++)
              finalList.add(arr[i]);
          return finalList;
      }
  }
  

• // OJ: https://leetcode.com/problems/array-transformation/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      vector<int> transformArray(vector<int>& A) {
          int N = A.size();
          while (true) {
              int prev = A[0];
              bool change = false;
              for (int i = 1; i < N - 1; ++i) {
                  int cur = A[i];
                  if (prev < A[i] && A[i + 1] < A[i]) A[i]--, change = true;
                  else if (prev > A[i] && A[i + 1] > A[i]) A[i]++, change = true;
                  prev = cur;
              }
              if (!change) return A;
          }
      }
  };
  

• class Solution:
      def transformArray(self, arr: List[int]) -> List[int]:
          f = True
          while f:
              f = False
              t = arr[:]
              for i in range(1, len(t) - 1):
                  if t[i] > t[i - 1] and t[i] > t[i + 1]:
                      arr[i] -= 1
                      f = True
                  if t[i] < t[i - 1] and t[i] < t[i + 1]:
                      arr[i] += 1
                      f = True
          return arr
  
  
  

• func transformArray(arr []int) []int {
  	f := true
  	for f {
  		f = false
  		t := make([]int, len(arr))
  		copy(t, arr)
  		for i := 1; i < len(arr)-1; i++ {
  			if t[i] > t[i-1] && t[i] > t[i+1] {
  				arr[i]--
  				f = true
  			}
  			if t[i] < t[i-1] && t[i] < t[i+1] {
  				arr[i]++
  				f = true
  			}
  		}
  	}
  	return arr
  }
  

All Problems

All Solutions