LeetCode 2967 - Minimum Cost to Make Array Equalindromic
We are given an integer array nums. We may repeatedly choose any element and replace it with any positive integer x. Replacing a value nums[i] with x costs |nums[i] - x|.
Difficulty: 🟡 Medium
Topics: Array, Math, Binary Search, Greedy, Sorting
Solution
LeetCode 2967 - Minimum Cost to Make Array Equalindromic
Problem Understanding
We are given an integer array nums. We may repeatedly choose any element and replace it with any positive integer x. Replacing a value nums[i] with x costs |nums[i] - x|.
The goal is to transform the array so that every element becomes equal to the same value y, where y must satisfy two conditions:
yis a palindromic number.y < 10^9.
The total cost is the sum of the costs paid for every modified element. We must return the minimum possible total cost.
Another way to think about the problem is that we need to choose a single palindromic target value y, then pay:
$$\sum |nums[i] - y|$$
for all elements in the array. Our task is to find the palindromic number that minimizes this expression.
The constraints are large:
ncan be as large as100,000nums[i]can be as large as10^9
Because of these constraints, any algorithm that tries all possible target values or performs expensive computations for every element will be too slow.
Several edge cases are worth noticing:
- The optimal median value might already be palindromic.
- The optimal median value might not be palindromic, requiring us to move to the nearest palindromic numbers.
- Arrays with a single element should return zero if that element is already palindromic, otherwise the distance to the nearest palindrome.
- Values can be close to
10^9, so palindrome generation must respect they < 10^9requirement. - Multiple palindromic numbers may produce similar costs, so both sides of the median need consideration.
Approaches
Brute Force
A direct approach would be to generate every palindromic number below 10^9.
For each palindrome p, compute:
$$\sum |nums[i] - p|$$
and keep the minimum.
This is correct because it explicitly evaluates every valid target.
However, there are roughly 110,000 palindromes below 10^9. Computing the cost for each palindrome requires scanning up to 100,000 array elements.
The resulting complexity is approximately:
$$110,000 \times 100,000$$
which is far too large.
Key Insight
For minimizing the sum of absolute deviations,
$$\sum |nums[i] - y|$$
the optimal unconstrained value is the median of the array.
This is a classic property of absolute distance minimization.
If there were no palindrome restriction, the median would be the answer.
Since our target must be a palindrome, the best palindrome must be very close to the median. Moving farther away from the median can only increase the absolute-distance objective.
Therefore:
- Sort the array.
- Find the median.
- Generate all palindromes below
10^9. - Binary search for the palindrome closest to the median.
- Only evaluate the nearest palindrome on the left and the nearest palindrome on the right.
Because the objective function is convex around the median, one of these two candidates must be optimal.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(P × n) | O(P) | Evaluate every palindrome against the entire array |
| Optimal | O(P + n log n) | O(P) | Use median property and binary search among palindromes |
Here P denotes the number of palindromes below 10^9, approximately 110,000.
Algorithm Walkthrough
- Generate all palindromic numbers less than
10^9.
Instead of checking every integer, construct palindromes directly. For a chosen first half, mirror it to create both odd-length and even-length palindromes. 2. Sort the input array.
Sorting allows us to obtain the median efficiently. 3. Compute the median.
For an array of size n, use:
nums[n // 2]
Any median minimizes the unconstrained sum of absolute differences. 4. Binary search in the palindrome list.
Find the insertion position where the median would be placed among all palindromes. 5. Collect candidate palindromes.
The palindrome immediately before the insertion point and the palindrome at the insertion point are the closest palindromes surrounding the median. 6. Compute costs.
For each candidate palindrome p, compute:
cost = Σ |nums[i] - p|
- Return the smaller cost.
Since the objective is minimized at the median and grows as we move away, one of the two nearest palindromes must produce the minimum possible cost.
Why it works
The function
$$f(y)=\sum |nums[i]-y|$$
is convex and achieves its minimum at the median. When restricting y to palindromic values, the optimum feasible point must be the palindrome closest to the median. Any palindrome farther away from the median lies farther along a nondecreasing portion of the convex function and therefore cannot yield a smaller cost. Evaluating the nearest palindrome on each side of the median guarantees that the global optimum is found.
Python Solution
from typing import List
from bisect import bisect_left
class Solution:
def minimumCost(self, nums: List[int]) -> int:
palindromes = []
def add_palindrome(x: int) -> None:
if x < 1_000_000_000:
palindromes.append(x)
# Odd-length palindromes
for half in range(1, 100000):
s = str(half)
add_palindrome(int(s + s[-2::-1]))
# Even-length palindromes
for half in range(1, 100000):
s = str(half)
add_palindrome(int(s + s[::-1]))
palindromes.sort()
nums.sort()
median = nums[len(nums) // 2]
idx = bisect_left(palindromes, median)
answer = float("inf")
if idx < len(palindromes):
target = palindromes[idx]
answer = min(
answer,
sum(abs(x - target) for x in nums)
)
if idx > 0:
target = palindromes[idx - 1]
answer = min(
answer,
sum(abs(x - target) for x in nums)
)
return answer
The implementation begins by generating every palindrome smaller than 10^9. Rather than testing each number individually, it constructs palindromes directly by mirroring a prefix. Both odd-length and even-length palindromes are generated.
After sorting the palindrome list, the input array is sorted and its median is extracted.
A binary search locates where the median would appear in the palindrome sequence. The two neighboring palindromes around that position are the only candidates that can be optimal.
The cost for each candidate is computed by summing absolute differences across the array, and the minimum of those costs is returned.
Go Solution
package main
import (
"math"
"sort"
"strconv"
)
func minimumCost(nums []int) int64 {
palindromes := make([]int, 0)
addPalindrome := func(x int) {
if x < 1000000000 {
palindromes = append(palindromes, x)
}
}
for half := 1; half < 100000; half++ {
s := strconv.Itoa(half)
rev := ""
for i := len(s) - 2; i >= 0; i-- {
rev += string(s[i])
}
val, _ := strconv.Atoi(s + rev)
addPalindrome(val)
}
for half := 1; half < 100000; half++ {
s := strconv.Itoa(half)
rev := ""
for i := len(s) - 1; i >= 0; i-- {
rev += string(s[i])
}
val, _ := strconv.Atoi(s + rev)
addPalindrome(val)
}
sort.Ints(palindromes)
sort.Ints(nums)
median := nums[len(nums)/2]
idx := sort.SearchInts(palindromes, median)
answer := int64(math.MaxInt64)
if idx < len(palindromes) {
target := palindromes[idx]
var cost int64
for _, x := range nums {
if x > target {
cost += int64(x - target)
} else {
cost += int64(target - x)
}
}
if cost < answer {
answer = cost
}
}
if idx > 0 {
target := palindromes[idx-1]
var cost int64
for _, x := range nums {
if x > target {
cost += int64(x - target)
} else {
cost += int64(target - x)
}
}
if cost < answer {
answer = cost
}
}
return answer
}
The Go implementation follows exactly the same strategy. The primary difference is that int64 is used for the accumulated cost because the total cost can exceed the range of a 32-bit integer. Go's sort.SearchInts provides the binary search functionality corresponding to Python's bisect_left.
Worked Examples
Example 1
nums = [1,2,3,4,5]
After sorting:
| Index | Value |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
| 4 | 5 |
Median:
| Value |
|---|
| 3 |
Binary search among palindromes finds:
| Candidate |
|---|
| 3 |
Cost:
| Element | Contribution |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 0 |
| 4 | 1 |
| 5 | 2 |
Total:
2 + 1 + 0 + 1 + 2 = 6
Answer:
6
Example 2
nums = [10,12,13,14,15]
Sorted array:
| Value |
|---|
| 10 |
| 12 |
| 13 |
| 14 |
| 15 |
Median:
13
Nearest palindromes:
| Left | Right |
|---|---|
| 11 | 22 |
Cost for 11:
| Element | Contribution |
|---|---|
| 10 | 1 |
| 12 | 1 |
| 13 | 2 |
| 14 | 3 |
| 15 | 4 |
Total:
11
Cost for 22:
12 + 10 + 9 + 8 + 7 = 46
Minimum:
11
Example 3
nums = [22,33,22,33,22]
Sorted:
[22,22,22,33,33]
Median:
22
Since 22 is already a palindrome:
Cost:
| Element | Contribution |
|---|---|
| 22 | 0 |
| 22 | 0 |
| 22 | 0 |
| 33 | 11 |
| 33 | 11 |
Total:
22
Answer:
22
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(P + n log n) | Generate palindromes once, sort array, evaluate two candidates |
| Space | O(P) | Store all palindromic numbers below 10^9 |
The number of palindromes below 10^9 is approximately 110,000, which is effectively a small constant relative to the input size. The dominant term is sorting the array, which requires O(n log n) time. Only two candidate palindromes are evaluated, so the cost computation remains linear.
Test Cases
sol = Solution()
assert sol.minimumCost([1, 2, 3, 4, 5]) == 6 # example 1
assert sol.minimumCost([10, 12, 13, 14, 15]) == 11 # example 2
assert sol.minimumCost([22, 33, 22, 33, 22]) == 22 # example 3
assert sol.minimumCost([1]) == 0 # single palindromic value
assert sol.minimumCost([10]) == 1 # nearest palindrome is 9 or 11
assert sol.minimumCost([11, 11, 11]) == 0 # already equalindromic
assert sol.minimumCost([9, 9, 9, 9]) == 0 # all equal palindrome
assert sol.minimumCost([8, 9, 10]) == 2 # median already palindrome
assert sol.minimumCost([100, 100, 100]) == 1 # nearest palindrome 99 or 101
assert sol.minimumCost([1000000000, 1000000000]) == 2 # near upper limit
assert sol.minimumCost([1, 1000000000]) > 0 # large spread
assert sol.minimumCost([123, 456, 789]) >= 0 # general case
assert sol.minimumCost([999999999]) == 0 # largest valid palindrome
Test Summary
| Test | Why |
|---|---|
[1,2,3,4,5] |
Basic odd-length example |
[10,12,13,14,15] |
Median is not palindromic |
[22,33,22,33,22] |
Median already palindrome |
[1] |
Smallest array size |
[10] |
Single non-palindromic value |
[11,11,11] |
Already equalindromic |
[9,9,9,9] |
Repeated palindrome |
[8,9,10] |
Median candidate exactly optimal |
[100,100,100] |
Closest palindrome search |
[1000000000,1000000000] |
Near upper constraint |
[1,1000000000] |
Extremely wide range |
[123,456,789] |
Generic mixed values |
[999999999] |
Largest palindrome under limit |
Edge Cases
Median Is Already a Palindrome
An easy mistake is to continue searching for other palindromes even when the median itself is valid. Since the unconstrained optimum is the median, if the median is palindromic then it is immediately the best feasible target. The implementation naturally handles this because the binary search candidate can be exactly the median.
Median Lies Between Two Palindromes
Consider a median value such as 13, where the nearest palindromes are 11 and 22. A solution that checks only the lower palindrome or only the upper palindrome may miss the optimum. The implementation always evaluates both neighboring palindromes and takes the minimum cost.
Values Near the Upper Bound
The target palindrome must be strictly less than 10^9. When generating palindromes, values greater than or equal to 10^9 must not be included. The implementation explicitly filters them out, ensuring every candidate satisfies the problem constraints.
Single Element Arrays
When n = 1, the median is simply the only value. The answer becomes the distance from that value to the nearest valid palindrome. The algorithm still works because binary search identifies the neighboring palindromes and evaluates them normally.
Large Duplicate Blocks
Arrays containing many identical values can expose inefficiencies in brute-force methods. The optimal solution remains efficient because sorting handles duplicates naturally and only two palindrome candidates are evaluated regardless of how many repeated values exist.