1909. Remove One Element to Make the Array Strictly Increasing

Description

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

Solutions

Solution 1

Python Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        def check(nums, i):
            prev = -inf
            for j, num in enumerate(nums):
                if i == j:
                    continue
                if prev >= nums[j]:
                    return False
                prev = nums[j]
            return True

        i, n = 1, len(nums)
        while i < n and nums[i - 1] < nums[i]:
            i += 1
        return check(nums, i - 1) or check(nums, i)

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int i = 1, n = nums.length;
        for (; i < n && nums[i - 1] < nums[i]; ++i)
            ;
        return check(nums, i - 1) || check(nums, i);
    }

    private boolean check(int[] nums, int i) {
        int prev = Integer.MIN_VALUE;
        for (int j = 0; j < nums.length; ++j) {
            if (i == j) {
                continue;
            }
            if (prev >= nums[j]) {
                return false;
            }
            prev = nums[j];
        }
        return true;
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int i = 1, n = nums.size();
        for (; i < n && nums[i - 1] < nums[i]; ++i)
            ;
        return check(nums, i - 1) || check(nums, i);
    }

    bool check(vector<int>& nums, int i) {
        int prev = 0;
        for (int j = 0; j < nums.size(); ++j) {
            if (i == j) continue;
            if (prev >= nums[j]) return false;
            prev = nums[j];
        }
        return true;
    }
};

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func canBeIncreasing(nums []int) bool {
	i, n := 1, len(nums)
	for ; i < n && nums[i-1] < nums[i]; i++ {

	}
	return check(nums, i-1) || check(nums, i)
}

func check(nums []int, i int) bool {
	prev := 0
	for j := 0; j < len(nums); j++ {
		if i == j {
			continue
		}
		if prev >= nums[j] {
			return false
		}
		prev = nums[j]
	}
	return true
}

TypeScript Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function canBeIncreasing(nums: number[]): boolean {
    const check = (p: number) => {
        let prev = undefined;
        for (let j = 0; j < nums.length; j++) {
            if (p != j) {
                if (prev !== undefined && prev >= nums[j]) {
                    return false;
                }
                prev = nums[j];
            }
        }
        return true;
    };
    for (let i = 0; i < nums.length; i++) {
        if (nums[i - 1] >= nums[i]) {
            return check(i - 1) || check(i);
        }
    }
    return true;
}

Rust Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
impl Solution {
    pub fn can_be_increasing(nums: Vec<i32>) -> bool {
        let check = |p: usize| -> bool {
            let mut prev = None;
            for j in 0..nums.len() {
                if p != j {
                    if let Some(value) = prev {
                        if value >= nums[j] {
                            return false;
                        }
                    }
                    prev = Some(nums[j]);
                }
            }
            true
        };
        for i in 1..nums.len() {
            if nums[i - 1] >= nums[i] {
                return check(i - 1) || check(i);
            }
        }
        true
    }
}