Non Decreasing Array - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Conditionals, Iteration

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input is an array nums containing n integers.

• Q: What is the expected output of the function?

  • A: The function should return True if the array nums can be made non-decreasing by modifying at most one element, otherwise False.

• Q: What does it mean for an array to be non-decreasing?

  • A: An array is non-decreasing if for every i from 0 to n-2, the condition nums[i] <= nums[i + 1] holds true.

• Q: What should be done if the array has only one element or is already non-decreasing?

  • A: If the array has only one element or is already non-decreasing, the function should return True.

• Q: Can the array contain negative numbers or be empty?

  • A: Yes, the array can contain negative numbers. If the array is empty, the function should return True.

• The function non_decreasing() should take an array nums and return True if it can be made non-decreasing by modifying at most one element. It returns False otherwise.

HAPPY CASE
Input: [4, 2, 3]
Expected Output: True
Explanation: Modify 4 to 1 to get the array [1, 2, 3], which is non-decreasing.

Input: [3, 4, 2, 3]
Expected Output: False
Explanation: More than one modification is needed to make the array non-decreasing.

EDGE CASE
Input: [1, 2, 3]
Expected Output: True
Explanation: The array is already non-decreasing, so no modification is needed.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the array and count violations of the non-decreasing condition. If there is more than one violation, return False. If a violation occurs, check if modifying either of the involved elements can resolve it.

1. Define the function `non_decreasing(nums)`.
2. Initialize a variable `count` to 0 to track violations.
3. Iterate through the array from the first to the second-to-last element:
   - If `nums[i] > nums[i + 1]`, increment `count`.
   - If `count > 1`, return `False`.
   - If a violation is detected, check if modifying `nums[i]` or `nums[i + 1]` can resolve it:
     - Modify `nums[i]` if it's the first element or the previous element is less than or equal to `nums[i + 1]`.
     - Otherwise, modify `nums[i + 1]`.
4. Return `True` if the array can be made non-decreasing.

⚠️ Common Mistakes

• Not properly checking if modifying either nums[i] or nums[i + 1] resolves the violation.
• Forgetting to return False if more than one modification is needed.

I-mplement

Implement the code to solve the algorithm.

def non_decreasing(nums):
    n = len(nums)
    count = 0  # Count of violations
    
    for i in range(n - 1):
        if nums[i] > nums[i + 1]:
            count += 1
            if count > 1:
                return False
            
            # Check if we can resolve the violation by modifying nums[i] or nums[i + 1]
            if i == 0 or nums[i - 1] <= nums[i + 1]:
                nums[i] = nums[i + 1]  # Modify nums[i]
            else:
                nums[i + 1] = nums[i]  # Modify nums[i + 1]
    
    return True