Skip to content

3818. Minimum Prefix Removal to Make Array Strictly Increasing

Description

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​​​​​​​

Solutions

Solution 1: Reverse Traversal

Thinking

We must drop a (possibly empty) prefix so the rest is strictly increasing, and the prefix should be as short as possible. \(n \le 10^5\) forbids testing every prefix.

The remainder is a suffix that is itself strictly increasing. The shortest prefix is the complement of the longest such suffix.

Walking right to left, the first descent \(nums[i-1] \ge nums[i]\) stops the suffix; the answer is \(i\).

If no descent appears, the whole array is increasing and the answer is \(0\).

We can traverse the array backwards from the end to find the first position \(i\) that does not satisfy the strictly increasing condition, i.e., \(nums[i-1] \geq nums[i]\). At this point, the minimum length of the prefix to remove is \(i\).

If the entire array is strictly increasing, we do not need to remove any prefix, so we return \(0\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def minimumPrefixLength(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1, 0, -1):
            if nums[i - 1] >= nums[i]:
                return i
        return 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int minimumPrefixLength(int[] nums) {
        for (int i = nums.length - 1; i > 0; --i) {
            if (nums[i - 1] >= nums[i]) {
                return i;
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int minimumPrefixLength(vector<int>& nums) {
        for (int i = nums.size() - 1; i; --i) {
            if (nums[i - 1] >= nums[i]) {
                return i;
            }
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
func minimumPrefixLength(nums []int) int {
    for i := len(nums) - 1; i > 0; i-- {
        if nums[i-1] >= nums[i] {
            return i
        }
    }
    return 0
}

1
2
3
4
5
6
7
8
function minimumPrefixLength(nums: number[]): number {
    for (let i = nums.length - 1; i; --i) {
        if (nums[i - 1] >= nums[i]) {
            return i;
        }
    }
    return 0;
}

Comments