LeetCode 665: Non-decreasing Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 665: Non-decreasing Array?

In LeetCode 665: Non-decreasing Array, you’re given an integer array nums, and your task is to determine if it’s possible to make the array non-decreasing by modifying at most one element. A non-decreasing array satisfies nums[i] <= nums[i+1] for all i. Return True if such a modification is possible, False otherwise. For example, with nums = [4, 2, 3], changing 4 to 1 yields [1, 2, 3], which is non-decreasing, so it’s True. With nums = [4, 2, 1], no single change works, so it’s False. This problem tests your ability to identify and resolve a single violation in a sequence.

Problem Statement

• Input:
• nums: List of integers.
• Output: A boolean—True if array can be made non-decreasing with ≤ 1 change, False otherwise.
• Rules:
• Non-decreasing: nums[i] <= nums[i+1] for all i.
• Modify at most one element.
• Check if result is possible.

Constraints

• 2 ≤ nums.length ≤ 10⁴.
• -10⁵ ≤ nums[i] ≤ 10⁵.

Examples

• Input: nums = [4, 2, 3]
• Output: True (Change 4 to 1: [1, 2, 3])
• Input: nums = [4, 2, 1]
• Output: False (No single change works)
• Input: nums = [3, 4, 2, 3]
• Output: False (Two dips: 4 to 2, 2 to 3)

These examples set the array—let’s solve it!

Understanding the Problem: Making It Non-decreasing

To solve LeetCode 665: Non-decreasing Array in Python, we need to check if we can modify at most one element in nums to make it non-decreasing, where each element is at least as large as the one before it. A brute-force approach—trying to modify each element and checking—would be O(n²), inefficient for n ≤ 10⁴. Since we’re looking for a single fix, we can optimize by scanning for violations and deciding how to adjust. We’ll use:

• Best Solution (Greedy Single-Pass): O(n) time, O(1) space—fast and intuitive.
• Alternative Solution (Brute-Force with Modification): O(n²) time, O(n) space—simple but slow.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy Single-Pass

Why This Is the Best Solution

The greedy single-pass approach is the top choice for LeetCode 665 because it’s efficient—O(n) time with O(1) space—and uses a single scan to count violations, greedily deciding how to fix each dip while ensuring only one change is used. It fits constraints (n ≤ 10⁴) perfectly and is easy to follow once you see the logic. It’s like walking through the array and smoothing out one bump at a time!

How It Works

Think of this as an array smoother:

• Step 1: Initialize Violation Count:
• changes = 0 to track modifications.
• Step 2: Scan for Violations:
• For each pair nums[i] > nums[i+1]:
• Increment changes.
• If changes > 1, return False.
• Decide fix:
• If i == 0 or nums[i-1] <= nums[i+1], lower nums[i] to nums[i+1].
• Else, raise nums[i+1] to nums[i].
• Step 3: Return Result:
• Return True if changes <= 1, False otherwise.

It’s like a dip fixer—scan and adjust!

Step-by-Step Example

Example: nums = [4, 2, 3]

• Step 1: changes = 0.
• Step 2: Scan:
• i=0: 4 > 2, changes = 1.
• i == 0, lower nums[0] to 2: [2, 2, 3] works.
• i=1: 2 <= 3, no change.
• Step 3: changes = 1 ≤ 1, return True.
• Output: True.

Example: nums = [3, 4, 2, 3]

• Step 1: changes = 0.
• Step 2: Scan:
• i=0: 3 <= 4, no change.
• i=1: 4 > 2, changes = 1.
• nums[i-1]=3 > nums[i+1]=2, raise nums[2] to 4: [3, 4, 4, 3].
• i=2: 4 > 3, changes = 2 > 1, return False.
• Output: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        # Step 1: Initialize change counter
        changes = 0
        n = len(nums)

        # Step 2: Scan for violations
        for i in range(n - 1):
            if nums[i] > nums[i + 1]:
                changes += 1
                if changes > 1:
                    return False

                # Decide how to fix
                if i == 0 or nums[i - 1] <= nums[i + 1]:
                    # Lower nums[i] to match nums[i+1]
                    pass  # Check only, no modification needed
                else:
                    # Raise nums[i+1] to match nums[i]
                    pass  # Check only, no modification needed

        # Step 3: Return result
        return True

• Lines 4-5: Init: Counter and length.
• Lines 8-19: Scan:
• Check each pair, count violations, decide fix direction (logical check only).
• Line 22: Return True if ≤ 1 change.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—no extra space.

This is like an array adjuster—scan and fix!

Alternative Solution: Brute-Force with Modification

Why an Alternative Approach?

The brute-force with modification approach tries modifying each element—O(n²) time, O(n) space. It’s simpler conceptually, testing each possible change and verifying, but inefficient for large n. It’s like trying every tweak until one works!

How It Works

Picture this as a trial tweaker:

• Step 1: For each index i:
• Save original value.
• Step 2: Try modifications:
• Set nums[i] to adjacent values or infinity.
• Check if non-decreasing.
• Step 3: Restore and repeat.
• Step 4: Return result.

It’s like a tweak tester—try and check!

Step-by-Step Example

Example: nums = [4, 2, 3]

• Step 1: i=0, orig = 4.
• Try nums[0]=2: [2, 2, 3], works, return True.
• Output: True.

Example: nums = [3, 4, 2, 3]

• Step 1: Try each:
• i=0: [2, 4, 2, 3], fails.
• i=1: [3, 3, 2, 3], fails.
• i=2: [3, 4, 4, 3], fails.
• i=3: [3, 4, 2, 4], fails.
• Step 2: No single fix works, return False.
• Output: False.

Code for Brute-Force Approach

Copy codeclass Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        # Step 1: Check original array
        def is_non_decreasing(arr):
            for i in range(len(arr) - 1):
                if arr[i] > arr[i + 1]:
                    return False
            return True

        # Step 2: Try modifying each element
        n = len(nums)
        orig = nums.copy()

        for i in range(n):
            # Try setting to previous or next value
            orig_val = nums[i]
            if i == 0:
                nums[i] = nums[i + 1] if i + 1 < n else 0
            elif i == n - 1:
                nums[i] = nums[i - 1]
            else:
                nums[i] = nums[i - 1]
            if is_non_decreasing(nums):
                return True
            nums[i] = orig_val  # Restore

        # Step 3: Return result
        return is_non_decreasing(orig)

• Lines 4-9: Helper: Check if array is non-decreasing.
• Lines 12-24: Try:
• Copy array, modify each index, check, restore.
• Line 27: Check original.
• Time Complexity: O(n²)—n modifications, O(n) checks each.
• Space Complexity: O(n)—copy of array.

It’s a trial fixer—modify and test!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n) time, O(1) space, fast and elegant.
• Cons: Greedy logic less obvious.
• Brute-Force (Alternative):
• Pros: O(n²) time, O(n) space, straightforward.
• Cons: Slower, more space.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• Input: [1, 2]
• Output: True.
• Input: [5, 7, 1, 8]
• Output: True (Change 1 to 7: [5, 7, 7, 8]).

Greedy handles these well.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Brute-Force: Time O(n²), Space O(n).

Greedy is optimal.

Key Takeaways

• Greedy: Single-pass smoothing—smart!
• Brute-Force: Trial tweaking—clear!
• Arrays: Fixing is fun.
• Python Tip: Loops rock—see Python Basics.

Final Thoughts: Smooth That Array

LeetCode 665: Non-decreasing Array in Python is a fun array challenge. Greedy single-pass offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 283: Move Zeroes or LeetCode 88: Merge Sorted Array. Ready to tweak? Head to Solve LeetCode 665 on LeetCode and make that array non-decreasing today!