Largest Number

LeetCode 179 | Difficulty: Medium

Medium

Problem Description

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^9`

Topics: Array, String, Greedy, Sorting

---

Approach

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 149 ms)

Metric	Value
Runtime	149 ms
Memory	40.2 MB
Date	2022-02-13

Solution

public class Solution {
    public string LargestNumber(int[] nums) {
        string[] vals = nums.Select(x=>x.ToString()).ToArray();
    Array.Sort(vals, new StringMergeComparer());
        if(vals[0]=="0") return vals[0];
    StringBuilder sb = new StringBuilder();
    return string.Join("",vals);
}

public class StringMergeComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        return (y+x).CompareTo(x+y);
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.