665. Non-decreasing Array LeetCode Solution

In this guide, you will get 665. Non-decreasing Array LeetCode Solution with the best time and space complexity. The solution to Non-decreasing Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Non-decreasing Array solution in C++
4. Non-decreasing Array solution in Java
5. Non-decreasing Array solution in Python
6. Additional Resources

Problem Statement of Non-decreasing Array

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

Complexity Analysis

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

665. Non-decreasing Array LeetCode Solution in 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 the previous value.
        else
          nums[i] = nums[i - 1];  // Increase the current value.
        modified = true;
      }

    return true;
  }
};
/* code provided by PROGIEZ */

665. Non-decreasing Array LeetCode Solution in 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];
  }
}
// code provided by PROGIEZ

665. Non-decreasing Array LeetCode Solution in 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])
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.