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 <= 10001 <= nums[i] <= 1000
Solutions
Solution 1: Traversal
We can traverse the array to find the first position i where nums[i] < nums[i+1] is not satisfied. Then, we check if the array is strictly increasing after removing either i or i+1. If it is, we return true; otherwise, we return false.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustC#
class Solution:
def canBeIncreasing(self, nums: List[int]) -> bool:
def check(k: int) -> bool:
pre = -inf
for i, x in enumerate(nums):
if i == k:
continue
if pre >= x:
return False
pre = x
return True
i = 0
while i + 1 < len(nums) and nums[i] < nums[i + 1]:
i += 1
return check(i) or check(i + 1)(code-box)
class Solution {
public boolean canBeIncreasing(int[] nums) {
int i = 0;
while (i + 1 < nums.length && nums[i] < nums[i + 1]) {
++i;
}
return check(nums, i) || check(nums, i + 1);
}
private boolean check(int[] nums, int k) {
int pre = 0;
for (int i = 0; i < nums.length; ++i) {
if (i == k) {
continue;
}
if (pre >= nums[i]) {
return false;
}
pre = nums[i];
}
return true;
}
}(code-box)
class Solution {
public:
bool canBeIncreasing(vector<int>& nums) {
int n = nums.size();
auto check = [&](int k) -> bool {
int pre = 0;
for (int i = 0; i < n; ++i) {
if (i == k) {
continue;
}
if (pre >= nums[i]) {
return false;
}
pre = nums[i];
}
return true;
};
int i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) {
++i;
}
return check(i) || check(i + 1);
}
};(code-box)
func canBeIncreasing(nums []int) bool {
check := func(k int) bool {
pre := 0
for i, x := range nums {
if i == k {
continue
}
if pre >= x {
return false
}
pre = x
}
return true
}
i := 0
for i+1 < len(nums) && nums[i] < nums[i+1] {
i++
}
return check(i) || check(i+1)
}(code-box)
function canBeIncreasing(nums: number[]): boolean {
const n = nums.length;
const check = (k: number): boolean => {
let pre = 0;
for (let i = 0; i < n; ++i) {
if (i === k) {
continue;
}
if (pre >= nums[i]) {
return false;
}
pre = nums[i];
}
return true;
};
let i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) {
++i;
}
return check(i) || check(i + 1);
}(code-box)
impl Solution {
pub fn can_be_increasing(nums: Vec<i32>) -> bool {
let check = |k: usize| -> bool {
let mut pre = 0;
for (i, &x) in nums.iter().enumerate() {
if i == k {
continue;
}
if pre >= x {
return false;
}
pre = x;
}
true
};
let mut i = 0;
while i + 1 < nums.len() && nums[i] < nums[i + 1] {
i += 1;
}
check(i) || check(i + 1)
}
}(code-box)
public class Solution {
public bool CanBeIncreasing(int[] nums) {
int n = nums.Length;
bool check(int k) {
int pre = 0;
for (int i = 0; i < n; ++i) {
if (i == k) {
continue;
}
if (pre >= nums[i]) {
return false;
}
pre = nums[i];
}
return true;
}
int i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) {
++i;
}
return check(i) || check(i + 1);
}
}(code-box)
