Remove One Element to Make the Array Strictly Increasing

Easy

#1742Time: O(N^2), where N is the number of elements in `nums`. The outer loop runs N times. Inside this loop, creating the temporary list takes O(N) time, and checking if it's increasing takes another O(N) time, leading to a total of N * O(N) = O(N^2).Space: O(N), where N is the number of elements in `nums`. This space is used to store the temporary list in each iteration.1 company

Data structures

Array

Companies

eBay

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through each element of the array, and for each element, we hypothetically remove it and then check if the remaining part of the array is strictly increasing.

Algorithm

Loop through each index i from 0 to nums.length - 1.
In each iteration, i represents the index of the element to be removed.
Create a new list, tempList.
Loop through each index j from 0 to nums.length - 1.
If i != j, add nums[j] to tempList.
Check if tempList is strictly increasing. To do this, loop from k = 1 to tempList.size() - 1 and check if tempList.get(k) <= tempList.get(k-1). If this condition is met, the list is not strictly increasing.
If tempList is found to be strictly increasing, return true.
If the outer loop finishes without finding a valid removal, return false.

Walkthrough

We can use a loop that iterates from i = 0 to n-1, where n is the length of the array. In each iteration, i represents the index of the element to be removed.

Inside the loop, we construct a new temporary array (or list) that contains all elements of the original array except the one at index i. After constructing the temporary array, we check if it is strictly increasing. This can be done with another loop that iterates through the temporary array, comparing each element with its predecessor.

If we find that a temporary array is strictly increasing, it means we've found a valid removal. We can immediately return true.

If the outer loop completes without finding any such valid removal, it means it's impossible to make the array strictly increasing by removing one element. In this case, we return false.

This also correctly handles the case where the array is already strictly increasing. For example, if nums = [1, 2, 3], removing the last element 3 results in [1, 2], which is strictly increasing, so the function will return true.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean canBeIncreasing(int[] nums) {6        int n = nums.length;7        for (int i = 0; i < n; i++) {8            // Create a temporary list without the element at index i9            List<Integer> tempList = new ArrayList<>();10            for (int j = 0; j < n; j++) {11                if (i != j) {12                    tempList.add(nums[j]);13                }14            }15 16            // Check if the temporary list is strictly increasing17            boolean isIncreasing = true;18            for (int k = 1; k < tempList.size(); k++) {19                if (tempList.get(k) <= tempList.get(k - 1)) {20                    isIncreasing = false;21                    break;22                }23            }24 25            if (isIncreasing) {26                return true;27            }28        }29        return false;30    }31}

Complexity

Time

O(N^2), where N is the number of elements in `nums`. The outer loop runs N times. Inside this loop, creating the temporary list takes O(N) time, and checking if it's increasing takes another O(N) time, leading to a total of N * O(N) = O(N^2).

Space

O(N), where N is the number of elements in `nums`. This space is used to store the temporary list in each iteration.

Trade-offs

Pros

Simple to understand and implement.
Directly follows the logic of the problem statement.

Cons

Inefficient in terms of time complexity due to nested loops.
Requires extra space proportional to the input size to create temporary arrays.

This optimal approach avoids the O(N^2) complexity by performing a single pass through the array. The key insight is that for the condition to be met, there can be at most one "violation" (where nums[i] <= nums[i-1]). We can find this violation and check if removing either of the two conflicting elements resolves the issue locally.

Algorithm

Initialize a counter violations = 0 and an index p = -1.
Loop through the array from i = 1 to n-1.
If nums[i] <= nums[i-1], increment violations and store the current index i in p.
After the loop, check the value of violations:
- If violations == 0, the array is already strictly increasing. Return true.
- If violations > 1, more than one removal is needed. Return false.
- If violations == 1, we have a single dip at index p. We can fix this if either removing nums[p] or nums[p-1] results in a valid sequence.
  - Removing nums[p-1] is valid if p == 1 (it's the first element) or if nums[p-2] < nums[p].
  - Removing nums[p] is valid if p == n-1 (it's the last element) or if nums[p-1] < nums[p+1].
If either of the conditions for violations == 1 is met, return true. Otherwise, return false.

Walkthrough

The core idea is that if the array can be made strictly increasing by removing one element, there can be at most one index i where nums[i] <= nums[i-1]. If there are two or more such "dips", we would need to remove at least two elements, so we can immediately return false.

We iterate through the array once to find the number of violations and the index of the last violation.

If we find zero violations, the array is already strictly increasing, so we return true.
If we find more than one violation, it's impossible to fix the array by removing only one element, so we return false.
If we find exactly one violation at index p (i.e., nums[p] <= nums[p-1]), we have two potential fixes:
1. Remove nums[p-1]: The array becomes ..., nums[p-2], nums[p], .... This is a valid fix if nums[p-2] < nums[p]. We must also consider the edge case where p-1 is the first element of the array (p=1), in which case this removal is always a valid local fix.
2. Remove nums[p]: The array becomes ..., nums[p-1], nums[p+1], .... This is a valid fix if nums[p-1] < nums[p+1]. We must also consider the edge case where p is the last element of the array, in which case this removal is always a valid local fix.

If either of these two fixes works, we can return true. If the single violation cannot be fixed by either removal, we return false.

1class Solution {2    public boolean canBeIncreasing(int[] nums) {3        int violations = 0;4        int p = -1;5        int n = nums.length;6 7        for (int i = 1; i < n; i++) {8            if (nums[i] <= nums[i - 1]) {9                violations++;10                p = i;11            }12        }13 14        if (violations == 0) {15            return true;16        }17 18        if (violations > 1) {19            return false;20        }21 22        // At this point, violations == 1. The violation is at index p.23        // This means nums[p] <= nums[p-1]24 25        // Case 1: Try removing nums[p-1]. The sequence becomes ..., nums[p-2], nums[p], ...26        // This is valid if p is 1 (i.e., we remove nums[0]) or if nums[p-2] < nums[p].27        if (p == 1 || nums[p - 2] < nums[p]) {28            return true;29        }30 31        // Case 2: Try removing nums[p]. The sequence becomes ..., nums[p-1], nums[p+1], ...32        // This is valid if p is the last index or if nums[p-1] < nums[p+1].33        if (p == n - 1 || nums[p - 1] < nums[p + 1]) {34            return true;35        }36 37        return false;38    }39}

Complexity

Time

O(N), where N is the number of elements in `nums`. We perform a single pass through the array to count violations.

Space

O(1), as we only use a few variables to keep track of violations and indices, regardless of the input size.

Trade-offs

Pros

Highly efficient with linear time complexity.
Space-efficient, using only a constant amount of extra space.

Cons

The logic can be slightly more complex to reason about compared to the direct simulation.

Solutions

Solution

1public 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 ); } }

1class Solution {2public3  boolean canBeIncreasing(int[] nums) {4    int i = 1, n = nums.length;5    for (; i < n && nums[i - 1] < nums[i]; ++i)6      ;7    return check(nums, i - 1) || check(nums, i);8  }9private10  boolean check(int[] nums, int i) {11    int prev = Integer.MIN_VALUE;12    for (int j = 0; j < nums.length; ++j) {13      if (i == j) {14        continue;15      }16      if (prev >= nums[j]) {17        return false;18      }19      prev = nums[j];20    }21    return true;22  }23}

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

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem