Welcome to Subscribe On Youtube

665. Non-decreasing Array

Description

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one 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 cannot get a non-decreasing array by modifying at most one element.

 

Constraints:

• n == nums.length
• 1 <= n <= 104
• -105 <= nums[i] <= 105

Solutions

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

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

• class Solution {
  public:
      bool checkPossibility(vector<int>& nums) {
          int n = nums.size();
          for (int i = 0; i < n - 1; ++i) {
              int a = nums[i], b = nums[i + 1];
              if (a > b) {
                  nums[i] = b;
                  if (is_sorted(nums.begin(), nums.end())) {
                      return true;
                  }
                  nums[i] = a;
                  nums[i + 1] = a;
                  return is_sorted(nums.begin(), nums.end());
              }
          }
          return true;
      }
  };
  

• class Solution:
      def checkPossibility(self, nums: List[int]) -> bool:
          def is_sorted(nums: List[int]) -> bool:
              return all(a <= b for a, b in pairwise(nums))
  
          n = len(nums)
          for i in range(n - 1):
              a, b = nums[i], nums[i + 1]
              if a > b:
                  nums[i] = b
                  if is_sorted(nums):
                      return True
                  nums[i] = nums[i + 1] = a
                  return is_sorted(nums)
          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