1909. Remove One Element to Make the Array Strictly Increasing


Problem Description

Given an array nums of integers, you need to determine if there is one element which can be removed to make the array strictly increasing. An array is strictly increasing if each element is greater than the previous one (nums[i] > nums[i - 1] for all i from 1 to nums.length - 1). The goal is to return true if the array can be made strictly increasing by removing exactly one element; otherwise, return false. It's also important to note that if the array is already strictly increasing without any removals, the answer should be true.

Intuition

The solution approach involves two key observations:

  1. If we encounter a pair of elements where the current element is not greater than its predecessor (nums[i] <= nums[i-1]), it presents a potential violation of the strictly increasing condition.
  2. To resolve this violation, we have two choices: either remove the current element (nums[i]) or the previous element (nums[i-1]). After making the removal, we should check if the rest of the array is strictly increasing.

The function check(nums, i) takes care of evaluating whether the array nums becomes strictly increasing if the element at index i is removed. It iterates through the array and skips over the index i. As it iterates, it maintains a prev value that stores the last valid number in the sequence. If prev becomes greater than or equal to the current number in the sequence at any point, that means the sequence is not strictly increasing, so it returns false. If it finishes the loop without finding such a scenario, it means the sequence is strictly increasing, and it returns true.

With these observations in hand, the main portion of the code starts checking elements from the beginning of the array. When it finds a violation where nums[i - 1] >= nums[i], it knows it's time to check the two possibilities: removing nums[i - 1] or nums[i]. It calls the check function for these two indices and returns true if either of these checks returns true, reflecting that the array could indeed be made strictly increasing by removing one of those elements.

Solution Approach

The Python code provided defines a Solution class with a method canBeIncreasing, which takes an integer list nums as input and returns a boolean indicating whether the array can become strictly increasing by removing exactly one element.

Here's a step-by-step walkthrough of the implementation:

  1. A helper function check(nums, i) is defined, which takes the array nums and an index i. This function is responsible for checking if the array can be strictly increasing by ignoring the element at index i. To do that:

    • It initializes a variable prev to -inf (negative infinity) to act as the comparator for the first element (since any integer will be greater than -inf).
    • It then iterates over all the elements in nums and skips the element at the index i. For each element num, it checks if prev is greater than or equal to num. If this condition is true at any point, it means removing the element at index i does not make the array strictly increasing, so it returns false.
    • If it completes the loop without finding any such violations, the function returns true, indicating that ignoring the element at index i results in a strictly increasing array.
  2. Within the canBeIncreasing method, a loop commences from the second element (i starts at 1) and compares each element with its predecessor.

    • As long as the elements are in strictly increasing order (nums[i - 1] < nums[i]), the loop continues.
    • When a non-increasing pair is found, the code checks two cases by invoking the check function: one where nums[i - 1] is ignored (by passing i - 1) and one where nums[i] is ignored (by passing i).
  3. The result of the method is the logical OR between these two checks:

    • check(nums, i - 1) confirms if the sequence is strictly increasing by ignoring the pre-violation element.
    • check(nums, i) confirms if the sequence is strictly increasing by ignoring the post-violation element.
    • If either check returns true, the whole method canBeIncreasing returns true, indicating the given array can be made strictly increasing by removing one element. If both checks return false, the method returns false.

In terms of algorithms and patterns, this approach employs a greedy strategy, testing if the removal of just one element at the point of violation can make the entire array strictly increasing. No advanced data structures are used, just elementary array and control flow manipulation.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's take an example array nums = [1, 3, 2, 4] to illustrate the solution approach.

  1. We start by iterating through the array from the second element. We compare each element with the one before it.

  2. In the first iteration, we have nums[0] = 1 and nums[1] = 3. Since 1 < 3, the array is strictly increasing so far, and no action is needed.

  3. In the second iteration, we see nums[1] = 3 and nums[2] = 2. 3 is not less than 2, which violates our strictly increasing condition. This is our potential problem area.

  4. We now have two scenarios to check:

    • Remove the previous element and check if the new array (ignoring nums[1]) is strictly increasing ([1, 2, 4]).
    • Remove the current element and check if the new array (ignoring nums[2]) is strictly increasing ([1, 3, 4]).
  5. We call our helper function check(nums, i) for both scenarios:

    • check(nums, 1) would ignore nums[1] = 3, resulting in [1, 2, 4]. The sequence is strictly increasing, so this returns true.
    • check(nums, 2) would ignore nums[2] = 2, resulting in [1, 3, 4]. This sequence is also strictly increasing, so this would also return true.
  6. Since removing nums[1] (which is 3) results in a strictly increasing array, we don't need to check further. We can return true.

The implementation would look something like this in Python:

1class Solution:
2    def canBeIncreasing(self, nums):
3        def check(nums, i):
4            prev = float('-inf')
5            for k, num in enumerate(nums):
6                if k == i:
7                    continue
8                if prev >= num:
9                    return False
10                prev = num
11            return True
12
13        for i in range(1, len(nums)):
14            if nums[i-1] >= nums[i]:
15                return check(nums, i-1) or check(nums, i)
16      
17        return True
18
19# Example Usage
20sol = Solution()
21result = sol.canBeIncreasing([1, 3, 2, 4])
22print(result)  # Output should be True

In this example, our array nums = [1, 3, 2, 4] can indeed be made strictly increasing by removing the element 3 (at index 1), and our function would correctly return true.

Python Solution

1from typing import List
2
3class Solution:
4    def canBeIncreasing(self, nums: List[int]) -> bool:
5        # Helper function to check if the sequence is strictly increasing
6        # by skipping the element at index skip_index
7        def is_strictly_increasing(nums, skip_index):
8            prev_value = float('-inf')
9            for index, num in enumerate(nums):
10                # Skip the element at skip_index
11                if index == skip_index:
12                    continue
13                # If current element is not greater than the previous one, sequence is not increasing
14                if prev_value >= nums[index]:
15                    return False
16                prev_value = nums[index]
17            return True
18
19        # Initialize variables
20        current_index = 1
21        sequence_length = len(nums)
22      
23        # Find the first instance where the sequence is not increasing
24        while current_index < sequence_length and nums[current_index - 1] < nums[current_index]:
25            current_index += 1
26
27        # Check if the sequence can be made strictly increasing
28        # by removing the element at the index just before or at the point of discrepancy
29        return (is_strictly_increasing(nums, current_index - 1) or 
30                is_strictly_increasing(nums, current_index))
31
32# Example usage:
33# sol = Solution()
34# result = sol.canBeIncreasing([1, 2, 10, 5, 7])
35# print(result)  # Output: True, since removing 10 makes the sequence strictly increasing
36

Java Solution

1class Solution {
2    // Function to check if removing one element from the array can make it strictly increasing
3    public boolean canBeIncreasing(int[] nums) {
4        int currentIndex = 1;
5        int arrayLength = nums.length;
6        // Iterate over the array to find the breaking point where the array ceases to be strictly increasing
7        for (; currentIndex < arrayLength && nums[currentIndex - 1] < nums[currentIndex]; ++currentIndex);
8
9        // Check if it's possible to make the array strictly increasing by removing the element at 
10        // either the breaking point or the one before it
11        return isStrictlyIncreasingAfterRemovingIndex(nums, currentIndex - 1) || 
12               isStrictlyIncreasingAfterRemovingIndex(nums, currentIndex);
13    }
14
15    // Helper function to check if the array is strictly increasing after removing the element at index i
16    private boolean isStrictlyIncreasingAfterRemovingIndex(int[] nums, int indexToRemove) {
17        int prevValue = Integer.MIN_VALUE;
18        // Iterate over the array
19        for (int j = 0; j < nums.length; ++j) {
20            // Skip the element at the removal index
21            if (indexToRemove == j) {
22                continue;
23            }
24            // Check if the previous value is not less than the current, array can't be made strictly increasing
25            if (prevValue >= nums[j]) {
26                return false;
27            }
28            // Update previous value
29            prevValue = nums[j];
30        }
31        return true; // Array can be made strictly increasing after removing the element at indexToRemove
32    }
33}
34

C++ Solution

1class Solution {
2public:
3    // Function to check if it's possible to have a strictly increasing sequence
4    // by removing at most one element from the given vector.
5    bool canBeIncreasing(vector<int>& nums) {
6        int i = 1; // Starting the iteration from the second element
7        int n = nums.size(); // Storing the size of nums
8        // Find the first instance where the current element is not greater than the previous one.
9        for (; i < n && nums[i - 1] < nums[i]; ++i)
10            ; // The loop condition itself ensures increment, empty body
11
12        // Check the sequences by excluding the element at (i - 1) or i
13        return isIncreasingSequence(nums, i - 1) || isIncreasingSequence(nums, i);
14    }
15
16private:
17    // Helper function to determine whether the sequence is strictly increasing
18    // if we virtually remove the element at index 'exclusionIndex'.
19    bool isIncreasingSequence(vector<int>& nums, int exclusionIndex) {
20        int prevVal = INT_MIN; // Use INT_MIN to handle the smallest integer case
21        for (int currIndex = 0; currIndex < nums.size(); ++currIndex) {
22            if (currIndex == exclusionIndex) continue; // Skip the exclusion index
23
24            // If the current element is not greater than the previous one, it's not strictly increasing.
25            if (prevVal >= nums[currIndex]) return false;
26            prevVal = nums[currIndex]; // Update the previous value
27        }
28        return true; // If all checks passed, the sequence is strictly increasing
29    }
30};
31

Typescript Solution

1function canBeIncreasing(nums: number[]): boolean {
2    // Helper function to check if the array can be strictly increasing
3    // by potentially removing the element at position p
4    const isStrictlyIncreasingWithRemoval = (positionToRemove: number): boolean => {
5        let previousValue: number | undefined = undefined; // Holds the last valid value
6        for (let index = 0; index < nums.length; index++) {
7            // Skips the element at the removal position
8            if (positionToRemove !== index) {
9                // Checks if the current element breaks the strictly increasing order
10                if (previousValue !== undefined && previousValue >= nums[index]) {
11                    return false;
12                }
13                // Updates the previous value to the current one
14                previousValue = nums[index];
15            }
16        }
17        return true;
18    };
19
20    // Iterate through the input array to find the break in the strictly increasing sequence
21    for (let i = 0; i < nums.length; i++) {
22        // Check if the current element is not less than the previous one
23        if (i > 0 && nums[i - 1] >= nums[i]) {
24            // Return true if removing either the previous element or the current one
25            // can make the sequence strictly increasing
26            return isStrictlyIncreasingWithRemoval(i - 1) || isStrictlyIncreasingWithRemoval(i);
27        }
28    }
29
30    // If no breaks are found, the sequence is already strictly increasing
31    return true;
32}
33

Time and Space Complexity

The given code aims to determine if a strictly increasing sequence can be made by removing at most one element from the array nums.

Time Complexity

The check() function is called at most twice, regardless of the input size. It iterates through the nums array up to n times, where n is the length of the array, potentially skipping one element. If we consider the length of the array as n, the time complexity of the check() is O(n) because it involves a single loop through all the elements.

Since check() is called at most twice, the time complexity of the entire canBeIncreasing() method is O(n) + O(n) which simplifies to O(n).

Space Complexity

The space complexity refers to the amount of extra space or temporary storage that an algorithm uses.

In the case of the provided Python code:

  • The check() function uses a constant amount of additional space (only the prev variable is used).
  • No additional arrays or data structures are created that depend on the input size n.

Therefore, the space complexity of the code is O(1), indicating constant space usage independent of the input size.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫