Remove One Element to Make the Array Strictly Increasing

Easy

Asked by:

+1

9 views

Topics:

Arrays

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

Remove One Element to Make the Array Strictly Increasing

Easy

Asked by:

9 views

Topics:

Arrays

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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array nums?
Can the array contain negative numbers, zeros, or duplicate values?
If it's impossible to make the array strictly increasing by removing one element, what should I return?
By strictly increasing, do you mean each element must be strictly greater than the previous element (no equality allowed)?
If there are multiple elements that, when removed, result in a strictly increasing array, should I return true if at least one such element exists?

Brute Force Solution

Approach

The brute force strategy to check if removing one element can make the array strictly increasing involves checking every possible case. We'll go through the array, one element at a time, and temporarily take it out.

Here's how the algorithm would work step-by-step:

Start by considering the first element as the one to remove.
Imagine removing that first element from the list.
Check if the remaining list is strictly increasing (meaning each number is bigger than the one before it).
If it is, you've found a solution, and you can stop.
If not, put the first element back and try removing the second element instead.
Check if the list is now strictly increasing after removing the second element.
Keep repeating this process, removing one element at a time and checking the remaining list.
If, after checking every single element for removal, you still haven't found a strictly increasing list, then no solution exists.

Code Implementation

def can_be_increasing_brute_force(numbers):
    for index_to_remove in range(len(numbers)):
        # Create a new array excluding the element at the current index
        modified_numbers = numbers[:index_to_remove] + numbers[index_to_remove+1:]

        # Check if the modified array is strictly increasing
        is_strictly_increasing = True
        for index in range(len(modified_numbers) - 1):
            # Array is not strictly increasing
            if modified_numbers[index] >= modified_numbers[index + 1]:
                is_strictly_increasing = False
                break

        # If strictly increasing, return True
        if is_strictly_increasing:
            return True

    # No solution found after trying every possible removal
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the array of size n, considering each element for removal. For each element considered, it checks if the remaining array is strictly increasing. Checking if an array of size (n-1) is strictly increasing requires comparing each element to its predecessor, taking O(n) time. Since this check is performed n times (once for each potential removal), the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach, as described, checks every possible removal. In each check, a modified list (either explicitly or implicitly) of potentially size N-1 is created to verify the strictly increasing condition. This modified list represents the array with one element removed. Since the size of this modified list is directly proportional to the original input size N, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The goal is to quickly find if removing a single number from the list makes it strictly increasing. The efficient way to do this is to check for issues as we move through the list, dealing with them immediately if possible, rather than trying every possible removal.

Here's how the algorithm would work step-by-step:

Go through the list from beginning to end, checking if each number is bigger than the one before it.
If you find a number that is not bigger than the one before it, this is a problem area.
At this problem area, you have two choices: either remove the number before it, or remove the current number.
See if removing the number before the problem area makes the rest of the list strictly increasing.
If that doesn't work, see if removing the current number makes the rest of the list strictly increasing.
If either of those removals fixes the list, then you know removing one number is enough.
If neither of those removals fixes the list, then you know you cannot make it strictly increasing by removing just one number.

Code Implementation

def can_be_increasing(numbers) -> bool:
    number_of_violations = 0
    previous_number = float('-inf')
    violation_index = -1

    for index in range(len(numbers)):
        current_number = numbers[index]
        if current_number <= previous_number:
            number_of_violations += 1
            violation_index = index
        previous_number = current_number

    if number_of_violations == 0:
        return True

    if number_of_violations > 1:
        return False

    # Attempt to remove the number before the violating number.
    temp_numbers = numbers[:violation_index - 1] + numbers[violation_index:]
    is_increasing_after_removal_before = True
    previous_number = float('-inf')
    for index in range(len(temp_numbers)):
        current_number = temp_numbers[index]
        if current_number <= previous_number:
            is_increasing_after_removal_before = False
            break
        previous_number = current_number

    if is_increasing_after_removal_before:
        return True

    # Attempt to remove the violating number.
    temp_numbers = numbers[:violation_index] + numbers[violation_index + 1:]
    is_increasing_after_removal_current = True
    previous_number = float('-inf')
    for index in range(len(temp_numbers)):
        current_number = temp_numbers[index]
        if current_number <= previous_number:
            is_increasing_after_removal_current = False
            break
        previous_number = current_number

    #If removing current is increasing, return true
    if is_increasing_after_removal_current:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of size n at most once to identify a potential violation of the strictly increasing property. In the event of a violation, it makes at most two additional passes through portions of the array to validate if removing either the preceding or current element resolves the issue. Because these passes are either a constant number or bounded by the initial array size, the dominant factor remains the initial linear scan, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided plain English explanation describes an in-place algorithm that primarily uses a loop to iterate through the input list. No auxiliary data structures, such as temporary lists, hash maps, or sets, are created to store intermediate results. The algorithm potentially stores a constant number of variables (e.g., to track the index or number of modifications) irrespective of the input list's size N. Therefore, the algorithm's space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return true immediately since an empty array is considered strictly increasing.
Array with one element	Return true immediately since an array with one element is strictly increasing.
Array with two elements that are already strictly increasing	Return true since no removal is needed.
Array with two elements that are not strictly increasing	Return true since removing either element will make the array strictly increasing.
Array with all identical elements	Return false since removing one element will still leave duplicate elements.
Array with strictly increasing elements	Return true because no element needs to be removed.
Array where removing the first element results in a strictly increasing array	The algorithm should check this condition.
Array where removing the last element results in a strictly increasing array	The algorithm should check this condition.