Split a given array into K subarrays minimizing the difference between their maximum and minimum

0 0 5 minutes read

Given a sorted array arr[] of N integers and an integer K, the task is to split the array into K subarrays such that the sum of the difference of maximum and minimum element of each subarray is minimized.

Examples:

Input: arr[] = {1, 3, 3, 7}, K = 4
Output: 0
Explanation:
The given array can be split into 4 subarrays as {1}, {3}, {3}, and {7}.
The difference between minimum and maximum of each subarray is:
1. {1}, difference = 1 – 1 = 0
2. {3}, difference = 3 – 3 = 0
3. {3}, difference = 3 – 3 = 0
4. {7}, difference = 7 – 7 = 0
Therefore, the sum all the difference is 0 which is minimized.

Input: arr[] = {4, 8, 15, 16, 23, 42}, K = 3
Output: 12
Explanation:
The given array can be split into 3 subarrays as {4, 8, 15, 16}, {23}, and {42}.
The difference between minimum and maximum of each subarray is:
1. {4, 8, 15, 16}, difference = 16 – 4 = 12
2. {23}, difference = 23 – 23 = 0
3. {42}, difference = 42 – 42 = 0
Therefore, the sum all the difference is 12 which is minimized.

Approach: To split the given array into K subarrays with the given conditions, the idea is to split at indexes(say i) where the difference between elements arr[i+1] and arr[i] is largest. Below are the steps to implement this approach:

Store the difference between consecutive pairs of elements in the given array arr[] into another array(say temp[]).
Sort the array temp[] in increasing order.
Initialise the total difference(say diff) as the difference of the first and last element of the given array arr[].
Add the first K – 1 values from the array temp[] to the above difference.
The value stored in diff is the minimum sum of the difference of maximum and minimum element of the K subarray.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the subarray
int find(int a[], int n, int k)
{
    vector<int> v;
 
    // Add the difference to vectors
    for (int i = 1; i < n; ++i) {
        v.push_back(a[i - 1] - a[i]);
    }
 
    // Sort vector to find minimum k
    sort(v.begin(), v.end());
 
    // Initialize result
    int res = a[n - 1] - a[0];
 
    // Adding first k-1 values
    for (int i = 0; i < k - 1; ++i) {
        res += v[i];
    }
 
// Return the minimized sum
    return res;
}
 
// Driver Code
int main()
{
// Given array arr[]
    int arr[] = { 4, 8, 15, 16, 23, 42 };
 
    int N = sizeof(arr) / sizeof(int);
 
// Given K
int K = 3;
 
// Function Call
    cout << find(arr, N, K) << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the subarray
static int find(int a[], int n, int k)
{
    Vector<Integer> v = new Vector<Integer>();
 
    // Add the difference to vectors
    for(int i = 1; i < n; ++i)
    {
       v.add(a[i - 1] - a[i]);
    }
 
    // Sort vector to find minimum k
    Collections.sort(v);
 
    // Initialize result
    int res = a[n - 1] - a[0];
 
    // Adding first k-1 values
    for(int i = 0; i < k - 1; ++i)
    {
       res += v.get(i);
    }
     
    // Return the minimized sum
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 4, 8, 15, 16, 23, 42 };
 
    int N = arr.length;
     
    // Given K
    int K = 3;
     
    // Function Call
    System.out.print(find(arr, N, K) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function to find the subarray
def find(a, n, k):
     
    v = []
     
    # Add the difference to vectors
    for i in range(1, n):
        v.append(a[i - 1] - a[i])
         
    # Sort vector to find minimum k
    v.sort()
     
    # Initialize result
    res = a[n - 1] - a[0]
     
    # Adding first k-1 values
    for i in range(k - 1):
        res += v[i]
     
    # Return the minimized sum
    return res
     
# Driver code
arr = [ 4, 8, 15, 16, 23, 42 ]
 
# Length of array
N = len(arr)
 
K = 3
 
# Function Call
print(find(arr, N, K))
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the subarray
static int find(int []a, int n, int k)
{
    List<int> v = new List<int>();
 
    // Add the difference to vectors
    for(int i = 1; i < n; ++i)
    {
       v.Add(a[i - 1] - a[i]);
    }
 
    // Sort vector to find minimum k
    v.Sort();
 
    // Initialize result
    int res = a[n - 1] - a[0];
 
    // Adding first k-1 values
    for(int i = 0; i < k - 1; ++i)
    {
       res += v[i];
    }
     
    // Return the minimized sum
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 4, 8, 15, 16, 23, 42 };
    int N = arr.Length;
     
    // Given K
    int K = 3;
     
    // Function Call
    Console.Write(find(arr, N, K) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// javascript program for the above approach
 
    // Function to find the subarray
    function find(a , n , k) {
        var v = [];
 
        // Add the difference to vectors
        for (i = 1; i < n; ++i) {
            v.push(a[i - 1] - a[i]);
        }
 
        // Sort vector to find minimum k
        v.sort((a,b)=>a-b);
 
        // Initialize result
        var res = a[n - 1] - a[0];
 
        // Adding first k-1 values
        for (i = 0; i < k - 1; ++i) {
            res += v[i];
        }
 
        // Return the minimized sum
        return res;
    }
 
    // Driver Code
     
 
        // Given array arr
        var arr = [ 4, 8, 15, 16, 23, 42 ];
 
        var N = arr.length;
 
        // Given K
        var K = 3;
 
        // Function Call
        document.write(find(arr, N, K) + "\n");
 
// This code contributed by aashish1995
</script>

Output:

Time Complexity: O(N), where N is the number of elements in the array.
Auxiliary Space: O(N), where N is the number of elements in the array.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!