Solution by awice


  • 1

    Approach #1: Brute Force [Time Limit Exceeded]

    Intuition

    For the given array A, if we are changing at most one element A[i], we should change A[i] to A[i-1], as it would be guaranteed that A[i-1] <= A[i], and A[i] would be the smallest possible to try and achieve A[i] <= A[i+1].

    Algorithm

    For each possible change A[i], check if the sequence is monotone increasing. We'll modify new, a copy of the array A.

    Python

    class Solution(object):
        def checkPossibility(self, A):
            def monotone_increasing(arr):
                for i in range(len(arr) - 1):
                    if arr[i] > arr[i+1]:
                        return False
                return True
    
            for i in range(len(A)):
                old_ai = A[i]
                A[i] = A[i-1] if i > 0 else float('-inf')
                if monotone_increasing(A):
                    return True
                A[i] = old_ai
    
            return False
    

    Java

    class Solution {
        private boolean monotoneIncreasing(int[] nums) {
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] > nums[i+1]) return false;
            }
            return true;
        }
        public boolean checkPossibility(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                int old = nums[i];
                nums[i] = i > 0 ? nums[i-1] : Integer.MIN_VALUE;
                if (monotoneIncreasing(nums)) return true;
                nums[i] = old;
            }
            return false;
        }
    }
    

    Complexity Analysis

    • Time Complexity: Let $$N$$ be the length of the given array. For each element A[i], we check if some sequence is monotone increasing, which takes $$O(N)$$ steps. In total, this is a complexity of $$O(N^2)$$.

    • Space Complexity: Only $$O(1)$$ additional space was used.


    Approach #2: Reduce to Smaller Problem [Accepted]

    Intuition

    If A[0] <= A[1] <= A[2], then we may remove A[0] without changing the answer. Similarly, if A[len(A)-3] <= A[len(A)-2] <= A[len(A)-1], we may remove A[len(A)-1] without changing the answer.

    If the problem is solvable, then after these removals, very few numbers will remain.

    Algorithm

    Consider the interval [i, j] corresponding to the subarray [A[i], A[i+1], ..., A[j]]. When A[i] <= A[i+1] <= A[i+2], we know we do not need to modify A[i], and we can consider solving the problem on the interval [i+1, j] instead. We use a similar approach for j.

    Afterwards, with the length of the interval under consideration being j - i + 1, if the interval has size 2 or less, then we did not find any problem. If our interval under consideration has 5 or more elements, then there are two disjoint problems that cannot be fixed with one replacement. Otherwise, our problem size is now at most 4 elements, which we can easily brute force.

    Python

    class Solution(object):
        def checkPossibility(self, A):
            def brute_force(A):
                # As in Approach #1
    
            i, j = 0, len(A) - 1
            while i+2 < len(A) and A[i] <= A[i+1] <= A[i+2]:
                i += 1
            while j-2 >= 0 and A[j-2] <= A[j-1] <= A[j]:
                j -= 1
    
            if j - i + 1 <= 2:
                return True
            if j - i + 1 >= 5:
                return False
    
            return brute_force(A[i: j+1])
    

    Java

    class Solution {
        private boolean monotoneIncreasing(int[] nums) {
            // As in Approach #1
        }
        public boolean bruteForce(int[] nums) {
            // As in Approach #1
        }
    
        public boolean checkPossibility(int[] nums) {
            int i = 0, j = nums.length - 1;
            while (i+2 < nums.length && nums[i] <= nums[i+1] && nums[i+1] <= nums[i+2]) i++;
            while (j-2 >= 0 && nums[j-2] <= nums[j-1] && nums[j-1] <= nums[j]) j--;
    
            if (j-i + 1 <= 2) return true;
            if (j-i + 1 >= 5) return false;
    
            return bruteForce(Arrays.copyOfRange(nums, i, j+1));
        }
    }
    

    Complexity Analysis

    • Time Complexity: Let $$N$$ be the length of the given array. Our pointers i and j move at most $$O(N)$$ times. Our brute force is constant time as there are at most 4 elements in the array. Hence, the complexity is $$O(N)$$.

    • Space Complexity: The extra array A[i: j+1] only has at most 4 elements, so it is constant space, and so is the space used by our auxillary brute force algorithm. In total, the space complexity is $$O(1)$$.


    Approach #3: Locate and Analyze Problem Index [Accepted]

    Intuition

    Consider all indices p for which A[p] > A[p+1]. If there are zero, the answer is True. If there are 2 or more, the answer is False, as more than one element of the array must be changed for A to be monotone increasing.

    At the problem index p, we only care about the surrounding elements. Thus, immediately the problem is reduced to a very small size that can be analyzed by casework.

    Algorithm

    As before, let p be the unique problem index for which A[p] > A[p+1]. If this is not unique or doesn't exist, the answer is False or True respectively. We analyze cases:

    • If p = 0, then we could make the array good by setting A[p] = A[p+1].
    • If p = len(A) - 2, then we could make the array good by setting A[p+1] = A[p].
    • Otherwise, A[p-1], A[p], A[p+1], A[p+2] all exist, and:
      • We could change A[p] to be between A[p-1] and A[p+1] if possible, or;
      • We could change A[p+1] to be between A[p] and A[p+2] if possible.

    Python

    class Solution(object):
        def checkPossibility(self, A):
            p = None
            for i in xrange(len(A) - 1):
                if A[i] > A[i+1]:
                    if p is not None:
                        return False
                    p = i
    
            return (p is None or p == 0 or p == len(A)-2 or
                    A[p-1] <= A[p+1] or A[p] <= A[p+2])
    

    Java

    class Solution {
        public boolean checkPossibility(int[] nums) {
            int p = -1;
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] > nums[i+1]) {
                    if (p >= 0) return false;
                    p = i;
                }
            }
            return (p == -1 || p == 0 || p == nums.length - 2 ||
                    nums[p-1] <= nums[p+1] || nums[p] <= nums[p+2]);
        }
    }
    

    Complexity Analysis

    • Time Complexity: Let $$N$$ be the length of the given array. We loop through the array once, so our time complexity is $$O(N)$$.

    • Space Complexity: We only use p, i, and the answer itself as additional space. The additional space complexity is $$O(1)$$.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.