Is Largest Number easy or hard?

Largest Number is generally considered a medium difficulty problem. The implementation is short once you know the trick, but discovering the correct comparison rule a+b vs b+a requires careful reasoning about string ordering and greedy decisions.

Largest Number Python/Java solution

Python solutions typically use sorted() with functools.cmp_to_key to implement the custom comparator. Java implementations use Arrays.sort with a Comparator that compares (b + a) and (a + b). Both versions follow the same greedy ordering logic and run in O(n log n) time.

How to solve Largest Number in O(n)?

An exact O(n) solution is not practical because the problem requires ordering elements relative to each other. Any comparison-based ordering requires at least O(n log n) operations. The optimal practical approach is sorting with a custom comparator that compares a+b and b+a.

What is the best approach for Largest Number?

The best approach uses custom sorting with a concatenation comparator. Convert numbers to strings and compare a+b with b+a to decide ordering. Sorting with this rule ensures the final concatenation produces the largest possible number. The overall time complexity is O(n log n * k), where k is the average digit length.

Is Largest Number asked at Google/Amazon/Meta?

Largest Number is a common medium-level interview problem seen in companies like Amazon, Google, and Meta. It tests understanding of custom comparators, greedy ordering logic, and edge cases with string concatenation. Interviewers often expect candidates to derive the a+b vs b+a comparison insight.

What data structure is used in Largest Number?

The primary data structure is an array of strings combined with a custom sorting comparator. Some implementations also use a heap or priority queue with the same comparator rule. The key idea is comparing concatenated strings rather than numeric values.

What is the time complexity of Largest Number?

The optimal solution runs in O(n log n * k) time. The n log n factor comes from sorting the array, while k represents the cost of comparing concatenated strings during the custom comparator check. Space complexity is O(n) because the integers are typically converted into strings.

179. Largest Number - Practice Online

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 10⁹