Skip to main content
Talentd

Minimum Cost to Make Array Equalindromic - Solution & Explanation

MediumArrayMathBinary SearchGreedy15 min readAsked at: Google
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums having length n.

You are allowed to perform a special move any number of times (including zero) on nums. In one special move you perform the following steps in order:

  • Choose an index i in the range [0, n - 1], and a positive integer x.
  • Add |nums[i] - x| to the total cost.
  • Change the value of nums[i] to x.

A palindromic number is a positive integer that remains the same when its digits are reversed. For example, 121, 2552 and 65756 are palindromic numbers whereas 24, 46, 235 are not palindromic numbers.

An array is considered equalindromic if all the elements in the array are equal to an integer y, where y is a palindromic number less than 109.

Return an integer denoting the minimum possible total cost to make nums equalindromic by performing any number of special moves.

 

Example 1:

Input: nums = [1,2,3,4,5]
Output: 6
Explanation: 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
Explanation: 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
Explanation: 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

Approach Overview

Problem Overview: You are given an integer array and can change every element to the same value. The catch: the final value must be a palindromic number. The cost of converting an element is |nums[i] - target|. Your task is to choose a palindromic target that minimizes the total cost.

Approach 1: Brute Force with Palindromic Number List (O(P * n) time, O(P) space)

Generate all palindromic numbers within the valid integer range (up to 1e9). Store them in a list. For each palindrome p, iterate through the array and compute the total cost sum(|nums[i] - p|). Track the minimum cost across all candidates. This works because the valid targets are restricted to palindromes, but the search space can still contain tens of thousands of numbers. The method is straightforward and easy to implement, but it becomes expensive since each palindrome requires a full pass through the array.

This approach relies mostly on sequential iteration over an array. It demonstrates the brute-force baseline clearly and guarantees correctness because every valid palindromic target is tested.

Approach 2: Median + Nearest Palindrome Search (O(n log n + n) time, O(P) space)

The key observation comes from the property of absolute differences: the sum sum(|nums[i] - x|) is minimized when x is the median of the array. Start by sorting the array to find its median using sorting. The optimal target without constraints would be this median. Since the target must be a palindrome, search for the closest palindromic numbers around the median.

Precompute the sorted list of palindromes. Use binary search to find the palindrome closest to the median. Typically, only a few candidates around that position (the nearest lower and higher palindromes) need evaluation. Compute the cost for these candidates and choose the minimum.

This drastically reduces the search space because you no longer evaluate every palindrome. Instead, you leverage the convex nature of the absolute difference function around the median.

Recommended for interviews: The median-based approach with a palindrome search is what interviewers expect. The brute force version proves you understand the constraint that the target must be palindromic. The optimized approach shows deeper insight into how absolute deviation behaves and how to combine that with binary search over candidate palindromes.

Approach 1: Brute Force with Palindromic Number List

This approach involves generating all possible palindromic numbers up to a specified limit and calculating the cost of converting the entire array to each of these palindromic numbers. The minimum cost among all conversions is the desired solution.

The key steps are:
- Generate all potential palindromic numbers up to 109.
- For each palindromic number, calculate the total cost to convert all elements in nums into this number.
- Keep track of the minimal cost encountered during these calculations.

The implemented code generates all possible palindromic numbers below 109 and iterates through each palindromic number to calculate the total cost of converting the entire array to this number. generate_palindromes constructs these numbers by mirroring the digits, both odd and even-length variations, then sorts through this list for any values below 109.

Next, min_cost_to_equalindromic iterates over these generated palindromes, computes the cost for each, and keeps track of the minimum found.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * k), where n is the number of elements in the input array, and k is the number of palindromic numbers generated and considered.
Space Complexity: O(k), for storing palindromic numbers.

Try this approach in the editor →

Approach 2: 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.

Next, we sort the array nums and take the median x of nums. We only need to find a number in the palindrome array ps that is closest to x through binary search, and then calculate the cost of nums becoming this number to get the answer.

The time complexity is O(n times log n), and the space complexity is O(M). Here, n is the length of the array nums, and M is the length of the palindrome array ps.

Similar problems:

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with Palindromic Number List

Time Complexity: O(n * k), where n is the number of elements in the input array, and k is the number of palindromic numbers generated and considered.
Space Complexity: O(k), for storing palindromic numbers.

Preprocessing + Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Palindromic Number ListO(P * n)O(P)Good baseline approach when constraints are small or when demonstrating correctness first.
Median + Nearest Palindrome SearchO(n log n + n)O(P)Preferred solution for large arrays. Uses sorting and evaluates only the closest palindrome candidates.

Video Solution

2967 Minimum Cost to Make Array Equalindromic || (Median ✅) (why Mean❓ and Range Till 10^4 🙋‍♂️) • Ayush Rao • 1,698 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Cost to Make Array Equalindromic easy or hard?
This problem is rated Medium because the brute-force idea is simple but the optimal solution requires recognizing that absolute difference sums are minimized at the median. Combining that insight with palindrome generation and binary search makes it a multi-concept problem.
Minimum Cost to Make Array Equalindromic Python/Java solution
The typical implementation generates all palindromes up to the limit, sorts the input array, finds the median, then checks the nearest palindromes using binary search. For each candidate, compute the sum of absolute differences. Both Python and Java implementations follow the same logic with O(n log n) complexity.
How to solve Minimum Cost to Make Array Equalindromic in O(n)?
A strict O(n) solution is difficult because the typical approach requires sorting to obtain the median. However, if the median could be found in linear time using a selection algorithm, the remaining computation would still require evaluating candidate palindromes in O(n). In practice, the accepted solution is O(n log n).
What is the best approach for Minimum Cost to Make Array Equalindromic?
The most efficient approach uses the median of the array combined with a search for the nearest palindromic number. Since the sum of absolute differences is minimized at the median, you sort the array, find the median, and evaluate the closest palindromes around it. This reduces the search space dramatically and runs in O(n log n) time due to sorting.
Is Minimum Cost to Make Array Equalindromic asked at Google/Amazon/Meta?
Problems involving minimizing absolute differences, medians, and constrained target values appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying concepts—median optimization, greedy reasoning, and candidate pruning—are common interview patterns.
What data structure is used in Minimum Cost to Make Array Equalindromic?
The main data structures are arrays and a precomputed list of palindromic numbers. Sorting is used to find the median, and binary search helps locate the closest palindrome candidates efficiently.
What is the time complexity of Minimum Cost to Make Array Equalindromic?
The optimized solution runs in O(n log n) time because the array must be sorted to find the median. After that, only a few nearby palindromes are evaluated, each costing O(n) to compute the total absolute difference. Space complexity is O(P) to store precomputed palindromic numbers.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Minimum Cost to Make Array Equal

Next

Minimum Moves to Equal Array Elements II