Minimum cost required to convert all Subarrays of size K to a single element

0 0 9 minutes read

Prerequisite: Sliding Window Median
Given an array arr[] consisting of N integers and an integer K, the task is to find the minimum cost required to make each element of every subarray of length K equal. Cost of replacing any array element by another element is the absolute difference between the two.
Examples:

Input: A[] = {1, 2, 3, 4, 6}, K = 3
Output: 7
Explanation:
Subarray 1: Cost to convert subarray {1, 2, 3} to {2, 2, 2} = |1-2| + |2-2| + |3-2| = 2
Subarray 2: Cost to convert subarray {2, 3, 4} to {3, 3, 3} = |2-3| + |3-3| + |4-3| = 2
Subarray 3: Cost to convert subarray {3, 4, 6} to {4, 4, 4} = |3-4| + |4-4| + |6-4| = 3
Minimum Cost = 2 + 2 + 3 = 7/
Input: A[] = {2, 3, 4, 4, 1, 7, 6}, K = 4
Output: 21

Approach:
To find the minimum cost to convert each element of the subarray to a single element, change every element of the subarray to the median of that subarray. Follow the steps below to solve the problem:

To find the median for each running subarray efficiently, use a multiset to get the sorted order of elements in each subarray. Median will be the middle element of this multiset.
For the next subarray remove the leftmost element of the previous subarray from the multiset, add the current element to the multiset.
Keep a pointer mid to efficiently keep track of the middle element of the multiset.
If the newly added element is smaller than the previous middle element, move mid to its immediate smaller element. Otherwise, move mid to its immediate next element.
Calculate cost of replacing every element of the subarray by the equation | A[i] – median_{each_subarray} |.
Finally print the total cost.

Below is the implementation for the above approach:

C++

// C++ Program to implement 
// the above approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find the minimum 
// cost to convert each element of 
// every subarray of size K equal 
int minimumCost(vector<int> arr, int n, 
                int k) 
{ 
    // Stores the minimum cost 
    int totalcost = 0; 
    int i, j; 
  
    // Stores the first K elements 
    multiset<int> mp(arr.begin(), 
                     arr.begin() + k); 
  
    if (k == n) { 
  
        // Obtain the middle element of 
        // the multiset 
        auto mid = next(mp.begin(), 
                        n / 2 - ((k + 1) % 2)); 
  
        int z = *mid; 
  
        // Calculate cost for the subarray 
        for (i = 0; i < n; i++) 
            totalcost += abs(z - arr[i]); 
  
        // Return the total cost 
        return totalcost; 
    } 
    else { 
  
        // Obtain the middle element 
        // in multiset 
        auto mid = next(mp.begin(), 
                        k / 2 - ((k + 1) % 2)); 
  
        for (i = k; i < n; i++) { 
  
            int zz = *mid; 
            int cost = 0; 
            for (j = i - k; j < i; j++) { 
  
                // Cost for the previous 
                // k length subarray 
                cost += abs(arr[j] - zz); 
            } 
            totalcost += cost; 
  
            // Insert current element 
            // into multiset 
            mp.insert(arr[i]); 
  
            if (arr[i] < *mid) { 
  
                // New element appears 
                // to the left of mid 
                mid--; 
            } 
  
            if (arr[i - k] <= *mid) { 
  
                // New element appears 
                // to the right of mid 
                mid++; 
            } 
  
            // Remove leftmost element 
            // from the window 
            mp.erase(mp.lower_bound(arr[i - k])); 
  
            // For last element 
            if (i == n - 1) { 
                zz = *mid; 
                cost = 0; 
  
                for (j = i - k + 1; 
                     j <= i; j++) { 
  
                    // Calculate cost for the subarray 
                    cost += abs(zz - arr[j]); 
                } 
  
                totalcost += cost; 
            } 
        } 
  
        // Return the total cost 
        return totalcost; 
    } 
} 
  
// Driver Code 
int main() 
{ 
    int N = 5, K = 3; 
  
    vector<int> A({ 1, 2, 3, 4, 6 }); 
  
    cout << minimumCost(A, N, K); 
} 

Java

import java.util.*; 
  
class GFG { 
  
  // Function to find the minimum 
  // cost to convert each element of 
  // every subarray of size K equal 
  static int minimumCost(int[] arr, int n, int k) 
  { 
    // Stores the minimum cost 
    int totalcost = 0; 
    int i = 0, j = 0; 
  
    // Stores the first K elements 
    List<Integer> mp = new ArrayList<Integer>(); 
    for (int x = 0; x < k; x++) { 
      mp.add(arr[x]); 
    } 
    Collections.sort(mp); 
  
    if (k == n) { 
      // Obtain the middle element of 
      // the list 
      int mid = mp.get(n / 2 - ((k + 1) % 2)); 
      int z = mid; 
  
      // Calculate cost for the subarray 
      for (i = 0; i < n; i++) { 
        totalcost += Math.abs(z - arr[i]); 
      } 
  
      // Return the total cost 
      return totalcost; 
    } 
    else { 
      // Obtain the middle element in the list 
      int mid = mp.get(k / 2 - ((k + 1) % 2)); 
  
      for (i = k; i < n; i++) { 
        int zz = mid; 
        int cost = 0; 
        for (j = i - k; j < i; j++) { 
          // Cost for the previous 
          // k length subarray 
          cost += Math.abs(arr[j] - zz); 
        } 
        totalcost += cost; 
  
        // Insert current element 
        // into the list 
        int idx 
          = Collections.binarySearch(mp, arr[i]); 
        if (idx < 0) { 
          mp.add(-idx - 1, arr[i]); 
        } 
        else { 
          mp.add(idx, arr[i]); 
        } 
  
        if (arr[i] < mid) { 
          // New element appears 
          // to the left of mid 
          mid = mp.get(k / 2 - ((k + 1) % 2)); 
        } 
  
        if (arr[i - k] <= mid) { 
          // New element appears 
          // to the right of mid 
          mid = mp.get(k / 2 - ((k + 1) % 2) + 1); 
        } 
  
        // Remove leftmost element 
        // from the window 
        idx = Collections.binarySearch(mp, 
                                       arr[i - k]); 
        if (idx >= 0) { 
          mp.remove(idx); 
        } 
  
        // For last element 
        if (i == n - 1) { 
          zz = mid; 
          cost = 0; 
          for (j = i - k + 1; j < i + 1; j++) { 
            // Calculate cost for the subarray 
            cost += Math.abs(zz - arr[j]); 
          } 
          totalcost += cost; 
        } 
      } 
  
      // Return the total cost 
      return totalcost; 
    } 
  } 
  
  // Driver Code 
  public static void main(String[] args) 
  { 
    int N = 5, K = 3; 
    int[] A = { 1, 2, 3, 4, 6 }; 
    System.out.println(minimumCost(A, N, K)); 
  } 
} 
  
// This code is contributed by phasing17.

Python3

import bisect 
  
# Function to find the minimum 
# cost to convert each element of 
# every subarray of size K equal 
def minimumCost(arr, n, k): 
    # Stores the minimum cost 
    totalcost = 0
    i, j = 0, 0
  
    # Stores the first K elements 
    mp = sorted(arr[:k]) 
  
    if k == n: 
        # Obtain the middle element of 
        # the list 
        mid = mp[n // 2 - ((k + 1) % 2)] 
        z = mid 
  
        # Calculate cost for the subarray 
        for i in range(n): 
            totalcost += abs(z - arr[i]) 
  
        # Return the total cost 
        return totalcost 
    else: 
        # Obtain the middle element in the list 
        mid = mp[k // 2 - ((k + 1) % 2)] 
  
        for i in range(k, n): 
            zz = mid 
            cost = 0
            for j in range(i - k, i): 
                # Cost for the previous 
                # k length subarray 
                cost += abs(arr[j] - zz) 
            totalcost += cost 
  
            # Insert current element 
            # into the list 
            bisect.insort(mp, arr[i]) 
  
            if arr[i] < mid: 
                # New element appears 
                # to the left of mid 
                mid = mp[k // 2 - ((k + 1) % 2)] 
  
            if arr[i - k] <= mid: 
                # New element appears 
                # to the right of mid 
                mid = mp[k // 2 - ((k + 1) % 2) + 1] 
  
            # Remove leftmost element 
            # from the window 
            idx = bisect.bisect_left(mp, arr[i - k]) 
            mp.pop(idx) 
  
            # For last element 
            if i == n - 1: 
                zz = mid 
                cost = 0
                for j in range(i - k + 1, i + 1): 
                    # Calculate cost for the subarray 
                    cost += abs(zz - arr[j]) 
                totalcost += cost 
  
        # Return the total cost 
        return totalcost 
  
# Driver Code 
if __name__ == '__main__': 
    N, K = 5, 3
    A = [1, 2, 3, 4, 6] 
    print(minimumCost(A, N, K)) 
  
    # This code is contributed by phasing17.

Javascript

// Javascript program for the above approach 
  
// Function to find the minimum cost to convert each  
// element of every subarray of size K equal 
function minimumCost(arr, n, k) { 
  // Stores the minimum cost 
  let totalcost = 0; 
  let i = 0, 
    j = 0; 
  
  // Stores the first K elements 
  let mp = arr.slice(0, k).sort((a, b) => a - b); 
  
  if (k == n) { 
    // Obtain the middle element of the list 
    let mid = mp[(Math.floor(n / 2) - ((k + 1) % 2))]; 
    let z = mid; 
  
    // Calculate cost for the subarray 
    for (let i = 0; i < n; i++) { 
      totalcost += Math.abs(z - arr[i]); 
    } 
  
    // Return the total cost 
    return totalcost; 
  } else { 
    // Obtain the middle element in the list 
    let mid = mp[(Math.floor(k / 2) - ((k + 1) % 2))]; 
  
    for (let i = k; i < n; i++) { 
      let zz = mid; 
      let cost = 0; 
      for (let j = i - k; j < i; j++) { 
        // Cost for the previous k length subarray 
        cost += Math.abs(arr[j] - zz); 
      } 
      totalcost += cost; 
  
      // Insert current element into the list 
      mp.splice(bisect_left(mp, arr[i]), 0, arr[i]); 
  
      if (arr[i] < mid) { 
        // New element appears to the left of mid 
        mid = mp[(Math.floor(k / 2) - ((k + 1) % 2))]; 
      } 
  
      if (arr[i - k] <= mid) { 
        // New element appears to the right of mid 
        mid = mp[(Math.floor(k / 2) - ((k + 1) % 2) + 1)]; 
      } 
  
      // Remove leftmost element from the window 
      mp.splice(bisect_left(mp, arr[i - k]), 1); 
  
      // For last element 
      if (i == n - 1) { 
        zz = mid; 
        cost = 0; 
        for (let j = i - k + 1; j <= i; j++) { 
          // Calculate cost for the subarray 
          cost += Math.abs(zz - arr[j]); 
        } 
        totalcost += cost; 
      } 
    } 
  
    // Return the total cost 
    return totalcost; 
  } 
} 
  
// Driver Code 
let N = 5, 
  K = 3; 
let A = [1, 2, 3, 4, 6]; 
console.log(minimumCost(A, N, K)); 
  
// Returns the index at which the element should be inserted into the sorted list 
function bisect_left(arr, x) { 
  let lo = 0, 
    hi = arr.length; 
  while (lo < hi) { 
    let mid = Math.floor((lo + hi) / 2); 
    if (arr[mid] < x) lo = mid + 1; 
    else hi = mid; 
  } 
  return lo; 
} 
  
// contributed by adityasharmadev01 

C#

// C# Equivalent 
using System; 
using System.Collections.Generic; 
   
public class GFG 
{ 
    // Function to find the minimum 
    // cost to convert each element of 
    // every subarray of size K equal 
    static int minimumCost(int[] arr, int n, int k) 
    { 
        // Stores the minimum cost 
        int totalcost = 0; 
        int i = 0, j = 0; 
   
        // Stores the first K elements 
        List<int> mp = new List<int>(); 
        for (int x = 0; x < k; x++) 
        { 
            mp.Add(arr[x]); 
        } 
        mp.Sort(); 
   
        if (k == n) 
        { 
            // Obtain the middle element of 
            // the list 
            int mid = mp[n / 2 - (k + 1) % 2]; 
            int z = mid; 
   
            // Calculate cost for the subarray 
            for (i = 0; i < n; i++) 
            { 
                totalcost += Math.Abs(z - arr[i]); 
            } 
   
            // Return the total cost 
            return totalcost; 
        } 
        else
        { 
            // Obtain the middle element in the list 
            int mid = mp[k / 2 - (k + 1) % 2]; 
   
            for (i = k; i < n; i++) 
            { 
                int zz = mid; 
                int cost = 0; 
                for (j = i - k; j < i; j++) 
                { 
                    // Cost for the previous 
                    // k length subarray 
                    cost += Math.Abs(arr[j] - zz); 
                } 
                totalcost += cost; 
   
                // Insert current element 
                // into the list 
                int idx = mp.BinarySearch(arr[i]); 
                if (idx < 0) 
                { 
                    mp.Insert(-idx - 1, arr[i]); 
                } 
                else
                { 
                    mp.Insert(idx, arr[i]); 
                } 
   
                if (arr[i] < mid) 
                { 
                    // New element appears 
                    // to the left of mid 
                    mid = mp[k / 2 - (k + 1) % 2]; 
                } 
   
                if (arr[i - k] <= mid) 
                { 
                    // New element appears 
                    // to the right of mid 
                    mid = mp[k / 2 - (k + 1) % 2 + 1]; 
                } 
   
                // Remove leftmost element 
                // from the window 
                idx = mp.BinarySearch(arr[i - k]); 
                if (idx >= 0) 
                { 
                    mp.RemoveAt(idx); 
                } 
   
                // For last element 
                if (i == n - 1) 
                { 
                    zz = mid; 
                    cost = 0; 
                    for (j = i - k + 1; j < i + 1; j++) 
                    { 
                        // Calculate cost for the subarray 
                        cost += Math.Abs(zz - arr[j]); 
                    } 
                    totalcost += cost; 
                } 
            } 
   
            // Return the total cost 
            return totalcost; 
        } 
    } 
   
    // Driver Code 
    public static void Main(String[] args) 
    { 
        int N = 5, K = 3; 
        int[] A = { 1, 2, 3, 4, 6 }; 
        Console.Write(minimumCost(A, N, K)); 
    } 
}

Output:

Time Complexity: O(NlogN)
Auxiliary Space: O(1)

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!