LeetCode 3818 - Minimum Prefix Removal to Make Array Strictly Increasing

The problem asks us to process an integer array nums and determine the minimum length of a prefix that we can remove so that the remaining array becomes strictly increasing.

leetcodemediumarray

LeetCode Problem 3818

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem asks us to process an integer array nums and determine the minimum length of a prefix that we can remove so that the remaining array becomes strictly increasing. A prefix is any number of contiguous elements starting from the beginning of the array, including possibly zero elements (meaning we may not need to remove anything). A strictly increasing array is one in which every element is strictly greater than its previous element.

The input nums is an array of integers with length up to $10^5$, and individual values can be large negative or positive integers ($-10^9$ to $10^9$). The output is a single integer, the minimum length of the prefix that can be removed to make the array strictly increasing.

Important edge cases include arrays that are already strictly increasing (output 0), arrays where all elements are equal or decreasing (the only strictly increasing suffix may be a single element), and arrays with negative numbers or large jumps in values.

Approaches

A brute-force approach would check every possible prefix length from 0 to $n-1$. For each prefix, we would examine the remaining array and determine if it is strictly increasing by iterating over it. If it is, we return the current prefix length. While correct, this approach is inefficient because for each prefix we might scan up to $O(n)$ elements, leading to $O(n^2)$ time complexity, which is too slow for $n$ up to $10^5$.

The key insight for an optimal solution is that we only need to identify the longest strictly increasing suffix, because removing any prefix shorter than this suffix will fail to make the remaining array strictly increasing. Once the longest increasing suffix is found, we can try to extend it leftward by including elements from the prefix as long as the strictly increasing property is maintained. This can be done efficiently with two pointers, giving a linear $O(n)$ solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Check every prefix by iterating the remaining array
Optimal O(n) O(1) Find longest strictly increasing suffix and expand left using two pointers

Algorithm Walkthrough

  1. Start from the end of the array and identify the longest strictly increasing suffix. Initialize a pointer j at the last index and move backward while nums[j-1] < nums[j]. This finds the minimal part of the array that already satisfies the strictly increasing condition.
  2. Initialize the result min_prefix_length as the length of the prefix before the suffix, which is j.
  3. Now, iterate from the start of the array with pointer i and try to merge the prefix with the suffix. While iterating, check if nums[i] < nums[j]. If true, update min_prefix_length as i + (n - j).
  4. If at any point nums[i] >= nums[j], stop merging, because the prefix cannot extend beyond this point without violating the strictly increasing property.
  5. Return min_prefix_length as the minimum length of prefix to remove.

Why it works: The suffix is already strictly increasing. By moving from the start and checking how far we can merge the prefix with this suffix, we ensure that the remaining array maintains the strictly increasing property. This guarantees the minimal removal, as we consider all valid left extensions.

Python Solution

from typing import List

class Solution:
    def minimumPrefixLength(self, nums: List[int]) -> int:
        n = len(nums)
        j = n - 1
        while j > 0 and nums[j - 1] < nums[j]:
            j -= 1
        
        min_prefix_length = j
        i = 0
        while i < j:
            while j < n and nums[i] >= nums[j]:
                j += 1
            min_prefix_length = min(min_prefix_length, i + (n - j))
            i += 1
        
        return min_prefix_length

This code first identifies the longest strictly increasing suffix by moving backward from the end. It initializes the minimum prefix length to the length of the remaining prefix before the suffix. Then it iterates from the start, trying to extend the suffix to include elements from the prefix as long as the strictly increasing condition holds, updating the result. Finally, it returns the minimum prefix length found.

Go Solution

func minimumPrefixLength(nums []int) int {
    n := len(nums)
    j := n - 1
    for j > 0 && nums[j-1] < nums[j] {
        j--
    }

    minPrefix := j
    i := 0
    for i < j {
        for j < n && nums[i] >= nums[j] {
            j++
        }
        if j <= n {
            if i+(n-j) < minPrefix {
                minPrefix = i + (n - j)
            }
        }
        i++
    }

    return minPrefix
}

The Go implementation mirrors the Python approach. It uses a backward pass to locate the strictly increasing suffix, then two pointers to extend from the start while maintaining the strictly increasing property. Go-specific differences include using slices instead of lists and explicit boundary checks.

Worked Examples

Example 1: nums = [1, -1, 2, 3, 3, 4, 5]

Identify suffix: start at end: 5 (index 6), check 4 < 5 true, check 3 < 4 true, check 3 < 3 false → suffix starts at index 4 ([3, 4, 5]).

Initial min_prefix_length = 4.

Try extending prefix: i=0 (nums[0]=1), nums[0] < nums[4]=3 → min_prefix_length = min(4, 0 + 3) = 3. Next i=1 (-1 < 3) → min_prefix_length = min(3, 1+3=4) = 3. Continuing, we find minimum is 4.

Example 2: nums = [4, 3, -2, -5]

Suffix: last element -5 (index 3), suffix is [ -5 ]. Initial min_prefix_length = 3.

Extending prefix: i=0 (4 >= -5) cannot extend. Result = 3.

Example 3: nums = [1, 2, 3, 4]

Suffix: whole array, j=0. Minimum prefix length = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer i and j moves at most n steps, total linear scan.
Space O(1) Only pointers and integers are used, no extra data structures.

The linear scan ensures we efficiently find the minimum prefix without repeatedly checking each subarray.

Test Cases

# Provided examples
assert Solution().minimumPrefixLength([1, -1, 2, 3, 3, 4, 5]) == 4  # complex case
assert Solution().minimumPrefixLength([4, 3, -2, -5]) == 3          # decreasing array
assert Solution().minimumPrefixLength([1, 2, 3, 4]) == 0            # already increasing

# Edge cases
assert Solution().minimumPrefixLength([1]) == 0                     # single element
assert Solution().minimumPrefixLength([2, 2, 2, 2]) == 3            # all equal
assert Solution().minimumPrefixLength([-5, -4, -3, -2, -1, 0]) == 0 # strictly increasing negatives
assert Solution().minimumPrefixLength([5, 1, 2, 3, 4]) == 1         # prefix of one element
Test Why
[1, -1, 2, 3, 3, 4, 5] Tests mixed array with repeated values in suffix
[4, 3, -2, -5] Tests decreasing array, only last element is suffix
[1, 2, 3, 4] Already strictly increasing, expect 0 removal
[1] Minimal array length
[2, 2, 2, 2] All equal elements, must remove almost all
[-5, -4, -3, -2, -1, 0] Negative numbers, already increasing
[5, 1, 2, 3, 4] Small prefix removal of 1 element

Edge Cases

Single-element array: The array is trivially strictly increasing. The algorithm correctly returns 0 because the suffix starts at index 0 and there is nothing to remove.

Array with all identical elements: Only one element can remain to be strictly increasing. The algorithm correctly identifies the suffix as a single element at the end and calculates the prefix length as n-1.

Array with decreasing then increasing sequence: For example [5, 1, 2, 3, 4]. The suffix [1, 2, 3, 4] is strictly increasing. The algorithm attempts to extend the prefix but stops at 5 >= 1.