546. Converting to Non-Decreasing Array with One Change

Given an array of numbers, you need to find out whether an array can be converted to a non-decreasing array where you are allowed to modify the maximum one element in the array.

Non-decreasing array: Array is called non-decreasing array when you traverse array from left to right, each element on the left is less than equal to the element on the right. So for any element at index i, input[i-1]<=input[i]<=input[i+1].

Example:

Example 1:
Input: [4, 5, 1, 7]
Output: true
Solution: Change 1 to 6, 5, or 7.

Example 2:
Input: [10, 5, 2]
Output: false

Example 3:
Input: [1, 2, 1, 5]
Output: true
Solution: Change 2 to 1.

Example 4:
Input: [1, 1, 1, 1]
Output: true
No change required.

Solution:

To convert an array into a non-decreasing array, consider both increasing and decreasing possibilities. Only one element can be modified. Begin by iterating through the array from right to left and count the number of elements that need to be decreased if the left element is greater than the right element. Then, iterate through the array from left to right and determine the number of elements that need to be increased if the right element is less than the left element.

Important: Modify elements just enough to meet the non-decreasing condition, making them equal to their neighboring elements. For example, in the array [1, 2, 1, 5], decrease the element 2 to 1 to satisfy the non-decreasing condition.

By following this approach, you can effectively convert the array into a non-decreasing array.

Time Complexity: O(N)

Output:

true
false
true
true

Reference: leetcode

Related Problems:

- Efficiently Rearrange Positive and Negative Numbers in Array on Each Side Hard
- Sliding Window Algorithm (Track the maximum of each subarray of size k) Hard
- Majority Element – Part 1 Beginner
- Find local minimum or local maximum in O(1) Medium