Minimum cost to make Array equal by increment/decrementing elements

Given an array, arr[], and the cost array cost[], the task is to find the minimum cost to make all the array elements equal by incrementing or decrementing the element at any index by 1. The cost of the increment or decrement operation for the element at index i is the cost[i].

Examples:

Input: arr[] = {1, 3, 5, 2}, cost[] = {2, 3, 1, 14}
Output: 8
Explanation: On making all elements equal to 2 the cost is 1*2 + 1*3 + 3*1 = 8 which is the minimum cost.

Input: arr[] = {3, 3, 3, 3, 3}, cost[] = {1, 2, 3, 4, 5}
Output: 0
Explanation: All are same already in the array arr[].

Approach: This can be solved using the following idea.

The idea is to try converting each array to each of all values between [1, 10⁶] and convert all to that number that gives minimum cost. We use prefix sum and suffix sum technique to store the cost to convert all elements to that index i and finally take the minimum of  sum of prefix sum and suffix sum at index i.

Follow the steps mentioned below to solve the problem:

• Initialize a variable maxSize = 1000002 which stores the max size.
• Initialize an array total_cost_at_i[] of size maxSize which stores the total cost for similar arr[i].
• Now traverse through the array and add the costs of all similar elements in the array total_cost_at_i[].
• Take the variable sum=0  to store the sum of cost till i.
• Declare the two arrays prefix for storing the cost to convert all the previous i-1 elements to i and suffix to store the cost of converting all the elements from i+1 to maxSize to i.
• Now take the minimum of prefix[i] + suffix[i] at every index and store the minimum in the min_cost variable.

Below is the implementation of the above approach.

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

Given an array, arr[], and the cost array cost[], the task is to find the minimum cost to make all the array elements equal by incrementing or decrementing the element at any index by 1. The cost of the increment or decrement operation for the element at index i is the cost[i].

Examples:

Input: arr[] = {1, 3, 5, 2}, cost[] = {2, 3, 1, 14}
Output: 8
Explanation: On making all elements equal to 2 the cost is 1*2 + 1*3 + 3*1 = 8 which is the minimum cost.

Input: arr[] = {3, 3, 3, 3, 3}, cost[] = {1, 2, 3, 4, 5}
Output: 0
Explanation: All are same already in the array arr[].

Approach: This can be solved using the following idea.

The idea is to try converting each array to each of all values between [1, 10⁶] and convert all to that number that gives minimum cost. We use prefix sum and suffix sum technique to store the cost to convert all elements to that index i and finally take the minimum of  sum of prefix sum and suffix sum at index i.

Follow the steps mentioned below to solve the problem:

• Initialize a variable maxSize = 1000002 which stores the max size.
• Initialize an array total_cost_at_i[] of size maxSize which stores the total cost for similar arr[i].
• Now traverse through the array and add the costs of all similar elements in the array total_cost_at_i[].
• Take the variable sum=0  to store the sum of cost till i.
• Declare the two arrays prefix for storing the cost to convert all the previous i-1 elements to i and suffix to store the cost of converting all the elements from i+1 to maxSize to i.
• Now take the minimum of prefix[i] + suffix[i] at every index and store the minimum in the min_cost variable.

Below is the implementation of the above approach.

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