Leetcode

Non-decreasing Array

  • Time:O(n)
  • Space:O(1)

C++

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 previous value
        else
          nums[i] = nums[i - 1];  // increase current value
        modified = true;
      }

    return true;
  }
};

JAVA

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];
  }
}

Python

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]