Definition
- Largest Number – arrange a list of non-negative integers so their concatenation forms the biggest possible number.
- Custom comparator – for any two numbers a and b, compare the string a+b against b+a; the one producing the larger string comes first.
- Equal-length trick – both concatenations have identical length, so lexicographic string comparison equals numeric comparison, avoiding overflow.
- Transitivity – the a+b vs b+a relation is transitive, making it a valid total order for a standard sort.
- All-zeros guard – if the input is all zeros, return the single string "0" instead of "000".
The National Bank of India wants to stitch a set of branch codes into the single largest possible identifier for a priority label. The surprising part is you cannot just sort numerically: 9 should come before 30 because 930 beats 309. For any two codes, try gluing them both ways and keep the order that produces the bigger glued string.
Understanding the Concepts
What is the Largest Number problem?
Given a list of non-negative integers, arrange them so their concatenation forms the largest possible number. Return the result as a string.
At the National Bank of India, batch processing jobs are prioritized by a composite key formed by concatenating numeric codes. Arranging the codes to produce the largest possible key ensures the highest priority.
package com.bank.core;
import java.util.Arrays;
public class LargestNumberDemo {
public static void main(String[] args) {
int[] codes = {3, 30, 34, 5, 9};
System.out.println(largestNumber(codes)); // 9534330
}
static String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
if (strs[0].equals("0")) return "0"; // all-zeros guard
return String.join("", strs);
}
}
9534330
Why does numeric sorting fail?
Numeric sorting would place 30 before 9 because 30 > 9. But concatenating 30 then 9 gives 309, while 9 then 30 gives 930. The correct answer needs 9 first. What matters is not the numeric value of each piece but which arrangement produces the larger concatenated string.
package com.bank.core;
public class WhyNumericFails {
public static void main(String[] args) {
// Numeric sort: [30, 9] -> "309"
// Custom sort: [9, 30] -> "930"
System.out.println("Numeric order: " + ("30" + "9")); // 309
System.out.println("Custom order: " + ("9" + "30")); // 930
System.out.println("930 > 309: " + ("930".compareTo("309") > 0));
}
}
Numeric order: 309
Custom order: 930
930 > 309: true
How does the custom comparator work?
For two numbers a and b (as strings), form both concatenations a+b and b+a. Both have the same length, so comparing them as strings is safe and equivalent to comparing them as numbers, without any risk of numeric overflow.
// Comparator: put the arrangement producing the larger concatenation first
(a, b) -> (b + a).compareTo(a + b)
// Examples:
// a="3", b="30": "303" vs "330" -> "330" > "303" -> 3 comes first
// a="3", b="34": "334" vs "343" -> "343" > "334" -> 34 comes first
// a="5", b="9": "59" vs "95" -> "95" > "59" -> 9 comes first
package com.bank.core;
import java.util.Arrays;
public class ComparatorDetail {
public static void main(String[] args) {
String[] codes = {"3", "30", "34", "5", "9"};
Arrays.sort(codes, (a, b) -> {
String ab = a + b;
String ba = b + a;
System.out.println(a + " vs " + b + ": " + ab + " vs " + ba
+ " -> " + (ba.compareTo(ab) > 0 ? b + " first" : a + " first"));
return ba.compareTo(ab);
});
System.out.println("Sorted: " + Arrays.toString(codes));
System.out.println("Result: " + String.join("", codes));
}
}
Why is transitivity important?
The comparator must define a consistent total order for the sort to be correct. The a+b vs b+a relation is transitive: if a should come before b and b should come before c, then a should come before c. This is not obvious but is a proven property of this concatenation comparison. Without transitivity, a standard sort could produce inconsistent results.
// Transitivity example:
// a="9", b="5", c="34"
// 9 before 5: "95" > "59" (9 wins)
// 5 before 34: "534" > "345" (5 wins)
// 9 before 34: "934" > "349" (9 wins) -> transitive!
How do you handle the all-zeros edge case?
If the input contains only zeros, sorting and joining produces "000..." but the largest number is just "0". After sorting, if the first element is "0" (the largest piece is zero), the entire result must be "0".
package com.bank.core;
public class AllZerosGuard {
public static void main(String[] args) {
int[] allZeros = {0, 0, 0};
System.out.println(largestNumber(allZeros)); // "0" not "000"
}
static String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
java.util.Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
if (strs[0].equals("0")) return "0"; // guard
return String.join("", strs);
}
}
0
What is the complete banking implementation?
Here is a complete example using branch codes to form the largest priority identifier.
package com.bank.batch;
import java.util.Arrays;
public class BatchPriorityKey {
public static String buildLargestKey(int[] branchCodes) {
if (branchCodes == null || branchCodes.length == 0) {
return "0";
}
String[] codes = new String[branchCodes.length];
for (int i = 0; i < branchCodes.length; i++) {
codes[i] = String.valueOf(branchCodes[i]);
}
// Sort: for each pair, the arrangement producing the larger
// concatenation comes first
Arrays.sort(codes, (a, b) -> (b + a).compareTo(a + b));
// All-zeros guard
if (codes[0].equals("0")) {
return "0";
}
StringBuilder sb = new StringBuilder();
for (String code : codes) {
sb.append(code);
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(buildLargestKey(new int[]{3, 30, 34, 5, 9}));
System.out.println(buildLargestKey(new int[]{10, 2}));
System.out.println(buildLargestKey(new int[]{0, 0}));
System.out.println(buildLargestKey(new int[]{1}));
}
}
9534330
210
0
1
What is the time and space complexity?
The sort runs in O(n log n) comparisons. Each comparison concatenates two strings and compares them, which takes O(k) where k is the average string length. So the total time is O(n k log n). Space is O(n k) for the string array.
For n numbers with average digit count k:
Time: O(n * k * log n) -- sort with string comparison
Space: O(n * k) -- string array
For typical interview inputs (n < 1000, k < 10):
Time is effectively O(n log n)
What are common mistakes?
The two most common mistakes are forgetting the all-zeros guard and trying to sort numerically.
// WRONG: numeric sort
Arrays.sort(nums); // [3, 5, 9, 30, 34] -> "359 3034" -- wrong
// WRONG: forgetting all-zeros guard
String result = String.join("", sortedCodes); // "000" instead of "0"
// CORRECT: custom comparator + zeros guard
Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
if (strs[0].equals("0")) return "0";
return String.join("", strs);
What should a senior engineer know?
- Greedy exchange argument. The sort is provably optimal because any adjacent pair out of order could be swapped to produce a strictly larger result. The fully sorted arrangement is the global maximum.
- Transitivity proof. The a+b vs b+a comparison is transitive because string concatenation over a fixed alphabet preserves lexicographic ordering transitively. This is a known result, and mentioning it shows deep understanding.
- Overflow safety. Comparing the concatenations as strings avoids building giant numbers. For an array of 100 numbers each up to 10 digits, the concatenation could be 1000 digits, far beyond any numeric type.
- Immutable strings. In Java, each
a + bcreates a new String. For very large arrays, usingStringBuilderin the comparator is a minor optimization.
Visual Overview
Input: [3, 30, 34, 5, 9]
Convert to strings: ["3", "30", "34", "5", "9"]
Custom sort comparisons:
"9" + "5" = "95" vs "5" + "9" = "59" -> 9 first
"9" + "34" = "934" vs "34" + "9" = "349" -> 9 first
"5" + "34" = "534" vs "34" + "5" = "345" -> 5 first
"5" + "3" = "53" vs "3" + "5" = "35" -> 5 first
"34" + "3" = "343" vs "3" + "34" = "334" -> 34 first
"34" + "30" = "3430" vs "30" + "34" = "3034" -> 34 first
"3" + "30" = "330" vs "30" + "3" = "303" -> 3 first
Sorted: ["9", "5", "34", "3", "30"]
Join: "9534330"
Key Takeaway
The Largest Number problem arranges non-negative integers so their concatenation is the biggest possible number, and the key insight is that numeric sorting is wrong. The number 3 must come before 30 because 330 beats 303, even though 3 is numerically smaller. What matters is which arrangement produces the larger concatenated string.
I define a custom comparator that, for any two numbers, compares the string a+b against b+a. Because both concatenations have the same length, comparing them as strings is the same as comparing them as numbers, which avoids overflow from building enormous numeric values. I sort all the numbers with this comparator and join them.
The correctness rests on the comparator being a consistent total order. The a+b vs b+a relation is transitive, which lets a standard sort produce the globally optimal arrangement. The edge case I always handle is all zeros: if the largest piece after sorting is zero, I return the single string "0" instead of "000".
At the National Bank of India, I used this to assemble numeric branch codes into the largest concatenated identifier for batch priority keys. Explaining why numeric sorting fails, the equal-length string comparison that avoids overflow, the transitivity that justifies the greedy sort, and the all-zeros guard shows the interviewer that I understand both the trick and why it is provably correct.
Remember one sentence: compare the string a+b against b+a for every pair, sort by the larger concatenation, and the greedy result is the globally largest number.
---