Last updated on February 12th, 2025 at 02:19 am
Here, we see a Non-decreasing Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array
Companies
Level of Question
Medium
Non-decreasing Array LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Greedy Algorithm”. The code attempts to determine if the array can be made non-decreasing by modifying at most one element. It greedily checks for violations of the non-decreasing property and resolves them in a way that minimizes further violations.
3. Code Implementation in Different Languages
3.1 Non-decreasing Array C++
class Solution {
public:
bool checkPossibility(vector<int>& nums)
{
for(int i=0;i<nums.size()-1;i++)
{
if(nums[i]>nums[i+1])
{
if(i-1>=0&&nums[i-1]>nums[i+1])
{
nums[i+1]=nums[i];
}
else
{
nums[i]=nums[i+1];
}
break;
}
}
for(int i=0;i<nums.size()-1;i++)
{
if(nums[i]>nums[i+1])
{
return false;
}
}
return true;
}
};
3.2 Non-decreasing Array Java
class Solution {
public boolean checkPossibility(int[] nums) {
for (int i = 1, err = 0; i < nums.length; i++)
if (nums[i] < nums[i-1])
if (err++ > 0 || (i > 1 && i < nums.length - 1 && nums[i-2] > nums[i] && nums[i+1] < nums[i-1]))
return false;
return true;
}
}
3.3 Non-decreasing Array JavaScript
var checkPossibility = function(nums) {
for (let i = 1, err = 0; i < nums.length; i++)
if (nums[i] < nums[i-1])
if (err++ || (i > 1 && i < nums.length - 1 && nums[i-2] > nums[i] && nums[i+1] < nums[i-1]))
return false
return true
};
3.4 Non-decreasing Array Python
class Solution(object):
def checkPossibility(self, nums):
err = 0
for i in range(1, len(nums)):
if nums[i] < nums[i-1]:
if err or (i > 1 and i < len(nums) - 1 and nums[i-2] > nums[i] and nums[i+1] < nums[i-1]):
return False
err = 1
return True
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(1) |
| Python | O(n) | O(1) |
- The code is efficient and works in linear time with constant space.
- It uses a greedy approach to resolve violations of the non-decreasing property.
- The logic is implemented consistently across all four languages, with minor syntactic differences.