#2967

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Cost to Make Array Equalindromic

Determine the minimum cost to convert an integer array into a palindromic array using allowed element modifications efficiently.

array math binary search greedy sorting

Problem Statement

Given a 0-indexed integer array nums of length n, you can perform a special move any number of times. In each move, you can change any element to a positive palindromic integer.

A palindromic number reads the same forwards and backwards, such as 121 or 65756. Your task is to compute the minimum total cost to transform nums into an array where all elements are equal to the same palindromic number.

Examples

Example 1

Input: nums = [1,2,3,4,5]

Output: 6

We can make the array equalindromic by changing all elements to 3 which is a palindromic number. The cost of changing the array to [3,3,3,3,3] using 4 special moves is given by |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6. It can be shown that changing all elements to any palindromic number other than 3 cannot be achieved at a lower cost.

Example 2

Input: nums = [10,12,13,14,15]

Output: 11

We can make the array equalindromic by changing all elements to 11 which is a palindromic number. The cost of changing the array to [11,11,11,11,11] using 5 special moves is given by |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11. It can be shown that changing all elements to any palindromic number other than 11 cannot be achieved at a lower cost.

Example 3

Input: nums = [22,33,22,33,22]

Output: 22

We can make the array equalindromic by changing all elements to 22 which is a palindromic number. The cost of changing the array to [22,22,22,22,22] using 2 special moves is given by |33 - 22| + |33 - 22| = 22. It can be shown that changing all elements to any palindromic number other than 22 cannot be achieved at a lower cost.

Constraints

1 <= n <= 105
1 <= nums[i] <= 109

Solution Approach

Identify Palindromic Candidates

Generate or identify relevant palindromic numbers that could serve as targets. Focus on numbers near the median of the array to reduce total cost.

Compute Cost Efficiently

For each candidate palindromic number, calculate the sum of absolute differences to all array elements. Keep track of the minimum total cost encountered.

Use Binary Search over Target Space

Apply binary search on sorted unique palindromic numbers within the range of array values. This leverages the problem pattern of searching over valid answers for an optimal cost.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is dominated by sorting the array O(n log n) and evaluating candidate palindromic numbers, which can be bounded by O(log(max(nums)) * n). Space complexity depends on storing candidates, usually O(n) or less.

What Interviewers Usually Probe

Focus on array median and its relation to minimizing total distance.
Recognize the palindromic constraint restricts valid target numbers.
Binary search over the answer space is expected for efficiency.

Common Pitfalls or Variants

Common pitfalls

Ignoring that the optimal target must be palindromic and choosing any median value.
Recomputing costs from scratch for each candidate instead of using cumulative sums or efficient methods.
Not considering edge cases where multiple palindromic numbers yield the same minimal cost.

Follow-up variants

Allow changing elements to any number, removing the palindromic restriction, which simplifies to standard median minimization.
Compute the minimum cost when only a limited number of special moves are allowed.
Consider arrays where elements are initially palindromic and only some need adjustment.

FAQ

What is the key pattern used in Minimum Cost to Make Array Equalindromic?

The main pattern is binary search over the valid answer space of palindromic numbers combined with median-based optimization.

Why use the median for selecting candidate palindromic numbers?

The median minimizes the sum of absolute differences for the array, which aligns with the minimal total cost goal.

Can I pick any number as the target?

No, the target must be a palindromic number; choosing a non-palindromic median will violate the problem constraint.

How do I efficiently generate palindromic candidates?

Focus on numbers within the min and max of the array, and generate palindromes by mirroring digits around the center.

Does the array length affect the approach?

Yes, longer arrays require careful sorting and binary search to avoid O(n^2) operations; the approach scales to n up to 10^5.

terminal

Solution

Solution 1: Preprocessing + Sorting + Binary Search

The range of palindrome numbers in the problem is $[1, 10^9]$. Due to the symmetry of palindrome numbers, we can enumerate in the range of $[1, 10^5]$, then reverse and concatenate them to get all palindrome numbers. Note that if it is an odd-length palindrome number, we need to remove the last digit before reversing. The array of palindrome numbers obtained by preprocessing is denoted as $ps$. We sort the array $ps$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

ps = []
for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]
    t2 = s[:-1][::-1]
    ps.append(int(s + t1))
    ps.append(int(s + t2))
ps.sort()


class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        def f(x: int) -> int:
            return sum(abs(v - x) for v in nums)

        nums.sort()
        i = bisect_left(ps, nums[len(nums) // 2])
        return min(f(ps[j]) for j in range(i - 1, i + 2) if 0 <= j < len(ps))

Continue Practicing

#2790 maximum number of groups with increasing length #2818 apply operations to maximize score #2659 make array empty