algoadvance

Leetcode 665. Non

Problem Statement

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 as non-decreasing if nums[i] <= nums[i + 1] 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.
2. Input: nums = [4,2,1]
   • Output: false
   • Explanation: You can’t get a non-decreasing array by modifying just one element.

Constraints:

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

Clarifying Questions

1. Can the array be empty?
   • No, n is guaranteed to be at least 1.
2. Are there any constraints on modifying elements to make the array non-decreasing?
   • You are allowed to modify any element to achieve the objective.

Strategy

1. Identify Violations: Iterate through the array to find points where nums[i] > nums[i + 1].
2. Count Violations: If more than one violation is found, return false.
3. Adjustments:
   • If a violation is found at nums[i] > nums[i + 1], decide whether to adjust nums[i] or nums[i + 1] based on surrounding elements.
   • If i == 0 or nums[i - 1] <= nums[i + 1], decrease nums[i].
   • Else, increase nums[i + 1].
4. Return Result: If only one or no violations are found after the loop, return true.

Code

#include <vector>
using namespace std;

bool checkPossibility(vector<int>& nums) {
    int countViolations = 0;

    for (int i = 0; i < nums.size() - 1; ++i) {
        if (nums[i] > nums[i + 1]) {
            // If already more than one modification required
            if (countViolations == 1) {
                return false;
            }
            countViolations++;

            // If this is the first element, or we can adjust nums[i]
            if (i == 0 || nums[i - 1] <= nums[i + 1]) {
                nums[i] = nums[i + 1];
            } else {
                // Otherwise adjust nums[i + 1]
                nums[i + 1] = nums[i];
            }
        }
    }
    return true;
}

Time Complexity

• Time Complexity: (O(n)), where n is the number of elements in the input array. This is because we only traverse the array once.
• Space Complexity: (O(1)) since we are using a constant amount of additional space.

This approach ensures that we check the minimum number of changes needed and decide appropriately based on the current and previous elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?