Non Decreasing Array Leetcode Problem 665 [Python Solution]

Welcome to another coding adventure!

In this blog post, we'll tackle the "Non-Decreasing Array" problem.

This problem asks us to determine if it's possible to transform an array into a non-decreasing array by modifying at most one element.

We'll explore an efficient Python solution for this problem, break down the algorithm, and discuss its time and space complexity.

So, let's dive in and solve the Non-Decreasing Array problem together!

Problem Overview

The problem statement is as follows:

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.

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• -10^5 <= nums[i] <= 10^5

To solve this problem, we need to develop an algorithm that determines if it's possible to transform the given array into a non-decreasing one by modifying at most one element.

Understanding Non-Decreasing Array Constraints

Before diving into the solution, let's understand the constraints mentioned in the problem:

• n is the length of the array nums, and it ranges from 1 to 10,000.
• The values in the array nums can range from -100,000 to 100,000.

Non-Decreasing Array LeetCode Problem Solution

Let's explore an efficient Python solution for the Non-Decreasing Array problem.

We'll go through the approach and provide a step-by-step explanation of the code.

1. Efficient Approach with Python Code

def checkPossibility(nums):
    if len(nums) <= 2:
        return True
    changed = False
    for i, num in enumerate(nums):
        if i == len(nums) - 1 or num <= nums[i + 1]:
            continue
        if changed:
            return False
        if i == 0 or nums[i + 1] >= nums[i - 1]:
            nums[i] = nums[i + 1]
        else:
            nums[i + 1] = nums[i]
        changed = True
    return True

Let's break down the code step by step:

• We define a function called checkPossibility that takes an array nums as its input.

• First, we handle the base case.

If the length of the array is less than or equal to 2, it is trivially non-decreasing, and we return True.

• We initialize a boolean variable changed to keep track of whether we've made a change to the array.

• Next, we iterate through the elements of the array using a for loop and an index i.

• Inside the loop, we check if we've reached the last element of the array or if the current element num is less than or equal to the next element in the array (nums[i + 1]).

If this condition is met, we continue to the next iteration of the loop.

• If the current element is greater than the next element, it means we've found a pair of elements that violates the non-decreasing condition.

• If changed is already True, it means we've made a change earlier, and we cannot make another change while preserving the non-decreasing order.

In this case, we return False.

• Now, we need to decide whether to modify the current element (nums[i]) or the next element (nums[i + 1]) to make the array non-decreasing.

We have two options:

- If `i` is 0 (the first element) or if the next element is greater than or equal to the previous element (`nums[i + 1] >= nums[i - 1]`), we modify the current element by setting it equal to the next element.

- Otherwise, we modify the next element by setting it equal to the current element.

• After making the necessary change, we set changed to True to indicate that we've made a change.

• Once the loop is completed, if we haven't encountered any issues, we return True, indicating that it's possible to make the array non-decreasing with at most one modification.

This efficient algorithm ensures that we make the optimal choices when deciding which element to modify while maintaining the non-decreasing property.

Non-Decreasing Array Python Code Solution

Here's the Python code for the checkPossibility function:

def checkPossibility(nums):
    if len(nums) <= 2:
        return True
    changed = False
    for i, num in enumerate(nums):
        if i == len(nums) - 1 or num <= nums[i + 1]:
            continue
        if changed:
            return False
        if i == 0 or nums[i + 1] >= nums[i - 1]:
            nums[i] = nums[i + 1]
        else:
            nums[i + 1] = nums[i]
        changed = True
    return True

You can use this function to check if a given array can be transformed into a non-decreasing array by modifying at most one element.

Time and Space Complexity

Now, let's analyze the time and space complexity of our solution:

• Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the input array nums.

We iterate through the array once, and the operations inside the loop are constant time.

• Space Complexity: The space complexity is O(1), as we use only a constant amount of additional memory to store variables such as changed, i, and num.

Reasoning Behind Our Efficient Approach

The reasoning behind our approach lies in making the optimal choices when deciding which element to modify while preserving the non-decreasing property.

We aim to minimize the number of changes and maximize the possibilities for the remaining elements in the array.

In cases where we have a choice, we prefer to decrease the left element if possible.

This choice is made because it gives us more flexibility for the remaining elements in the array.

By ensuring that the left element is as small as necessary to maintain non-decreasing order, we maximize the possibilities for the elements ahead.

However, we need to handle some edge cases, such as when we can't change the left element because it's already at its minimum.

In such cases, we modify the right element to match the left element's value while preserving the non-decreasing order.

Related Interview Questions By Company:

• Unique Paths II LeetCode
• Encode And Decode Tinyurl LeetCode
• Ones And Zeroes LeetCode

Related Interview Questions By Difficulty:

• Next Greater Element I LeetCode
• Find All Anagrams In A String LeetCode
• Best Time To Buy And Sell Stock II LeetCode

Related Interview Questions By Category:

• Combination Sum II LeetCode
• Same Tree LeetCode
• Climbing Stairs LeetCode

Conclusion

In this blog post, we tackled the "Non-Decreasing Array" problem, which asked us to determine if an array can be transformed into a

non-decreasing array by modifying at most one element.

We presented an efficient Python solution and explained the algorithm step by step.

The solution optimally handles various edge cases and ensures that we make the best choices when deciding which element to modify.

With a time complexity of O(n) and a space complexity of O(1), this solution is both efficient and effective.

If you found this blog post helpful, please like and engage to support our our platform.

Feel free to comment, ask questions, make suggestions, and share this content with others.

Check out the problem on LeetCode.

Happy coding!