Skip to main content
Talentd

Minimum Cost to Make Arrays Identical - Solution & Explanation

MediumArrayGreedySorting8 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

You are given two integer arrays arr and brr of length n, and an integer k. You can perform the following operations on arr any number of times:

  • Split arr into any number of contiguous subarrays and rearrange these subarrays in any order. This operation has a fixed cost of k.

  • Choose any element in arr and add or subtract a positive integer x to it. The cost of this operation is x.

Return the minimum total cost to make arr equal to brr.

 

Example 1:

Input: arr = [-7,9,5], brr = [7,-2,-5], k = 2

Output: 13

Explanation:

  • Split arr into two contiguous subarrays: [-7] and [9, 5] and rearrange them as [9, 5, -7], with a cost of 2.
  • Subtract 2 from element arr[0]. The array becomes [7, 5, -7]. The cost of this operation is 2.
  • Subtract 7 from element arr[1]. The array becomes [7, -2, -7]. The cost of this operation is 7.
  • Add 2 to element arr[2]. The array becomes [7, -2, -5]. The cost of this operation is 2.

The total cost to make the arrays equal is 2 + 2 + 7 + 2 = 13.

Example 2:

Input: arr = [2,1], brr = [2,1], k = 0

Output: 0

Explanation:

Since the arrays are already equal, no operations are needed, and the total cost is 0.

 

Constraints:

  • 1 <= arr.length == brr.length <= 105
  • 0 <= k <= 2 * 1010
  • -105 <= arr[i] <= 105
  • -105 <= brr[i] <= 105

Approach Overview

Problem Overview: You are given two arrays and a fixed operation cost. The goal is to make the arrays identical with the minimum total cost. You can either keep elements in their current order and pay the element-wise difference cost, or rearrange the arrays (with a fixed extra cost) and then align them optimally.

Approach 1: Direct Element Matching (Greedy, O(n) time, O(1) space)

The simplest strategy keeps both arrays in their original order. Iterate through the arrays and compute the total cost as sum(abs(a[i] - b[i])). This works because each position is forced to match its counterpart, so the greedy choice is simply minimizing the difference at that position. This approach avoids any rearrangement cost but may produce a higher total if the arrays are poorly aligned. Prefer this when the arrays are already similarly ordered.

Approach 2: Sort Both Arrays and Rebuild Alignment (Greedy + Sorting, O(n log n) time, O(1) extra space)

If rearranging elements is allowed with a fixed additional cost, a better strategy is to reorder both arrays to minimize pairwise differences. Sort both arrays and then compute sum(abs(sortedA[i] - sortedB[i])). Sorting ensures the smallest elements align with the smallest counterparts, which minimizes the total absolute difference. Add the fixed rearrangement cost to this value. This greedy observation comes from the property that matching numbers with similar magnitudes minimizes total deviation. The final answer is the minimum between the direct alignment cost and the sorted alignment cost plus the operation fee.

Sorting transforms the problem into a classic minimum absolute difference pairing problem. Once sorted, a single pass computes the optimal cost.

Recommended for interviews: The greedy + sorting approach is typically what interviewers expect. The direct comparison solution shows you understand the baseline cost without rearrangement. Recognizing that sorting minimizes total pairwise absolute differences demonstrates stronger algorithmic intuition with greedy reasoning and sorting. Since the arrays are processed sequentially, the implementation stays simple while maintaining an optimal O(n log n) complexity. Problems like this frequently appear in array optimization scenarios involving array transformations.

Solution

If splitting the array is not allowed, we can directly calculate the sum of absolute differences between the two arrays as the total cost c_1. If splitting is allowed, we can divide the array arr into n subarrays of length 1, then rearrange them in any order, and compare with array brr, calculating the sum of absolute differences as the total cost c_2. To minimize c_2, we can sort both arrays and then calculate the sum of absolute differences. The final result is min(c_1, c_2 + k).

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array arr.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Element MatchingO(n)O(1)When arrays must remain in original order or rearranging is expensive
Greedy + Sorting AlignmentO(n log n)O(1) extra (in-place sort)General case when rearranging elements is allowed and reduces total difference

Video Solution

3424. Minimum Cost to Make Arrays Identical | Sorting | Arrays • Aryan Mittal • 1,180 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Minimum Cost to Make Arrays Identical easy or hard?
Minimum Cost to Make Arrays Identical is typically classified as a Medium problem. The implementation is simple, but recognizing that sorting minimizes total absolute difference requires greedy insight and familiarity with array pairing strategies.
Minimum Cost to Make Arrays Identical Python/Java solution
Implement the greedy approach by first computing the direct difference cost, then sorting both arrays and recomputing the difference. Add the fixed rearrangement cost to the sorted version and return the minimum. This logic is straightforward to implement in Python, Java, C++, Go, or TypeScript.
How to solve Minimum Cost to Make Arrays Identical in O(n)?
An O(n) solution exists if you only compare arrays in their original order. Iterate through the arrays once and compute sum(abs(a[i] - b[i])). However, this ignores the possibility of rearranging elements, which may lead to a higher cost than the sorting-based O(n log n) optimal solution.
What is the best approach for Minimum Cost to Make Arrays Identical?
The optimal approach compares two strategies: keeping the arrays in their original order or sorting both arrays and aligning them greedily. Compute the direct cost using sum of absolute differences, then compute the sorted alignment cost and add the rearrangement fee. The minimum of the two gives the final answer. The sorting-based method runs in O(n log n) time.
Is Minimum Cost to Make Arrays Identical asked at Google/Amazon/Meta?
Problems involving minimizing absolute differences and greedy pairing after sorting are common in interviews at companies like Google, Amazon, and Meta. Variants often appear under array optimization or greedy matching patterns.
What data structure is used in Minimum Cost to Make Arrays Identical?
The solution mainly relies on arrays and sorting. After sorting both arrays, a simple linear scan computes the pairwise absolute difference. No complex data structures such as heaps or hash maps are required.
What is the time complexity of Minimum Cost to Make Arrays Identical?
The optimal solution runs in O(n log n) time due to sorting both arrays. After sorting, a single linear pass computes the total absolute difference in O(n). The space complexity is O(1) extra if sorting is done in place.

Ready to solve this problem?

Practice Minimum Cost to Make Arrays Identical with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays