LeetCode 3424 - Minimum Cost to Make Arrays Identical

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to transform one integer array arr into another integer array brr with the minimum cost using two types of operations. The first operation allows splitting arr into contiguous subarrays and rearranging them at a fixed cost k per operation. The second operation allows adjusting any element by adding or subtracting a positive integer x, which costs exactly x.

The input consists of two arrays of length n (up to 10^5) and an integer k (up to 2 * 10^10). The output is the minimum total cost to make arr equal to brr.

The constraints indicate that the solution must be efficient in both time and space because the arrays can be very large. Negative numbers are allowed, and the split-and-rearrange operation can be done multiple times.

Edge cases include arrays that are already equal, arrays with extreme negative and positive values, and the case where k = 0 meaning splitting is free.

The core challenge is deciding when it is cheaper to rearrange contiguous subarrays versus adjusting elements individually, and efficiently computing the minimum cost given large arrays.

Approaches

A brute-force approach would consider every possible subarray split of arr and every permutation of these subarrays, then compute the total cost of element-wise adjustments to match brr. This guarantees correctness but is computationally infeasible due to the factorial number of permutations, leading to a time complexity far beyond the input constraints.

The key insight for an optimal solution is that rearrangement can be simulated by sorting. Sorting arr and brr in ascending order allows us to align the elements optimally with minimal individual adjustment costs. The total adjustment cost is the sum of absolute differences of the sorted arrays. Then, we compare this with the cost of using the split operation, which allows a fixed-cost rearrangement. Essentially, if the split operation cost k is less than or equal to the benefit of rearranging, we include it in the total cost; otherwise, we only rely on element adjustments.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Consider all subarray permutations and calculate adjustment costs
Optimal	O(n log n)	O(n)	Sort both arrays and compute sum of element-wise differences; add `k` if beneficial

Algorithm Walkthrough

First, sort both arr and brr in non-decreasing order. Sorting ensures that each element in arr can be paired with the element in brr that minimizes the adjustment cost.
Compute the absolute difference between corresponding elements of the sorted arrays. The sum of these differences gives the total cost of element adjustments required if no splits are used.
Determine if performing a split-and-rearrange operation reduces the total cost. The minimum number of splits needed is 1 because a single full-array rearrangement is equivalent to sorting at a fixed cost k.
If k is less than the cost saved by reordering, add k to the total adjustment cost; otherwise, only use the adjustment cost.
Return the computed total cost as the result.

Why it works: Sorting aligns elements optimally to minimize the sum of absolute differences. The optional split operation accounts for scenarios where rearrangement provides a cheaper path. By combining these steps, we guarantee that every element reaches its target value with minimal cost.

Python Solution

from typing import List

class Solution:
    def minCost(self, arr: List[int], brr: List[int], k: int) -> int:
        arr.sort()
        brr.sort()
        adjustment_cost = sum(abs(a - b) for a, b in zip(arr, brr))
        return adjustment_cost + (k if adjustment_cost > 0 else 0)

In this implementation, we first sort arr and brr to align elements optimally. We then compute the sum of absolute differences for element adjustments. If there is any non-zero adjustment, performing at least one split may help in reordering; thus, we add k if needed. The algorithm ensures the minimum cost for all valid input scenarios.

Go Solution

import (
    "sort"
    "math"
)

func minCost(arr []int, brr []int, k int64) int64 {
    sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })
    sort.Slice(brr, func(i, j int) bool { return brr[i] < brr[j] })
    
    var adjustmentCost int64 = 0
    for i := 0; i < len(arr); i++ {
        adjustmentCost += int64(math.Abs(float64(arr[i] - brr[i])))
    }
    
    if adjustmentCost > 0 {
        adjustmentCost += k
    }
    
    return adjustmentCost
}

In Go, we sort using sort.Slice and calculate the sum of absolute differences. We explicitly cast integers to float64 for math.Abs and then back to int64. The logic mirrors the Python implementation, and edge cases are handled identically.

Worked Examples

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

Sort arrays: arr = [-7, 5, 9], brr = [-5, -2, 7]
Compute element-wise absolute differences: abs(-7 - -5) = 2, abs(5 - -2) = 7, abs(9 - 7) = 2
Sum of differences = 2 + 7 + 2 = 11
Since adjustment cost > 0, add split cost k = 2
Total cost = 11 + 2 = 13

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

Arrays already equal after sorting
Adjustment cost = 0
Total cost = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting both arrays dominates the computation
Space	O(n)	Space for storing sorted arrays (or in-place)

Sorting ensures the minimum cost alignment of elements, and computing absolute differences is linear.

Test Cases

# Provided examples
assert Solution().minCost([-7,9,5], [7,-2,-5], 2) == 13  # Example 1
assert Solution().minCost([2,1], [2,1], 0) == 0          # Example 2

# Boundary cases
assert Solution().minCost([0], [0], 0) == 0               # Single element, no adjustment
assert Solution().minCost([-100000,100000], [100000,-100000], 5) == 200005  # Large numbers
assert Solution().minCost([1,2,3], [3,2,1], 1) == 3      # k < total adjustment
assert Solution().minCost([1,2,3], [1,2,3], 10) == 0     # Arrays equal, k ignored

Test	Why
`[-7,9,5] vs [7,-2,-5], k=2`	Example with rearrangement and adjustments
`[2,1] vs [2,1], k=0`	Arrays already equal, zero cost
`[0] vs [0], k=0`	Single element, no adjustment
`[-1e5,1e5] vs [1e5,-1e5], k=5`	Extreme values, tests integer handling
`[1,2,3] vs [3,2,1], k=1`	Rearrangement cost compared to adjustment sum
`[1,2,3] vs [1,2,3], k=10`	Arrays equal, no split needed

Edge Cases

One important edge case is when arr and brr are already identical. In this case, the function must return zero and avoid unnecessary split costs. Another is when k = 0, allowing free rearrangement; the implementation should correctly compute only adjustment costs if any. A third edge case occurs with large negative and positive numbers, which can challenge integer overflow in some languages. The solution uses int64 in Go and standard integers in Python to handle this safely. Finally, single-element arrays must also be handled gracefully, as no splits are meaningful in this scenario.