Teaching Kids Programming – Remove One Element to Make the Array Strictly Increasing (LIS Algorithms)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a 0-indexed integer array nums, return true if it can be made strictly increasing after removing exactly one element, or false otherwise. If the array is already strictly increasing, return true. The array nums is strictly increasing if nums[i – 1] < nums[i] for each index (1 <= i < nums.length).

Example 1:
Input: nums = [1,2,10,5,7]
Output: true
Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7].
[1,2,5,7] is strictly increasing, so return true.

Example 2:
Input: nums = [2,3,1,2]
Output: false
Explanation:
[3,1,2] is the result of removing the element at index 0.
[2,1,2] is the result of removing the element at index 1.
[2,3,2] is the result of removing the element at index 2.
[2,3,1] is the result of removing the element at index 3.
No resulting array is strictly increasing, so return false.

Example 3:
Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any element is [1,1].
[1,1] is not strictly increasing, so return false.

Constraints:
2 <= nums.length <= 1000
1 <= nums[i] <= 1000

Hints:
For each index i in nums remove this index.
If the array becomes sorted return true, otherwise revert to the original array and try different index.

Bruteforce Algorithm to Check If Array is Strictly Increase at At Most 1 Removal

We can simulate removing each number and check if the remaining array is strictly increasing. O(N) for checking N choices, and O(N) for checking if an array is strictly increasing. The overall time complexity is O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        def is_strictly_increasing(arr):
            #return sorted(arr) == arr and len(arr) == len(set(arr))
            return all(arr[i] < arr[i + 1] for i in range(len(arr) - 1))
 
        for i in range(len(nums)):
            arr = nums[:i] + nums[i + 1:]
            if is_strictly_increasing(arr):
                return True
        
        return False

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        def is_strictly_increasing(arr):
            #return sorted(arr) == arr and len(arr) == len(set(arr))
            return all(arr[i] < arr[i + 1] for i in range(len(arr) - 1))

        for i in range(len(nums)):
            arr = nums[:i] + nums[i + 1:]
            if is_strictly_increasing(arr):
                return True
        
        return False

We can use the sorted() and rule out the duplicate elements to check if an array is strictly increasing, but that takes O(NLogN) time.

1
2

def is_sorted(arr):
    return sorted(arr) == arr and len(arr) == len(set(arr))

def is_sorted(arr):
    return sorted(arr) == arr and len(arr) == len(set(arr))

Longest Increasing Subsequence Length After Removing At Most 1 Number

If we remove one number (original array has N numbers), the longest increasing subsequence should be N-1. Thus, the problem is the same as checking the length of the Longest Increasing Subsequence should be at most N-1.

The O(N^2) Longest Increasing Subsequence Algorithm via Dynamic Programming Algorithm:

1
2
3
4
5
6
7
8
9

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)        
        return max(dp) + 1 >= n

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)        
        return max(dp) + 1 >= n

And the LIS can be done via a Greedy (more efficient) algorithm via bisect_left:

LIS in Greedy: Teaching Kids Programming – Greedy Algorithm to Find Longest Increasing Subsequence in O(NLogN) via Binary Search

1
2
3
4
5
6
7
8
9
10

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        lis = []
        for i in nums:
            idx = bisect.bisect_left(lis, i)
            if idx == len(lis):
                lis.append(i)
            else:
                lis[idx] = i
        return len(lis) + 1 >= len(nums)

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        lis = []
        for i in nums:
            idx = bisect.bisect_left(lis, i)
            if idx == len(lis):
                lis.append(i)
            else:
                lis[idx] = i
        return len(lis) + 1 >= len(nums)

Iterating over numbers take O(N) time, and the bisect_left takes O(LogN) to find the insertion index in a sorted list. The overall time complexity is O(NLogN).

–EOF (The Ultimate Computing & Technology Blog) —