665. Non-decreasing Array

MediumArray
Leetcode Link

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:

  1. 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.

  2. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does merge sort divide the problem into subproblems?

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:

  1. The function checkPossibility begins by iterating over the array nums using a loop that runs from the starting index to the second-to-last index of the array.
  2. In each iteration, it compares the current element nums[i] with the next element nums[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.
  3. 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 the is_sorted function to check if this change makes the entire array non-decreasing. If so, it returns True.
    • 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 sets nums[i + 1] = nums[i]. Then it checks with the is_sorted function once more. If the array is non-decreasing after this change, it returns True.
  4. 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.
  5. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example 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.

  1. We start by checking the array from left to right. We compare the first and second elements: 4 and 2. Since 4 is greater than 2, this violates the non-decreasing order.

  2. Now, we have two possibilities to correct the array:

    • We can lower the first element 4 to 2, making the array [2, 2, 3].
    • We can raise the second element 2 to 4, making the array [4, 4, 3].

  3. Let's try the first possibility. We lower 4 to 2. 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.

  4. Since the array [2, 2, 3] is non-decreasing, we return True, 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
Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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 in O(n) where n is the number of elements in nums.
  • The is_sorted function is O(n), as it evaluates all adjacent pairs in nums.
  • In the worst-case scenario, is_sorted is called twice, maintaining O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫