Minimum Prefix Removal to Make Array Strictly Increasing - Solution & Explanation

Problem Overview: You are given an integer array and can remove any number of elements from the prefix. The goal is to remove the smallest prefix so the remaining suffix becomes strictly increasing. Formally, find the minimum k such that nums[k:] satisfies nums[i] < nums[i+1] for every valid index.

Approach 1: Brute Force Prefix Check (O(n^2) time, O(1) space)

Try every possible prefix removal. For each index k from 0 to n-1, check whether the suffix nums[k:] is strictly increasing. The check requires iterating through the remaining array and verifying nums[i] < nums[i+1]. The first valid k is the answer. This approach directly models the problem but performs repeated scans of the array, leading to O(n^2) time in the worst case. Space stays O(1) since no extra structures are required. Useful for reasoning about the problem, but inefficient for large inputs.

Approach 2: Reverse Traversal (O(n) time, O(1) space)

The key observation: if a suffix is strictly increasing, every pair of adjacent elements inside it must satisfy nums[i-1] < nums[i]. Instead of testing every prefix removal, scan the array from the right and locate the longest strictly increasing suffix. Start at the last index and move left while the increasing condition holds. The moment you encounter a violation (nums[i-1] >= nums[i]), the suffix beginning at i is the longest valid strictly increasing suffix. Removing the prefix of length i makes the remaining array strictly increasing.

This works because any earlier start would include the violating pair, breaking the strictly increasing property. The scan touches each element at most once, giving O(n) time with constant extra memory. The logic is simple: iterate backward and track where the increasing order breaks.

Conceptually, this solution relies on properties of arrays and a single linear pass similar to techniques used in two pointers style scans where order relationships between neighbors determine valid segments.

Recommended for interviews: Reverse Traversal. Interviewers expect the O(n) observation that only the longest increasing suffix matters. Showing the brute force idea first demonstrates problem understanding, while the reverse scan shows optimization and pattern recognition.