Skip to content

665. Non-decreasing Array 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  bool checkPossibility(vector<int>& nums) {
    bool modified = false;

    for (int i = 1; i < nums.size(); ++i)
      if (nums[i] < nums[i - 1]) {
        if (modified)
          return false;
        if (i == 1 || nums[i] >= nums[i - 2])
          nums[i - 1] = nums[i];  // Decrease the previous value.
        else
          nums[i] = nums[i - 1];  // Increase the current value.
        modified = true;
      }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean checkPossibility(int[] nums) {
    int j = -1;

    for (int i = 0; i + 1 < nums.length; ++i)
      if (nums[i] > nums[i + 1]) {
        if (j != -1)
          return false;
        j = i;
      }

    return j == -1 || j == 0 || j == nums.length - 2 || //
        nums[j - 1] <= nums[j + 1] ||                   //
        nums[j] <= nums[j + 2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def checkPossibility(self, nums: list[int]) -> bool:
    j = None

    for i in range(len(nums) - 1):
      if nums[i] > nums[i + 1]:
        if j is not None:
          return False
        j = i

    return (j is None or j == 0 or j == len(nums) - 2 or
            nums[j - 1] <= nums[j + 1] or nums[j] <= nums[j + 2])