665. Non-decreasing Array
Problem Description
This problem requires us to assess whether a given array nums
containing n
integers can be converted into a non-decreasing array by altering no more than one element. An array is regarded as non-decreasing if for every index i
, where i
ranges from 0
to n - 2
, the following condition is satisfied: nums[i] <= nums[i + 1]
. The challenge lies in determining whether we can achieve such a state with a single modification or if the array's current state is already non-decreasing.
Intuition
To solve this problem, we must iterate through the array and identify any pair of consecutive elements where the first is greater than the second (nums[i] > nums[i + 1]
). This condition indicates that the array is not non-decreasing at that point. When we find such a pair, we have two possible actions to try:
-
Lower the first element (
nums[i]
) to match the second one (nums[i + 1]
), which can help maintain a non-decreasing order if the rest of the array is non-decreasing. -
Alternatively, raise the second element (
nums[i + 1]
) to match the first one (nums[i]
), which again can make the entire array non-decreasing if the rest of it adheres to the rule.
For both scenarios, after making the change, we need to check if the entire array is non-decreasing. If it is, then we can achieve the goal with a single modification. If we make it through the entire array without needing more than one change, the array is either already non-decreasing or can be made so with one modification. The key here is recognizing that if there are two places where nums[i] > nums[i + 1]
, we can't make the array non-decreasing with just a single change.
The given solution iterates through the array, checks for the condition that violates the non-decreasing order, and performs only one of the two modifications mentioned above. It then verifies if the whole array is non-decreasing following that modification. If this check is passed, it returns True
. If the loop is exhausted without having to make any changes, the array is already non-decreasing, and so, the function also returns True
.
Solution Approach
The solution employs a straightforward iterative approach along with a helper function is_sorted
, which checks if the array passed to it is non-decreasing. This is done using the pairwise
utility to traverse the array in adjacent pairs and ensuring each element is less than or equal to the next.
Here's a step-by-step breakdown of the algorithm:
- The function
checkPossibility
begins by iterating over the arraynums
using a loop that runs from the starting index to the second-to-last index of the array. - In each iteration, it compares the current element
nums[i]
with the next elementnums[i + 1]
. If it finds these elements are ordered correctly (nums[i] <= nums[i + 1]
), it continues to the next pair; otherwise, it indicates a potential spot for correction. - When a pair is found where
nums[i] > nums[i + 1]
, the solution has two possibilities for correction:- Lower the first element: It sets
nums[i] = nums[i + 1]
to match the second element and uses theis_sorted
function to check if this change makes the entire array non-decreasing. If so, it returnsTrue
. - Raise the second element: If the previous step does not yield a non-decreasing array, the solution resets
nums[i]
to its original value and setsnums[i + 1] = nums[i]
. Then it checks with theis_sorted
function once more. If the array is non-decreasing after this change, it returnsTrue
.
- Lower the first element: It sets
- Throughout the iteration, if no change is needed or if the change leads to a non-decreasing array, the function moves to the next pair of elements.
- In a scenario where no pairs violate the non-decreasing order, the function will complete the loop and return
True
, as no alteration is required or a maximum of one was sufficient.
In this algorithm, the data structure used is the original input array nums
. The pattern employed here revolves around validating an array's non-decreasing property and the ability to stop as soon as the requirement is violated twice since that indicates more than one change would be necessary. The elegance of this solution lies in its O(n)
time complexity, as it requires only a single pass through the array to determine its non-decreasing property with at most one modification.
In summary, the provided solution correctly handles both the detection of a non-decreasing sequence violation and the decision-making for adjusting the array, efficiently reaching a verdict with minimal changes and checks.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach:
Suppose we have an array nums = [4, 2, 3]
. According to the problem, we are allowed to make at most one modification to make the array non-decreasing. Let's process this array according to the algorithm described above.
-
We start by checking the array from left to right. We compare the first and second elements:
4
and2
. Since4
is greater than2
, this violates the non-decreasing order. -
Now, we have two possibilities to correct the array:
- We can lower the first element
4
to2
, making the array[2, 2, 3]
. - We can raise the second element
2
to4
, making the array[4, 4, 3]
.
- We can lower the first element
-
Let's try the first possibility. We lower
4
to2
. Now we need to check if after this modification, the array is non-decreasing. By simple inspection, we see[2, 2, 3]
is indeed a non-decreasing array. -
Since the array
[2, 2, 3]
is non-decreasing, we returnTrue
, indicating that the original array[4, 2, 3]
can be made non-decreasing with a single modification.
The algorithm successfully finds the correct modification on the first try, and further evaluation is not necessary. The solution is efficient and adheres to O(n)
time complexity, as it processes each element of the array only once.
Solution Implementation
1from typing import List
2
3
4class Solution:
5 def check_possibility(self, nums: List[int]) -> bool:
6 # Helper function to check if the list is non-decreasing.
7 def is_sorted(arr: List[int]) -> bool:
8 for i in range(len(arr) - 1):
9 if arr[i] > arr[i+1]:
10 return False
11 return True
12
13 n = len(nums)
14 # Go through each pair in the list.
15 for i in range(n - 1):
16 # If the current element is greater than the next element, a modification is needed.
17 if nums[i] > nums[i + 1]:
18 # Temporarily change the current element to the next one and check if sorted.
19 temp = nums[i]
20 nums[i] = nums[i + 1]
21 if is_sorted(nums):
22 return True
23 # If not sorted, revert the change and modify the next element instead.
24 nums[i] = temp
25 nums[i + 1] = temp
26 return is_sorted(nums)
27 # If no modification needed, then it is already non-decreasing.
28 return True
29
30
31# Example usage:
32# sol = Solution()
33# print(sol.check_possibility([4,2,3])) # True
34# print(sol.check_possibility([4,2,1])) # False
35
1class Solution {
2
3 // Main method to check if the array can be made non-decreasing by modifying at most one element
4 public boolean checkPossibility(int[] nums) {
5 // Iterate through the array elements
6 for (int i = 0; i < nums.length - 1; ++i) {
7 // Compare current element with the next one
8 int current = nums[i];
9 int next = nums[i + 1];
10
11 // If the current element is greater than the next, we need to consider modifying one of them
12 if (current > next) {
13 // Temporarily modify the current element to the next element's value
14 nums[i] = next;
15 // Check if the array is sorted after this modification
16 if (isSorted(nums)) {
17 return true;
18 }
19 // Revert the change to the current element
20 nums[i] = current;
21 // Permanently modify the next element to the current element's value
22 nums[i + 1] = current;
23 // Return whether the array is sorted after this second modification
24 return isSorted(nums);
25 }
26 }
27 // If no modifications were needed, the array is already non-decreasing
28 return true;
29 }
30
31 // Helper method to check if the array is sorted in non-decreasing order
32 private boolean isSorted(int[] nums) {
33 // Iterate through the array elements
34 for (int i = 0; i < nums.length - 1; ++i) {
35 // If the current element is greater than the next, the array is not sorted
36 if (nums[i] > nums[i + 1]) {
37 return false;
38 }
39 }
40 // If no such pair is found, the array is sorted
41 return true;
42 }
43}
44
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to check if it's possible to make the array non-decreasing
7 // by modifying at most one element.
8 bool checkPossibility(std::vector<int>& nums) {
9 int n = nums.size(); // Get the size of the input array
10
11 // Iterate over the array to find a pair where the current element
12 // is greater than the next element.
13 for (int i = 0; i < n - 1; ++i) {
14 int current = nums[i], next = nums[i + 1];
15
16 // If a pair is found where the current element is greater than the next,
17 // we have two choices to fix the array:
18 // Either modify the current element to be equal to the next element,
19 // Or modify the next element to be equal to the current element.
20 if (current > next) {
21 // Temporarily modify the current element
22 nums[i] = next;
23
24 // Check if the array is sorted after this modification
25 if (std::is_sorted(nums.begin(), nums.end())) {
26 return true; // If sorted, return true
27 }
28
29 // Undo the modification of the current element
30 nums[i] = current;
31
32 // Permanently modify the next element to match the current element
33 nums[i + 1] = current;
34
35 // Return whether the array is sorted after modifying the next element
36 return std::is_sorted(nums.begin(), nums.end());
37 }
38 }
39
40 // If we never found a pair that needed fixing, the array is already
41 // non-decreasing, so we return true.
42 return true;
43 }
44};
45
1// This function checks if the array can be made non-decreasing by modifying at most one element.
2function checkPossibility(nums: number[]): boolean {
3 // Helper function to determine whether the array is sorted in non-decreasing order.
4 const isNonDecreasing = (arr: number[]): boolean => {
5 for (let i = 0; i < arr.length - 1; ++i) {
6 if (arr[i] > arr[i + 1]) {
7 return false;
8 }
9 }
10 return true;
11 };
12
13 // Main loop to check each pair of elements in the array.
14 for (let i = 0; i < nums.length - 1; ++i) {
15 const current = nums[i],
16 next = nums[i + 1];
17
18 // If the current element is greater than the next element,
19 // we try to make an adjustment and check if it resolves the non-decreasing order issue.
20 if (current > next) {
21 const temp = nums[i]; // Keep the original value to restore later if needed.
22
23 nums[i] = next; // Try lowering the current value to the next one's value.
24 if (isNonDecreasing(nums)) {
25 return true;
26 }
27
28 nums[i] = temp; // Restore the original value as the lowering approach did not work.
29 nums[i + 1] = current; // Try raising the next value to the current one's value.
30
31 // Return whether this adjustment resulted in a non-decreasing array.
32 return isNonDecreasing(nums);
33 }
34 }
35
36 // If no adjustments were needed, the array is already non-decreasing.
37 return true;
38}
39
Time and Space Complexity
Time Complexity
The time complexity of the checkPossibility
function consists of a for
loop that iterates through the elements of nums
once, and a potential two calls to the is_sorted
helper function within the loop if a disorder is found. The is_sorted
function iterates through the elements of nums
once to compare adjacent pairs.
Let's break it down:
- The
for
loop runs inO(n)
wheren
is the number of elements innums
. - The
is_sorted
function isO(n)
, as it evaluates all adjacent pairs innums
. - In the worst-case scenario,
is_sorted
is called twice, maintainingO(n)
for each call.
Thus, the time complexity is O(n)
for the single loop plus O(n)
for each of the two possible calls to is_sorted
, which yields a worst-case time complexity of O(n + 2n)
, simplified to O(n)
.
Space Complexity
The space complexity of the function is primarily O(1)
since the function only uses a constant extra space for the variables a
, b
, and i
, and modifies the input list nums
in-place.
However, considering the creation of the iterator over the pairwise comparison, if it is not optimized away by the interpreter, may in some cases add a small overhead, but this does not depend on the size of the input and hence remains O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.