algoadvance

Leetcode 1909. Remove One Element to Make the Array Strictly Increasing

Problem Statement

You are given a 0-indexed integer array nums. You need to determine if it is possible to remove exactly one element from the array such that the resulting array is strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for every index i where 0 <= i < nums.length - 1.

Return true if it is possible to remove one element from the array to make it strictly increasing, otherwise return false.

Example:

Input: nums = [1,2,10,5,7]
Output: true

Clarifying Questions

  1. Input Constraints:
    • What is the minimum and maximum length of the input array?
    • Are the elements of the input array bounded within certain limits?
  2. Edge Cases:
    • What should be returned if the array is already strictly increasing?
    • How should the case where there’s only one element in the array be handled?

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int n = nums.size();
        
        // Track the number of violations
        int count = 0;
        
        for (int i = 1; i < n; ++i) {
            if (nums[i] <= nums[i-1]) {
                count++;
                if (count > 1) return false;
                // Check if removing nums[i-1] or nums[i] could solve the problem
                if (i > 1 && nums[i] <= nums[i-2] && i < n-1 && nums[i+1] <= nums[i-1]) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

Strategy

  1. Initial Check:
    • Traverse the array to count how many times nums[i-1] >= nums[i].
    • If this count exceeds 1, return false immediately, as removing one element won’t be sufficient.
  2. Decision Making:
    • For each detected non-increasing pair (nums[i-1], nums[i]):
      • Check if removing nums[i-1] or nums[i] could potentially fix the array to make it strictly increasing.
      • Use conditions like nums[i] <= nums[i-2] and nums[i+1] <= nums[i-1] to see if removing one of the elements would lead to a potential fix.

Time Complexity

This ensures the algorithm is efficient even for larger inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI