Problem Description

• LeetCode 1909: Remove One Element to Make the Array Strictly Increasing

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 i that satisfies 1 <= i < nums.length.

Examples:

• Input: nums = [1,2,10,5,7] → Output: true (remove 10)
• Input: nums = [2,3,1,2] → Output: false (need to remove more than one element)
• Input: nums = [1,1,1] → Output: false (equal elements violate strict increasing)

Algorithm Walkthrough

Main Idea

The algorithm works by counting violations first, then checking if the violations can be fixed by removing exactly one element.

Core Strategy:

1. Count all positions where nums[i-1] >= nums[i] (violations of strict increasing property)
2. Analyze the violation count and determine if removal of one element can fix it

Step-by-Step Process

Step 1: Violation Detection

Scan the array and count violations where adjacent elements are not strictly increasing.

Step 2: Decision Based on Violation Count

Case A: count == 0

• Array is already strictly increasing
• Return true

Case B: count > 1

• Multiple violations require removing more than one element
• Return false

Case C: count == 1 (Single violation at position p) Three subcases to consider:

Case 1: Delete nums[p] (current violating element)

• Condition: nums[p-1] < nums[p+1] (and indices are in bounds)
• Example: [1,2,3,9,6,10] where 6 at index 4 violates policy
  • Violation: nums[3]=9 >= nums[4]=6 at p=4
  • Check: nums[3] < nums[5] → 9 < 10 ✓
  • Solution: Remove nums[4]=6 → [1,2,3,9,10]

Case 2: Delete nums[p-1] (previous element causing violation)

• Condition: nums[p-2] < nums[p] (and indices are in bounds)
• Example: [1,2,3,13,10,11] where 10 at index 4 violates policy
  • Violation: nums[3]=13 >= nums[4]=10 at p=4
  • Check: nums[2] < nums[4] → 3 < 10 ✓
  • Solution: Remove nums[3]=13 → [1,2,3,10,11]

Case 3: Edge violations (p=1 or p=n-1)

• Condition: Violation at beginning or end of array
• No further checks needed - can always remove first or last element
• Example 1: [9,1,2,3] where 1 at index 1 violates policy
  • Violation: nums[0]=9 >= nums[1]=1 at p=1
  • Solution: Remove nums[0]=9 → [1,2,3]
• Example 2: [1,2,3,0] where 0 at index 3 violates policy
  • Violation: nums[2]=3 >= nums[3]=0 at p=3 (which equals n-1)
  • Solution: Remove nums[3]=0 → [1,2,3]

Full Solution (Java)

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        // Count violations and track position
        int count = 0;
        int n = nums.length;
        int p = 0;  // Position of violation

        // Step 1: Find all violations
        for (int i = 1; i < n; i++) {
            if (nums[i-1] >= nums[i]) {
                count++;
                p = i;  // Store position of violation
            }
        }

        // Step 2: Handle no violations
        if (count == 0) {
            return true;  // Already strictly increasing
        }

        // Step 3: Handle multiple violations
        if (count > 1) {
            return false;  // Can't fix with one removal
        } 

        // Step 4: Handle single violation (count == 1)
        else {
            // Case 3: Edge violations - always fixable
            if (p == 1 || p == n-1) {
                return true;
            } 
            // Case 1 & 2: Middle violations - check both removal options
            else if ((p > 1) && (p + 1 <= n-1) && (nums[p-1] < nums[p+1]) ||  // Case 1: Remove nums[p]
                     (p >= 2) && (p < n-1) && (nums[p-2] < nums[p])) {        // Case 2: Remove nums[p-1]
                return true;
            } 
            else {
                return false;  // Neither removal option works
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array to detect violations: O(n)
• Constant time validation of removal options: O(1)
• Overall: O(n) - linear time complexity

Space Complexity: O(1)

• Fixed variables: Only uses count, p, and n variables
• No extra arrays: Processes input array in-place
• Overall: O(1) - constant extra space

Optimality

• Lower bound: Must examine each adjacent pair at least once → Ω(n)
• This solution: Exactly one pass with minimal operations → O(n)
• Space efficient: Constant memory usage regardless of input size

This makes the violation counting approach both time-optimal and space-optimal for solving the "Remove One Element" problem.