Largest Palindromic Number solution and explanation
9 more videos on this problem
LARGEST PALINDROMIC NUMBER | LEETCODE 2384 | PYTHON SOLUTIONCracking FAANG · 14:56 · 3K views
2384. Largest Palindromic Number (Leetcode Medium)Programming Live with Larry · 11:33 · 1K views
2384. Largest Palindromic Number || Leetcode Contest Medium || CPP || Most intuitive solution 🤩🤩Coding Techniques with Komal | Newton School · 11:26 · 1K views
Leetcode Weekly contest 307 - Medium - Largest Palindromic NumberPrakhar Agrawal · 10:38 · 1K views
[Leetcode-WC-307] Largest Palindromic NumberSandeep Kumar · 7:32 · 1K views
2384. Largest Palindromic Number || leetcode Weekly 307 || Leetcode MediumBinaryMagic · 22:08 · 834 views
Leetcode Weekly Contest 307 | Largest Palindromic Number | Medium | ExplainedCoding with Jenish · 13:14 · 364 views
Largest Palindromic Number - Leetcode 2384 - PythonNotesByPravat · 3:44 · 346 views
2384. Largest Palindromic Number || JAVA Code || C++ Code || LeetCode || Hindi ||Code - गुरू · 12:21 · 330 views
Leetcode 2384. Largest Palindromic Number (greedy)LetsCode · 10:34 · 116 views
The problem
You are given a string num consisting of digits only.
Return the largest palindromic integer (in the form of a string) that can be formed using digits taken from num. It should not contain leading zeroes.
Notes:
- You do not need to use all the digits of
num, but you must use at least one digit. - The digits can be reordered.
Example 1:
Input: num = "444947137" Output: "7449447" Explanation: Use the digits "4449477" from "444947137" to form the palindromic integer "7449447". It can be shown that "7449447" is the largest palindromic integer that can be formed.
Example 2:
Input: num = "00009" Output: "9" Explanation: It can be shown that "9" is the largest palindromic integer that can be formed. Note that the integer returned should not contain leading zeroes.
Constraints:
1 <= num.length <= 105numconsists of digits.
Approach overview
Problem Overview: You are given a string of digits. Rearrange some or all digits to form the numerically largest palindromic number. Each digit can be used at most as many times as it appears in the input, and the result cannot contain leading zeros unless the entire palindrome is "0".
Approach 1: Frequency Count and Greedy Construction (Time: O(n), Space: O(1))
This approach counts how many times each digit appears, then greedily builds the palindrome from the largest digits down. Use a frequency array or map (a classic Hash Table / Counting technique) to track occurrences of digits 0–9. For every digit from 9 to 0, place count[d] / 2 copies on the left side of the palindrome. These will later be mirrored to the right side. If any digit still has one leftover occurrence, choose the largest such digit as the middle character.
The key constraint is avoiding leading zeros. If the current left half is empty, skip adding pairs of '0'. This prevents results like "000..." when larger digits exist. After building the left half, mirror it and insert the chosen middle digit if one exists. This greedy ordering ensures the final palindrome is numerically maximal. Because the digit range is fixed (0–9), counting and construction run in linear time with constant auxiliary space.
Approach 2: Two Pointer Merge Technique (Time: O(n log n), Space: O(n))
This method first sorts the digits so larger values are processed earlier. After sorting, use a two pointers style merge strategy: one pointer scans from the start while another groups identical digits from the end. Whenever a pair of the same digit is found, append one to the left half and reserve the other for the mirrored side. Digits without pairs are candidates for the center position of the palindrome.
Sorting simplifies grouping but increases time complexity to O(n log n). After pairing digits, track the largest unpaired digit to place in the middle. Finally concatenate left + middle + reverse(left). This approach is straightforward in languages where sorting strings or arrays is convenient, though it uses extra memory for the sorted structure.
Recommended for interviews: The frequency-count greedy solution is what most interviewers expect. It shows you recognize the fixed digit range and can exploit counting for linear performance. Explaining the pairing logic and the rule that prevents leading zeros demonstrates strong understanding of Greedy construction and palindrome structure.
Approach 1: Frequency Count and Greedy Construction
This approach involves counting the frequency of each digit in the string. We then determine the maximum possible digits that can form the palindromic structure by utilizing greedy principles. The highest digits available will be used to maximize the number, ensuring no leading zeroes.
def largestPalindromic(num):
counts = [0] * 10
for digit in num:
counts[int(digit)] += 1
left_half = []
mid = ''
for digit in range(9, -1, -1):
if digit == 0 and not left_half:
continue
while counts[digit] >= 2:
left_half.append(str(digit))
counts[digit] -= 2
for digit in range(9, -1, -1):
if counts[digit] > 0:
mid = str(digit)
break
result = ''.join(left_half) + mid + ''.join(reversed(left_half))
return '0' if result == '' else result
num = "444947137"
print(largestPalindromic(num))function largestPalindromic(num) {
const counts = new Array(10).fill(0);
for (let digit of num) {
counts[digit]++;
}
let left_half = [];
let mid = '';
for (let digit = 9; digit >= 0; --digit) {
if (digit === 0 && left_half.length === 0) {
continue;
}
while (counts[digit] >= 2) {
left_half.push(digit);
counts[digit] -= 2;
}
}
for (let digit = 9; digit >= 0; --digit) {
if (counts[digit] > 0) {
mid = String(digit);
break;
}
}
const result = left_half.join('') + mid + left_half.reverse().join('');
return result === '' ? '0' : result;
}
const num = "444947137";
console.log(largestPalindromic(num));The function begins by counting all digits in the given number string. It then collects pairs of digits to form the left and right halves of the palindrome. The 'middle' is the largest possible digit that can appear in the center if any single digit remains unpaired. The result string is formed by joining the left-half, the middle digit, and the inverse of the left-half. Leading zeroes are avoided by skipping over zeros when left-half is empty.
Time Complexity: O(n) where n is the length of the input string. We traverse the input once to count, then traverse a fixed range of 10 to construct the palindrome.
Space Complexity: O(1), apart from the output, because the frequency array size and other variables do not depend on input size.
Approach 2: Two Pointer Merge Technique
We use a two-pointer approach to sort and find the largest palindromic number. By sorting the digits in descending order, palindromic sequences are attempted from both ends, ensuring to skip zeroes to avoid leading zeros.
import java.util.Arrays;
public class LargestPalindromic {
public static String largestPalindromic(String num) {
int[] counts = new int[10];
for (char c : num.toCharArray()) {
counts[c - '0']++;
}
StringBuilder left = new StringBuilder();
String mid = "";
for (int i = 9; i >= 0; i--) {
if (i == 0 && left.length() == 0) continue;
while (counts[i] > 1) {
left.append(i);
counts[i] -= 2;
}
}
for (int i = 9; i >= 0; i--) {
if (counts[i] > 0) {
mid = String.valueOf(i);
break;
}
}
String result = left.toString() + mid + left.reverse().toString();
return result.isEmpty() ? "0" : result;
}
public static void main(String[] args) {
String num = "444947137";
System.out.println(largestPalindromic(num));
}
}using System;
using System.Text;
public class LargestPalindromic {
public static string LargestPalindromicNumber(string num) {
int[] counts = new int[10];
foreach (char c in num) {
counts[c - '0']++;
}
StringBuilder leftHalf = new StringBuilder();
string mid = "";
for (int i = 9; i >= 0; i--) {
if (i == 0 && leftHalf.Length == 0) continue;
while (counts[i] >= 2) {
leftHalf.Append(i);
counts[i] -= 2;
}
}
for (int i = 9; i >= 0; i--) {
if (counts[i] > 0) {
mid = i.ToString();
break;
}
}
string result = leftHalf.ToString() + mid + new string(leftHalf.ToString().Reverse().ToArray());
return result.Length == 0 ? "0" : result;
}
public static void Main() {
string num = "444947137";
Console.WriteLine(LargestPalindromicNumber(num));
}
}This Java implementation uses a frequency array to count each digit. We form the palindrome by attempting to build a string from the highest digits while maintaining symmetry using a two-pointer mechanism. The largest unused digit may be placed in the middle if possible. Forming the output ensures no leading zeros are present by skipping initial zeros.
Time Complexity: O(n), as the string is traversed to fill the frequency array and to construct the palindrome.
Space Complexity: O(1), extra space use is minimal and constant.
Approach 3: Default Approach
class Solution {
public:
string largestPalindromic(string num) {
vector<int> cnt(10);
for (char c : num) ++cnt[c - '0'];
string mid = "";
for (int i = 9; ~i; --i) {
if (cnt[i] % 2) {
mid += (i + '0');
--cnt[i];
break;
}
}
string t = "";
for (int i = 0; i < 10; ++i) {
if (cnt[i]) {
cnt[i] >>= 1;
while (cnt[i]--) {
t += (i + '0');
}
}
}
while (t.size() && t.back() == '0') {
t.pop_back();
}
string ans = t;
reverse(ans.begin(), ans.end());
ans += mid + t;
return ans == "" ? "0" : ans;
}
};function largestPalindromic(num: string): string {
const count = new Array(10).fill(0);
for (const c of num) {
count[c]++;
}
while (count.reduce((r, v) => (v % 2 === 1 ? r + 1 : r), 0) > 1) {
for (let i = 0; i < 10; i++) {
if (count[i] % 2 === 1) {
count[i]--;
break;
}
}
}
let res = [];
let oddIndex = -1;
for (let i = 9; i >= 0; i--) {
if (count[i] % 2 == 1) {
oddIndex = i;
count[i] -= 1;
}
res.push(...new Array(count[i] >> 1).fill(i));
}
if (oddIndex !== -1) {
res.push(oddIndex);
}
const n = res.length;
for (let i = 0; i < n; i++) {
if (res[i] !== 0) {
res = res.slice(i);
if (oddIndex !== -1) {
res.push(...[...res.slice(0, res.length - 1)].reverse());
} else {
res.push(...[...res].reverse());
}
return res.join('');
}
}
return '0';
}func largestPalindromic(num string) string {
cnt := make([]int, 10)
for _, c := range num {
cnt[c-'0']++
}
ans := ""
for i := 9; i >= 0; i-- {
if cnt[i]%2 == 1 {
ans = strconv.Itoa(i)
cnt[i]--
break
}
}
for i := 0; i < 10; i++ {
if cnt[i] > 0 {
cnt[i] >>= 1
s := strings.Repeat(strconv.Itoa(i), cnt[i])
ans = s + ans + s
}
}
ans = strings.Trim(ans, "0")
if ans == "" {
return "0"
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Frequency Count and Greedy Construction | Time Complexity: O(n) where n is the length of the input string. We traverse the input once to count, then traverse a fixed range of 10 to construct the palindrome. |
| Two Pointer Merge Technique | Time Complexity: O(n), as the string is traversed to fill the frequency array and to construct the palindrome. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count and Greedy Construction | O(n) | O(1) | Best general solution. Uses digit frequency and greedy pairing for optimal performance. |
| Two Pointer Merge Technique | O(n log n) | O(n) | Useful when digits are already sorted or when implementing pair grouping after sorting. |
Frequently asked questions
Is Largest Palindromic Number easy or hard?
Largest Palindromic Number is rated Medium difficulty on LeetCode with an acceptance rate around 37%. The challenge lies in constructing the largest numeric palindrome while handling edge cases such as leading zeros and choosing the correct center digit.
Largest Palindromic Number Python/Java solution
Python and JavaScript implementations typically use a frequency counter and string builder to construct the left half, select a middle digit, and mirror the result. Java and C# solutions often use sorted arrays with two-pointer grouping or the same counting strategy.
How to solve Largest Palindromic Number in O(n)?
Use a counting approach. Create a frequency array for digits 0–9, then greedily append digit pairs from 9 down to 0 to form the left half of the palindrome. Select the largest remaining digit as the middle if one exists, and mirror the left half to complete the palindrome. Skip leading zero pairs unless the result would otherwise be empty.
What is the best approach for Largest Palindromic Number?
The frequency count with greedy construction is the optimal approach. Count occurrences of each digit, add pairs of digits from 9 down to 0 to build the left half, and mirror it. If a digit remains unpaired, place the largest one in the center. This method runs in O(n) time with O(1) space because only digits 0–9 are tracked.
Is Largest Palindromic Number asked at Google/Amazon/Meta?
Palindrome construction and greedy digit problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving digit rearrangement, counting frequencies, or building palindromes are common because they test greedy reasoning and string manipulation.
What data structure is used in Largest Palindromic Number?
A frequency array or hash table is the primary data structure. It stores how many times each digit appears, enabling efficient pairing of digits when constructing the palindrome. Strings or character arrays are then used to build the final result.
What is the time complexity of Largest Palindromic Number?
The optimal solution runs in O(n) time where n is the length of the digit string. Counting frequencies takes one pass and constructing the palindrome requires iterating through digits 0–9. Space complexity is O(1) because the frequency array size is constant.