{x}
blog image

Remove One Element to Make the Array Strictly Increasing

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

Solution Explanation:

The problem asks whether removing exactly one element from the input array nums can make it strictly increasing. A strictly increasing array means that each element is greater than the previous one.

The solution employs a straightforward approach:

  1. Find the First Violation: The code iterates through the array to locate the first index i where the strictly increasing condition nums[i] < nums[i+1] is violated. This means nums[i] >= nums[i+1].

  2. Check Removal Options: Once the violation is found, the solution checks two possibilities:

    • Removing the element at index i.
    • Removing the element at index i+1.

  3. check Function: A helper function check(k) is used to determine if the array is strictly increasing after removing the element at index k. It iterates through the modified array, comparing each element to the previous one. If it finds a violation (non-strictly increasing order), it returns false. Otherwise, it returns true.

  4. Return Value: The main function returns true if either removing the element at i or i+1 results in a strictly increasing array. Otherwise, it returns false.

Time Complexity Analysis:

  • The initial loop to find the first violation takes O(n) time, where n is the length of the input array.
  • The check function is called at most twice, each call taking O(n) time in the worst case.
  • Therefore, the overall time complexity is O(n).

Space Complexity Analysis:

The solution uses a constant amount of extra space (for variables like i, pre, and k). Therefore, the space complexity is O(1).

Code in Different Languages:

The provided code snippets demonstrate the solution in multiple languages (Python, Java, C++, Go, TypeScript, Rust, C#). All versions follow the same algorithm described above. The differences are mainly in syntax and library usage specific to each language. For example, -inf (negative infinity) in Python is handled differently in other languages (using Integer.MIN_VALUE in Java, numeric_limits<int>::min() in C++, etc.). The essential logic, however, remains consistent.