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.

A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.

An array is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

 

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

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