FastPrepFind Min Max Difference

Find Min Max Difference

Amazon logoAmazon● HardFULLTIMEOA

Updated

Problem statement

You are given an unsorted array arr of n integers and an integer k.

Keep any n - k of the elements. Any combination of elements may be kept, and their order does not matter. Sort the kept elements and look at the differences between consecutive elements. The largest of these differences is the score of that choice. Return the smallest score over all possible choices.

Function

findMinMaxDifference(arr: int[], k: int) → int

Complete the function findMinMaxDifference in the editor.

findMinMaxDifference has the following parameters:

  1. int[] arr: an unsorted array of integers
  2. int k: the number of elements to leave out

Returns int: the smallest possible largest difference between consecutive kept elements

Examples

Example 1

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

Here arr = [1, 4, 3, 6, 5] and k = 2, so we keep n - k = 3 values. Some possible choices:

  • [4, 3, 1], sorted [1, 3, 4]: differences 3 - 1 = 2 and 4 - 3 = 1. The max of these is 2.
  • [1, 6, 4], sorted [1, 4, 6]: differences 4 - 1 = 3 and 6 - 4 = 2. The max of these is 3.
  • [3, 6, 5], sorted [3, 5, 6]: differences 5 - 3 = 2 and 6 - 5 = 1. The max of these is 2.
  • [4, 6, 5], sorted [4, 5, 6]: differences 5 - 4 = 1 and 6 - 5 = 1. The max of these is 1.

Out of all possible choices, the smallest of these maxima is 1. It cannot be lower, because all values are different. Hence, the answer is 1.

Constraints

  • 2 <= n <= 10^5, where n is the length of arr
  • 0 <= k <= n - 2
  • 1 <= arr[i] <= 10^9

More Amazon interview questions

Similar questions at other companies

Interview reports that mention this question

Amazon interview experiences

See Amazon hiring insights
Saved
class Solution {
    public int findMinMaxDifference(int[] arr, int k) {
      // write your code here
    }

}
Checking account…