FastPrep
Problem · Array

Minimum Removals for a Nice Array

Learn this problem
● MediumAdobe logoAdobeFULLTIMEONSITE INTERVIEW

Problem statement

An array is nice when removing exactly one of its elements leaves a strictly increasing array.

Given an array of positive integers nums, delete the minimum number of elements, without reordering the remaining elements, so that the remaining array is nice. Return that minimum number.

The remaining nice array must contain at least two elements.

Function

minimumRemovalsForNice(nums: int[]) → int

Examples

Example 1

nums = [4,1,2,3]return = 0

The whole array is already nice because deleting 4 leaves 1, 2, 3.

Example 2

nums = [5,4,3,2,1]return = 3

A longest increasing subsequence has length 1, so at most two elements can remain in a nice array.

Constraints

  • 2 <= nums.length <= 200000
  • 1 <= nums[i] <= 10^9
  • Deleting an element preserves the relative order of all remaining elements.

More Adobe problems

drafts saved locally
public int minimumRemovalsForNice(int[] nums) {
    // Write your code here.
}
nums[4,1,2,3]
expected0
checking account