FastPrep
Problem · Array

Min Deletions to Almost Sorted

Learn this problem
● HardSalesforce logoSalesforceOA
See Salesforce hiring insights

Problem statement

An array of integers is almost sorted if at most one element can be deleted from it to make it perfectly sorted, ascending. For example, arrays [2, 1, 7], [13], [9, 2] and [1, 5, 6] are almost sorted because they have 0 or 1 elements out of place. The arrays [4, 2, 1], [1, 2, 6, 4, 3] are not because they have more than one element out of place. Given an array of n unique integers, determine the minimum number of elements to remove so it becomes almost sorted.

Function

minDeletions(arr: int[]) → int

Complete the function minDeletions in the editor.

minDeletions has the following parameter(s):

  1. int arr[n]: an unsorted array of integers

Returns

int: the minimum number of items that must be deleted to create an almost sorted array

Examples

Example 1

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

Remove 2 to get arr' = [3, 4, 5, 1] or remove 7 to get arr' = [3, 4, 2, 5], both of which are almost sorted. The minimum number of elements that must be removed in this case is 1.

Constraints

  • 1 ≤ n ≤ 105
  • 1 ≤ arr[i] ≤ 109
  • All elements of arr are distinct.

More Salesforce problems

drafts saved locally
public int minDeletions(int[] arr) {
  // write your code here
}
arr[3, 4, 2, 5, 1]
expected1
checking account