Watch 10 video solutions for Minimum Prefix Removal to Make Array Strictly Increasing, a medium level problem involving Array. This walkthrough by Developer Coder has 275 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
You need to remove exactly one prefix (possibly empty) from nums.
Return an integer denoting the minimum length of the removed prefix such that the remaining array is strictly increasing.
Example 1:
Input: nums = [1,-1,2,3,3,4,5]
Output: 4
Explanation:
Removing the prefix = [1, -1, 2, 3] leaves the remaining array [3, 4, 5] which is strictly increasing.
Example 2:
Input: nums = [4,3,-2,-5]
Output: 3
Explanation:
Removing the prefix = [4, 3, -2] leaves the remaining array [-5] which is strictly increasing.
Example 3:
Input: nums = [1,2,3,4]
Output: 0
Explanation:
The array nums = [1, 2, 3, 4] is already strictly increasing so removing an empty prefix is sufficient.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109āāāāāāā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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Check | O(n^2) | O(1) | Initial reasoning or very small arrays where simplicity matters |
| Reverse Traversal (Longest Increasing Suffix) | O(n) | O(1) | Optimal approach for interviews and large arrays |