_665. Non-decreasing Array.md

665. Non-decreasing Array

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 14, 2024

Last updated : July 04, 2024

---

Related Topics : Array

Acceptance Rate : 24.9 %

---

Idea
    Go through each adjacent pairing until you find an increasing pairing
    
    If found, check to see if it's the last value causing the decrease.
        Return True if it is cause we can just change to be infinity or starmap
        
        Iterate through the values to the right of the issue section to see if
        there's another issue. If there is, return False cause we're only alowed
        to modify one value.

        Return True if the problem value is the first pairing, since we can just
        nums[0] = -inf to solve it

        Return True if by deleting the value or by deleting the value before, the 
        two halves connect and are non-decreasing.

        It's an OR cause it could be smt like [1, 2, 5, 7, 3, 5, 6] where (7, 3) is
        the flagged pair but (5, 3) by deleting 7 doesn't work and (7, 5) by deleting
        3 also doesn't work

    If no increasing pair found at all, return true
    

---

Solutions

• m665.java
• m665.py

Java

m665.java

class Solution {
    public boolean checkPossibility(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (!(nums[i - 1] > nums[i])) {
                continue;
            }

            if (i + 1 >= nums.length) {
                return true;
            }

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j - 1] > nums[j]) {
                    return false;
                }
            }

            if (i == 1) {
                return true;
            }

            return (nums[i - 2] <= nums[i]) || (nums[i - 1] <= nums[i + 1]);
        }

        return true;
    }
}

Python

m665.py

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        for i in range(1, len(nums)) :
            if nums[i - 1] > nums[i] :
                # is last val causing so we don't have to "reconnect"
                if i + 1 >= len(nums) :
                    return True

                # if right half has issue, we have more than 1 edit confirmed
                for j in range(i + 1, len(nums)) :
                    if nums[j - 1] > nums[j] :
                        return False
                
                # if issue is the starting value, we don't have to check the two sides
                if i == 1 :
                    return True

                # if deleting one of the two values will allow the two halves to connect
                # so that they're non-decending, we good
                return (nums[i - 2] <= nums[i]) or (nums[i - 1] <= nums[i + 1])

        # by default already non-decending
        return True