Devin's Blog

Non Decreasing Array

2 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • Mark the element you see that is out of order, and change its ordering.
  • If you see more than one element who’s order must change, then return False.
  • What tripped me up was this case:
    • [5, 7, 1, 8]
    • In this case, while I am at the 7, I return False immediately since the 7 is greater than 1, and 1 is greater than 5, meaning:
      • If I try to change 7 to be 1, through transitivity I am also making 7 less than 5, thereby messing up the ordering.
    • However, if I simply change the 1 to be equal to 7, then I am marking that element as changed while still giving a chance that everything will be in order as I finish.
    • This works since by setting the 1 equal to 7, I am not messing with the orders of the previous values while still accounting for the fact that changing 1 to 7 may not be enough in the future (for example with [5, 7, 1, 0]).

Complexity

Runtime

Space

Code

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        n = len(nums)
        descending = False
        for i in range(n - 1):
            # Mark as descending order
            if nums[i] > nums[i + 1]:
                if descending:
                    return False
                descending = True
                if i != 0:
                    if nums[i - 1] > nums[i + 1]:
                        nums[i + 1] = nums[i]
                    else: # Edge case
                        nums[i] = nums[i - 1]
        return True

Notes

Cards

START Basic Front: Non Decreasing Array Back: Mark an element as changed, but make sure to mark the correct element.

END

References

Graph View