Find Min Max Difference
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:
int[] arr: an unsorted array of integersint 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 = 1Here 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, wherenis the length ofarr0 <= k <= n - 21 <= arr[i] <= 10^9
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Delete and Freeze GameRubrik · OARubrik interview questions
- Most Segments That Sort the ArrayRippling · OARippling interview questions
- IPO Share AllocationTwo Sigma · OATwo Sigma interview questions
- Most Items Within Budget from a Start IndexHudson River Trading · OAHudson River Trading interview questions
- Divide Tree NodesGoogle · OA · ONSITE INTERVIEWGoogle interview questions
- Maximum Server Processing TimeArista Networks · OAArista Networks interview questions
- Minimum Satellite Data Transfer IterationsHSBC · OAHSBC interview questions
- Initial Public OfferingPoint72 · OAPoint72 interview questions
- Luna and the Colorful SocksPhonePe · OAPhonePe interview questions
- Minimum Starting Coins to Buy All ProductsMicrosoft · OAMicrosoft interview questions