CODEWITHSUNDEEP
xcodealgorithmarrays
Akash Goyal
Akash Goyal

Reputation: 1303

select K-elements from an array of size N, such that the difference between the minimum and maximum element in the sub-array is least

How to select K-elements from an array such that the difference between the minimum and maximum element in the subarray is least

Example: Given Array

     100 200 20 10 30 32 35 50 60 28 18
     k=4

Various possible Outcomes

    10 18 20 28
    max-min = 28-10 = 18

    28 30 32 35
    max-min = 35-28 = 7

etc.

  So, we will select [28 30 32 35] as the subarray

Upvotes: 2

Views: 1174

Answers (1)

sve
sve

Reputation: 4356

Let the array be a[1..N]. Sort it. Then pick the subarray a[i], a[i + 1], ..., a[i + K - 1] , i = 1, ..., N - K + 1, such that a[i + K - 1] - a[i] is minimal. You can do this in linear time. Since the sorting takes O(nlogn) the total execution time of the algorithm is O(nlogn)

Upvotes: 3

Related Questions