Katkat
Back

Arrange Nonnegative Integers to Form the Largest Number

LinkedInSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests custom sorting logic and string manipulation to arrange a list of nonnegative integers into the lexicographically largest combined numerical string.

Problem Statement

Given a list of nonnegative integers nums, arrange them such that their concatenation forms the largest possible number. Since the resulting number can be very large, return the answer as a string.

You must use every value in nums exactly once.

Function Signature

def largest_number(nums: list[int]) -> str:
    pass

Constraints

  • 1 <= len(nums) <= 10^4
  • 0 <= nums[i] <= 10^9

Examples

Example 1

Input: nums = [10, 2]
Output: "210"
Explanation: Concatenating [2, 10] produces "210", which is larger than [10, 2] producing "102".

Example 2

Input: nums = [3, 30, 34, 5, 9]
Output: "9534330"
Explanation: Comparing prefix overlaps, 34 precedes 3 because "343" > "334", and 3 precedes 30 because "330" > "303".

Edge Cases

  • All zeros: For an input like [0, 0], the output must be "0", not "00".
  • Identical prefixes: Numbers such as 3 and 30 require checking pairwise concatenations ("330" vs "303").

Hints

Hint 1

Standard lexicographical or numerical sorting fails because a shorter number might need to come before or after a longer number sharing the same prefix.

Hint 2

For any two numbers `a` and `b` converted to strings, compare the concatenated results `a + b` versus `b + a` to decide their relative order.

Hint 3

Remember to handle the edge case where the largest number in the sorted list is `'0'`, which means all values are zero.

Follow-up questions

  • How does the custom comparator ensure a valid total ordering (transitivity)?
  • What is the time complexity in terms of the number of integers n and the maximum number of digits k per integer?
  • How would your approach change if the stream of numbers arrived dynamically and you frequently needed to query the largest number formed by the current set?