FastPrep
Problem · Array

Sort One Displaced Element

Learn this problem
● MediumGleanFULLTIMEPHONE SCREEN

Problem statement

You are given an integer array values. It was formed from some nondecreasing array by removing at most one element and inserting that same element at any position.

Return the values in nondecreasing order. Your algorithm must run in O(n) time. Return a new array; do not modify values.

Function

sortOneDisplaced(values: int[]) → int[]

Examples

Example 1

values = [1,2,6,3,4,5,7]return = [1,2,3,4,5,6,7]

The value 6 is the only displaced element. Removing it and inserting it between 5 and 7 restores nondecreasing order.

Example 2

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

Duplicate values are allowed. The first 4 can be moved beside the second 4.

Example 3

values = [1,2,3,3]return = [1,2,3,3]

The input is already nondecreasing, so the returned array has the same values.

Constraints

  • 1 <= values.length <= 200000
  • Every element is a 32-bit signed integer.
  • There exists a nondecreasing array from which values can be obtained by moving at most one element.
drafts saved locally
public int[] sortOneDisplaced(int[] values) {
    // write your code here
}
values[1,2,6,3,4,5,7]
expected[1,2,3,4,5,6,7]
checking account