Leetcode 179 - Largest Number

Prompt: Given a list of integers, return the largest number by combining all the integers in the list in string format.

Example:

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

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

Input: nums = [1]
Output: "1"

Input: nums = [10]
Output: "10"

Solution: A possible solution is to sort the integers by largest at a given position. To do this, we can make a nested for loop to go through all pairs of integers and switch the position of the integers by comparing the integer value of the string concatenation of the two integers in different order. For example:

Given integers a and b.

If int(str(a) + str(b)) < int(str(b) + str(a)), then we can be sure that integer b would create the largest possible integer if it is positioned to the left.

If we do this for all positions, we essentially find the largest possible integer at all positions. The concatenation of all the largest possible integers in string format would return the largest integer.

The runtime is O(n²) because there’s a nested for loop.