We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove One Element to Make the Array Strictly Increasing

Number: 2020

Difficulty: Easy

Paid? No

Companies: Amazon, Google, eBay

Problem Description

Given a 0-indexed integer array nums, determine if it is possible to obtain a strictly increasing sequence by removing exactly one element from nums. An array is strictly increasing if every element is greater than its previous element. If the array is already strictly increasing, the result should be true.

Key Insights

  • Only one removal is allowed.
  • Traverse the array and identify where the strictly increasing property fails (i.e., nums[i] <= nums[i-1]).
  • Only one such violation is permitted; more than one violation leads to a false outcome.
  • When a violation is found, consider whether removing either the previous element or the current element will preserve the strictly increasing order.
  • Special boundary cases (such as the beginning of the array) can be handled with conditional checks.

Space and Time Complexity

Time Complexity: O(n) - iterate through the array once.
Space Complexity: O(1) - only a constant amount of extra space is used.

Solution

The solution involves a single pass through the array while maintaining a count of removals needed. Start scanning from index 1 to compare each element with its predecessor. If a violation (i.e., nums[i] <= nums[i-1]) occurs, increment a removal counter. If the counter exceeds one, return false immediately.

For each violation, check if removing the previous element (if possible) or the current element would fix the violation. Specifically, if i < 2 or nums[i] > nums[i-2], then it is valid to remove nums[i-1]. Otherwise, update the current element as if you removed it (conceptually), so that nums[i] takes the value of the previous element or remains as is if it satisfies the order relative to nums[i-2].

This method ensures that by simulating a removal, the array can be made strictly increasing if at most one such removal is required.

Code Solutions

# Python solution for Remove One Element to Make the Array Strictly Increasing

def can_be_increasing(nums):
    removal_count = 0  # Count how many removals are needed
    for i in range(1, len(nums)):
        # Check for the violation of strictly increasing order
        if nums[i] <= nums[i - 1]:
            removal_count += 1
            if removal_count > 1:
                return False
            # Check if we can remove nums[i-1] safely
            if i == 1 or nums[i] > nums[i - 2]:
                continue
            else:
                # Otherwise, simulate the removal of nums[i]
                nums[i] = nums[i - 1]
    return True

# Example usage:
print(can_be_increasing([1, 2, 10, 5, 7]))  # Expected output: True
print(can_be_increasing([2, 3, 1, 2]))       # Expected output: False
← Back to All Questions