Welcome to Subscribe On Youtube

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

665. Non-decreasing Array (Easy)

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

 

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

 

Constraints:

• 1 <= n <= 10 ^ 4
• - 10 ^ 5 <= nums[i] <= 10 ^ 5

Related Topics:
Array

Solution 1.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public boolean checkPossibility(int[] nums) {
          int length = nums.length;
          boolean flag = false;
          for (int i = 1; i < length; i++) {
              int prevNum = nums[i - 1], curNum = nums[i];
              if (prevNum > curNum) {
                  if (flag)
                      return false;
                  else {
                      if (i > 1 && i < length - 1) {
                          int prev2Num = nums[i - 2], nextNum = nums[i + 1];
                          if (curNum < prev2Num && nextNum < prevNum)
                              return false;
                      }
                      flag = true;
                  }
              }
          }
          return true;
      }
  }
  
  ############
  
  class Solution {
      public boolean checkPossibility(int[] nums) {
          for (int i = 0; i < nums.length - 1; ++i) {
              int a = nums[i], b = nums[i + 1];
              if (a > b) {
                  nums[i] = b;
                  if (isSorted(nums)) {
                      return true;
                  }
                  nums[i] = a;
                  nums[i + 1] = a;
                  return isSorted(nums);
              }
          }
          return true;
      }
      
      private boolean isSorted(int[] nums) {
          for (int i = 0; i < nums.length - 1; ++i) {
              if (nums[i] > nums[i + 1]) {
                  return false;
              }
          }
          return true;
      }
  }
  

• // OJ: https://leetcode.com/problems/non-decreasing-array/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      bool checkPossibility(vector<int>& A) {
          int N = A.size(), R = N - 2;
          for (; R >= 0 && A[R] <= A[R + 1]; --R);
          for (int i = 0; i < N; ++i) {
              if ((i == 0 || i == N - 1 || A[i + 1] >= A[i - 1]) && i >= R) return true;
              if (i - 1 >= 0 && A[i] < A[i - 1]) break;
          }
          return false;
      }
  };
  

• class Solution:
      def checkPossibility(self, nums):
          """
          :type nums: List[int]
          :rtype: bool
          """
          if len(nums) < 2:
              return True
          count = 0
          for i in range(1, len(nums)):
              if nums[i] < nums[i - 1]:
                  if count == 1:
                      return False
                  if not (
                      i + 1 == len(nums)
                      or nums[i + 1] >= nums[i - 1]
                      or i - 2 < 0
                      or nums[i - 2] < nums[i]
                  ):
                      return False
                  else:
                      count = 1
          return True
  
  ############
  
  class Solution(object):
    def checkPossibility(self, nums):
      """
      :type nums: List[int]
      :rtype: bool
      """
      flag = False
      pre = float("-inf")
      for i in range(len(nums) - 1):
        if nums[i] < pre:
          if nums[i + 1] >= nums[i - 1]:
            nums[i] = nums[i + 1]
          else:
            nums[i - 1] = nums[i]
          flag = True
          break
        pre = nums[i]
      if not flag and len(nums) > 1 and nums[-1] < nums[-2]:
        nums[-1] = nums[-2]
      pre = float("-inf")
      for num in nums:
        if num < pre:
          return False
        pre = num
      return True
  
  

• func checkPossibility(nums []int) bool {
  	isSorted := func(nums []int) bool {
  		for i, b := range nums[1:] {
  			if nums[i] > b {
  				return false
  			}
  		}
  		return true
  	}
  	for i := 0; i < len(nums)-1; i++ {
  		a, b := nums[i], nums[i+1]
  		if a > b {
  			nums[i] = b
  			if isSorted(nums) {
  				return true
  			}
  			nums[i] = a
  			nums[i+1] = a
  			return isSorted(nums)
  		}
  	}
  	return true
  }
  

• function checkPossibility(nums: number[]): boolean {
      const isSorted = (nums: number[]) => {
          for (let i = 0; i < nums.length - 1; ++i) {
              if (nums[i] > nums[i + 1]) {
                  return false;
              }
          }
          return true;
      };
      for (let i = 0; i < nums.length - 1; ++i) {
          const a = nums[i],
              b = nums[i + 1];
          if (a > b) {
              nums[i] = b;
              if (isSorted(nums)) {
                  return true;
              }
              nums[i] = a;
              nums[i + 1] = a;
              return isSorted(nums);
          }
      }
      return true;
  }
  
  

All Problems

All Solutions