How do you solve Non-decreasing Array on LeetCode?

Non-decreasing Array (LeetCode #665) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Only one modification is allowed, so we need to track how many times the non-decreasing condition fails.

What is the time complexity of Non-decreasing Array?

The optimal solution for Non-decreasing Array runs in O(n) time and uses O(1) space. The time complexity is O(n) because we only make a single pass through the array, checking each pair of elements once.

What is the brute force solution for Non-decreasing Array?

The brute force approach for Non-decreasing Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks all possible modifications of the array by iterating through each element and attempting to change it. If any modification results in a non-decreasing array, we return true. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Non-decreasing Array?

Non-decreasing Array uses the following concepts: Array. The recommended patterns to study are: Array, Two Pointers.

What are the interview tips for Non-decreasing Array?

Always clarify the constraints and requirements before jumping into coding. Think about edge cases, such as arrays of length 1 or 2. Discuss your thought process out loud to help the interviewer follow your reasoning.

What are common mistakes when solving Non-decreasing Array?

Not checking the previous element when modifying the current one. Failing to count the number of modifications correctly.

#665

Non-decreasing Array

Medium

ArrayArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution iterates through the array just once, counting how many times the non-decreasing condition fails. If it fails more than once, we cannot fix it with a single modification.

⚙️

Algorithm

4 steps

1Step 1: Initialize a counter to count the number of modifications needed.
2Step 2: Iterate through the array and check if nums[i] > nums[i + 1].
3Step 3: If the condition fails, increment the counter and check if we can adjust either nums[i] or nums[i + 1] to maintain the non-decreasing property.
4Step 4: If the counter exceeds 1, return false; otherwise, return true.

solution.py16 lines

1# Full working Python code
2
3def checkPossibility(nums):
4    count = 0
5    for i in range(len(nums) - 1):
6        if nums[i] > nums[i + 1]:
7            count += 1
8            if count > 1:
9                return False
10            # Adjust nums[i] or nums[i + 1]
11            if i > 0 and nums[i - 1] > nums[i + 1] and i + 1 < len(nums) - 1:
12                nums[i + 1] = nums[i]
13    return True
14
15# Example usage
16print(checkPossibility([4, 2, 3]))  # Output: True

ℹ

Complexity note: The time complexity is O(n) because we only make a single pass through the array, checking each pair of elements once.

1Only one modification is allowed, so we need to track how many times the non-decreasing condition fails.
2Adjusting elements should be done carefully to maintain the overall order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.