#665

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Non-decreasing Array

Check if an array can become non-decreasing by modifying at most one element using an array-driven solution strategy.

Problem Statement

You are given an integer array nums with n elements. Your goal is to determine if it is possible to modify at most one element to make the array non-decreasing.

A non-decreasing array is defined as one where every element nums[i] is less than or equal to nums[i + 1] for all valid indices i. If you can achieve this by modifying one element, return true; otherwise, return false.

Examples

Example 1

Input: nums = [4,2,3]

Output: true

You could modify the first 4 to 1 to get a non-decreasing array.

Example 2

Input: nums = [4,2,1]

Output: false

You cannot get a non-decreasing array by modifying at most one element.

Constraints

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

Solution Approach

Initial Traversal

Traverse through the array while comparing each element with the next one. Track any violations where nums[i] > nums[i + 1]. This is crucial for identifying where modifications are needed.

Evaluate Modifications

When a violation is found, check if modifying the current element or the next one can resolve the issue. Make sure the modification does not create new violations in the array.

Edge Case Consideration

If there are multiple violations, more than one modification would be required, making it impossible to solve. Hence, return false immediately if more than one violation is encountered.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because we only need a single pass through the array. The space complexity is O(1), as no extra space is needed other than a few variables for tracking violations and modifications.

What Interviewers Usually Probe

Look for candidates who can correctly identify and handle violations in the array.
Evaluate if the candidate is able to make decisions based on a single modification possibility.
Pay attention to the candidate’s approach towards edge cases like multiple violations.

Common Pitfalls or Variants

Common pitfalls

Assuming that one modification always solves the problem, without verifying the array after modification.
Not handling the case where multiple violations are found, leading to incorrect results.
Over-complicating the solution by introducing unnecessary data structures or operations.

Follow-up variants

Modify the problem to allow up to two modifications and check how the candidate handles this.
Introduce larger arrays to see how the candidate optimizes for larger inputs.
Change the array to be a non-negative integer array, modifying the problem constraints.

FAQ

What is the pattern for solving the Non-decreasing Array problem?

The problem follows an array-driven solution strategy, focusing on identifying violations and making minimal modifications.

How can I determine if modifying one element is enough to solve the Non-decreasing Array problem?

You need to track any violations where nums[i] > nums[i + 1] and check if modifying the current or next element resolves the issue without introducing new violations.

How do I handle edge cases for the Non-decreasing Array problem?

If there are multiple violations in the array, return false immediately, as modifying just one element will not be sufficient.

Can multiple modifications be allowed in the Non-decreasing Array problem?

This problem specifically requires at most one modification. Allowing more modifications would change the problem's constraints and solution approach.

What is the time complexity of the Non-decreasing Array problem?

The time complexity is O(n) due to the need for a single pass through the array.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#667 beautiful arrangement ii #661 image smoother #659 split array into consecutive subsequences