TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Q: What is the input to the function?
nums
containing n
integers.Q: What is the expected output of the function?
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?
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?
True
.Q: Can the array contain negative numbers or be empty?
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.
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
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