Minimum Cost to Make Array Equalindromic

Med

#2647Time: O(K * n), where K is the number of palindromes and n is the length of `nums`. With K ≈ 10^5 and n ≤ 10^5, the complexity is roughly O(10^10), which is not feasible.Space: O(K), where K is the number of palindromes generated. K is approximately 10^5 for palindromes up to 10^9.

Patterns

Math Greedy

Algorithms

Binary Search Sorting

Data structures

Array

Prompt

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 10⁹.

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 <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating all possible palindromic numbers up to a certain limit (e.g., slightly above 10^9). Then, for each generated palindrome, we calculate the total cost to make all elements in nums equal to this palindrome. We keep track of the minimum cost found across all palindromes.

Algorithm

Generate a list of all palindromic numbers up to a reasonable upper bound (e.g., 10^9 + 10^5).
Initialize minCost to a very large value (e.g., Long.MAX_VALUE).
Iterate through each palindrome p in the generated list.
For each p, calculate the total cost to change all elements of nums to p. The cost is currentCost = sum(|num - p| for num in nums).
Update minCost with the minimum cost found so far: minCost = min(minCost, currentCost).
After checking all palindromes, return minCost.

Walkthrough

The brute-force method systematically checks every potential palindromic target value y. First, we need a way to get all palindromes. We can generate them by taking a number, converting it to a string, and appending its reverse (with a slight modification for odd/even length palindromes). We would generate all palindromes up to a certain bound (the maximum possible value in nums plus some buffer). For each of these palindromes, we iterate through the entire nums array, summing up the absolute differences |nums[i] - y|. This sum represents the cost for a given palindrome y. We maintain a variable to store the minimum cost seen so far and update it whenever a smaller cost is found. While straightforward, this method is computationally expensive because the number of palindromes is large, and for each one, we perform a linear scan of the input array.

Complexity

Time

O(K * n), where K is the number of palindromes and n is the length of `nums`. With K ≈ 10^5 and n ≤ 10^5, the complexity is roughly O(10^10), which is not feasible.

Space

O(K), where K is the number of palindromes generated. K is approximately 10^5 for palindromes up to 10^9.

Trade-offs

Pros

Simple to conceptualize and implement.

Cons

Extremely inefficient due to the large number of palindromes to check and the cost calculation for each.
Will result in a 'Time Limit Exceeded' error for the given constraints.

The core idea is that the cost function C(y) = sum(|nums[i] - y|) is minimized when y is the median of the array nums. Since y must be a palindrome, the optimal palindromic value y must be one of the two palindromes closest to the median. This approach first finds the median of nums by sorting the array. Then, it finds the largest palindrome less than or equal to the median and the smallest palindrome greater than or equal to the median. Finally, it calculates the cost for these two palindromic candidates and returns the minimum of the two.

Algorithm

Sort the input array nums.
Determine the median of the array. If n is odd, the median m is nums[n/2]. If n is even, the median can be taken as nums[n/2] (or any value in the median interval).
Find the largest palindrome p1 that is less than or equal to the median m. This can be done by starting from m and decrementing until a palindrome is found.
Find the smallest palindrome p2 that is greater than or equal to the median m. This can be done by starting from m and incrementing until a palindrome is found.
Calculate the cost to make all elements equal to p1: cost1 = sum(|nums[i] - p1|).
Calculate the cost to make all elements equal to p2: cost2 = sum(|nums[i] - p2|).
The result is the minimum of cost1 and cost2.

Walkthrough

This approach leverages a key mathematical property: the sum of absolute differences to a point is minimized when that point is the median of the data set. Our target value y must be a palindrome, so it might not be the exact median. However, because the cost function C(y) is convex, the optimal palindromic y must be one of the two palindromes that are closest to the true median.

The algorithm proceeds as follows:

Sort the nums array to easily find the median. This takes O(n log n) time.
The median is nums[n/2].
We then search for the two palindromic candidates that bracket the median. p1 is found by decrementing from the median, and p2 is found by incrementing.
We compute the total cost for both p1 and p2 and return the smaller one.

1import java.util.Arrays;2 3class Solution {4    public long minimumCost(int[] nums) {5        Arrays.sort(nums);6        int n = nums.length;7        long median = (n % 2 == 1) ? nums[n / 2] : (long)(nums[n / 2 - 1] + nums[n / 2]) / 2;8 9        long p1 = findLowerPalindrome(median);10        long p2 = findUpperPalindrome(median);11 12        long cost1 = calculateCost(nums, p1);13        long cost2 = calculateCost(nums, p2);14 15        return Math.min(cost1, cost2);16    }17 18    private boolean isPalindrome(long n) {19        if (n < 0) return false;20        long original = n;21        long reversed = 0;22        while (n > 0) {23            reversed = reversed * 10 + n % 10;24            n /= 10;25        }26        return original == reversed;27    }28 29    private long findLowerPalindrome(long n) {30        while (!isPalindrome(n)) {31            n--;32        }33        return n;34    }35 36    private long findUpperPalindrome(long n) {37        while (!isPalindrome(n)) {38            n++;39        }40        return n;41    }42 43    private long calculateCost(int[] nums, long p) {44        long cost = 0;45        for (int num : nums) {46            cost += Math.abs(num - p);47        }48        return cost;49    }50}

Complexity

Time

O(n log n + G), where `n` is the number of elements and `G` is the search space for the nearest palindromes. The `O(n log n)` for sorting is the dominant factor.

Space

O(log n) or O(n), depending on the space complexity of the sorting algorithm used. Java's `Arrays.sort` for primitives has an average space complexity of O(log n).

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Correct and guaranteed to pass within the given time constraints.
Relatively easy to implement using standard library functions.

Cons

The time complexity is dominated by sorting, which is O(n log n). This can be improved upon.
The linear search for the nearest palindromes can be slow if the median is far from any palindrome, though the gaps between palindromes are not excessively large.

This approach is an optimization of the previous one. Instead of sorting the entire array to find the median, which takes O(n log n) time, we can use a selection algorithm like Quickselect to find the median in O(n) average time. Once the median is found, the rest of the logic remains the same: find the two nearest palindromes and calculate the minimum cost.

Algorithm

Find the median m of the nums array using a linear-time selection algorithm like Quickselect. This avoids a full sort.
Once the median m is found, identify the two nearest palindrome candidates: p1 (largest palindrome <= m) and p2 (smallest palindrome >= m).
This search can be optimized by constructing the palindromes from the digits of the median m rather than linear searching.
Calculate the costs for transforming the array to p1 and p2.
Return the minimum of the two costs.

Walkthrough

This is the most time-efficient approach. It refines the median-based method by optimizing the step of finding the median. A full sort is overkill when only the median element is required.

Median Finding: Use a selection algorithm (e.g., Quickselect) to find the median of nums in O(n) average time. This avoids the O(n log n) cost of sorting.
Palindrome Finding: After finding the median m, we still need the two closest palindromes. Instead of a simple linear search (incrementing/decrementing), we can directly construct them. We take the first half of the digits of m, form a palindrome, and compare it with m. Based on the comparison, we might need to adjust the first half (by +1 or -1) to find the other candidate. This finds the palindromes in O(log m) time.
Cost Calculation: As before, calculate the costs for the two palindrome candidates and return the minimum.

This combination of linear-time median finding and efficient palindrome construction leads to an overall O(n) time complexity.

1import java.util.Arrays;2 3class Solution {4    // The main method would use a Quickselect algorithm to find the median in O(n).5    // For brevity, we still use sort here to get the median, but the main idea of this6    // approach is to replace this with a faster selection algorithm.7    public long minimumCost(int[] nums) {8        Arrays.sort(nums);9        int n = nums.length;10        long median = (n % 2 == 1) ? nums[n / 2] : (long)(nums[n / 2 - 1] + nums[n / 2]) / 2;11 12        long p1 = findLowerPalindrome(median);13        long p2 = findUpperPalindrome(median);14 15        long cost1 = calculateCost(nums, p1);16        long cost2 = calculateCost(nums, p2);17 18        return Math.min(cost1, cost2);19    }20 21    // More efficient palindrome finders by construction22    private long findLowerPalindrome(long n) {23        String s = String.valueOf(n);24        int len = s.length();25        String halfStr = s.substring(0, (len + 1) / 2);26        long halfNum = Long.parseLong(halfStr);27        long p = createPalindrome(halfNum);28        if (p > n) {29            p = createPalindrome(halfNum - 1);30        }31        return p;32    }33 34    private long findUpperPalindrome(long n) {35        String s = String.valueOf(n);36        int len = s.length();37        String halfStr = s.substring(0, (len + 1) / 2);38        long halfNum = Long.parseLong(halfStr);39        long p = createPalindrome(halfNum);40        if (p < n) {41            p = createPalindrome(halfNum + 1);42        }43        return p;44    }45 46    private long createPalindrome(long half) {47        String s = String.valueOf(half);48        String reversedHalf = new StringBuilder(s).reverse().toString();49        String fullStr = s + reversedHalf.substring(s.length() % 2);50        return Long.parseLong(fullStr);51    }52 53    private long calculateCost(int[] nums, long p) {54        long cost = 0;55        for (int num : nums) {56            cost += Math.abs(num - p);57        }58        return cost;59    }60}

Complexity

Time

O(n). Finding the median takes O(n), finding palindromes takes O(log m), and calculating costs takes O(n). The total complexity is dominated by the linear scans.

Space

O(1) or O(log n), if the selection algorithm is implemented in-place or recursively.

Trade-offs

Pros

Theoretically optimal time complexity.
Most efficient for very large input arrays.

Cons

Implementing a robust, worst-case linear-time selection algorithm (like Median of Medians) is complex.
The practical performance gain over the O(n log n) solution might be small unless n is extremely large, as sorting algorithms are highly optimized in standard libraries.

Solutions

Solution

1public class Solution { private static long [] ps ; private int [] nums ; static { ps = new long [ 2 * ( int ) 1 e5 ]; for ( int i = 1 ; i <= 1 e5 ; i ++) { String s = Integer . toString ( i ); String t1 = new StringBuilder ( s ). reverse (). toString (); String t2 = new StringBuilder ( s . substring ( 0 , s . length () - 1 )). reverse (). toString (); ps [ 2 * i - 2 ] = Long . parseLong ( s + t1 ); ps [ 2 * i - 1 ] = Long . parseLong ( s + t2 ); } Arrays . sort ( ps ); } public long minimumCost ( int [] nums ) { this . nums = nums ; Arrays . sort ( nums ); int i = Arrays . binarySearch ( ps , nums [ nums . length / 2 ]); i = i < 0 ? - i - 1 : i ; long ans = 1L << 60 ; for ( int j = i - 1 ; j <= i + 1 ; j ++) { if ( 0 <= j && j < ps . length ) { ans = Math . min ( ans , f ( ps [ j ])); } } return ans ; } private long f ( long x ) { long ans = 0 ; for ( int v : nums ) { ans += Math . abs ( v - x ); } return ans ; } }

1using ll = long long ; ll ps [ 2 * 100000 ]; int init = [] { for ( int i = 1 ; i <= 100000 ; i ++ ) { string s = to_string ( i ); string t1 = s ; reverse ( t1 . begin (), t1 . end ()); string t2 = s . substr ( 0 , s . length () - 1 ); reverse ( t2 . begin (), t2 . end ()); ps [ 2 * i - 2 ] = stoll ( s + t1 ); ps [ 2 * i - 1 ] = stoll ( s + t2 ); } sort ( ps , ps + 2 * 100000 ); return 0 ; }(); class Solution { public: long long minimumCost ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int i = lower_bound ( ps , ps + 2 * 100000 , nums [ nums . size () / 2 ]) - ps ; auto f = [ & ]( ll x ) { ll ans = 0 ; for ( int & v : nums ) { ans += abs ( v - x ); } return ans ; }; ll ans = LLONG_MAX ; for ( int j = i - 1 ; j <= i + 1 ; j ++ ) { if ( 0 <= j && j < 2 * 100000 ) { ans = min ( ans , f ( ps [ j ])); } } return ans ; } };

1ps = [] 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 ))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution { private static long [] ps ; private int [] nums ; static { ps = new long [ 2 * ( int ) 1 e5 ]; for ( int i = 1 ; i <= 1 e5 ; i ++) { String s = Integer . toString ( i ); String t1 = new StringBuilder ( s ). reverse (). toString (); String t2 = new StringBuilder ( s . substring ( 0 , s . length () - 1 )). reverse (). toString (); ps [ 2 * i - 2 ] = Long . parseLong ( s + t1 ); ps [ 2 * i - 1 ] = Long . parseLong ( s + t2 ); } Arrays . sort ( ps ); } public long minimumCost ( int [] nums ) { this . nums = nums ; Arrays . sort ( nums ); int i = Arrays . binarySearch ( ps , nums [ nums . length / 2 ]); i = i < 0 ? - i - 1 : i ; long ans = 1L << 60 ; for ( int j = i - 1 ; j <= i + 1 ; j ++) { if ( 0 <= j && j < ps . length ) { ans = Math . min ( ans , f ( ps [ j ])); } } return ans ; } private long f ( long x ) { long ans = 0 ; for ( int v : nums ) { ans += Math . abs ( v - x ); } return ans ; } }

1using ll = long long ; ll ps [ 2 * 100000 ]; int init = [] { for ( int i = 1 ; i <= 100000 ; i ++ ) { string s = to_string ( i ); string t1 = s ; reverse ( t1 . begin (), t1 . end ()); string t2 = s . substr ( 0 , s . length () - 1 ); reverse ( t2 . begin (), t2 . end ()); ps [ 2 * i - 2 ] = stoll ( s + t1 ); ps [ 2 * i - 1 ] = stoll ( s + t2 ); } sort ( ps , ps + 2 * 100000 ); return 0 ; }(); class Solution { public: long long minimumCost ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int i = lower_bound ( ps , ps + 2 * 100000 , nums [ nums . size () / 2 ]) - ps ; auto f = [ & ]( ll x ) { ll ans = 0 ; for ( int & v : nums ) { ans += abs ( v - x ); } return ans ; }; ll ans = LLONG_MAX ; for ( int j = i - 1 ; j <= i + 1 ; j ++ ) { if ( 0 <= j && j < 2 * 100000 ) { ans = min ( ans , f ( ps [ j ])); } } return ans ; } };

1ps = [] 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 ))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.