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] – medianeach_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:
7
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
