algoadvance

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

Problem Statement

You are given a 0-indexed integer array nums of length n. You need to determine whether it is possible to remove exactly one element from the array to make the rest of the array strictly increasing.

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

Clarifying Questions

  1. What should be returned if the array is already strictly increasing?
    • We return true because we can simply remove an element that would still preserve the strict increasing property.
  2. What if the array has less than or equal to two elements?
    • For length <= 2, we can always remove one element to get a strictly increasing array.

Strategy

  1. Iterate through the array and track instances where nums[i] >= nums[i+1].
  2. If more than one such instance is found, return false because removing one element will not be enough to make the sequence strictly increasing.
  3. If exactly one such instance is found, test two sub-cases:
    • Remove the larger element at the instance.
    • Remove the smaller element next to the instance.
  4. Check if either of these sub-cases result in a strictly increasing array.

Time Complexity

The solution involves a single or at most double pass through the array.

Code

public class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int count = 0, n = nums.length;
        int idx = -1;

        // Detect the number of points where the sequence is not increasing
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] >= nums[i + 1]) {
                count++;
                idx = i;
                if (count > 1) return false;
            }
        }

        // If there are no such points or only one, check the possible cases
        if (count == 0) return true;
        if (idx == 0 || idx == n - 2) return true;

        if ((idx > 0 && nums[idx - 1] < nums[idx + 1]) ||
            (idx < n - 2 && nums[idx] < nums[idx + 2])) {
            return true;
        }

        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test with sample inputs
        System.out.println(sol.canBeIncreasing(new int[]{1, 2, 10, 5, 7})); // true
        System.out.println(sol.canBeIncreasing(new int[]{2, 3, 1, 2}));    // false
        System.out.println(sol.canBeIncreasing(new int[]{1, 1, 1}));        // false
        System.out.println(sol.canBeIncreasing(new int[]{1, 2, 3}));        // true
    }
}

The provided solution should adequately handle the problem and edge cases like smaller arrays or typical elements that maintain a stable comparison for strictly increasing subarray creation.

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