79. Largest Number Medium Topics Companies Given a list of non-negative integers nums,…
- User
- Largest Number Medium Topics Companies 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] <= 109
class Solution: def largestNumber(self, nums: List[int]) -> str:
- Assistant
To solve the "Largest Number" problem, the goal is to arrange a list of non-negative integers such that they form the largest possible number when concatenated together. Here's a step-by-step guide to approach and implement this solution in Python.
Problem Statement
Given a list of non-negative integers
nums, arrange them such that they form the largest number and return it as a string.Examples:
-
Example 1:
- Input:
nums = [10, 2] - Output:
"210"
- Input:
-
Example 2:
- Input:
nums = [3, 30, 34, 5, 9] - Output:
"9534330"
- Input:
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 10^9
Approach
-
Convert Numbers to Strings:
- Since concatenation is required, it's more convenient to work with the numbers as strings.
-
Custom Sorting:
- To determine the order of two numbers
aandb, compare the concatenated results ofa + bandb + a. - If
a + bis greater thanb + a, thenashould come beforeb; otherwise,bshould come beforea. - This ensures that the concatenation of the entire list results in the largest possible number.
- To determine the order of two numbers
-
Handle Edge Cases:
- If after sorting, the first number is
'0', it means all numbers are zeros. In this case, return'0'to avoid multiple leading zeros.
- If after sorting, the first number is
Implementation
Here's how you can implement this approach in Python:
from typing import List from functools import cmp_to_key class Solution: def largestNumber(self, nums: List[int]) -> str: # Convert all numbers to strings nums_str = list(map(str, nums)) # Define a comparator that decides which concatenation is bigger def compare(a, b): if a + b > b + a: return -1 # a should come before b elif a + b < b + a: return 1 # b should come before a else: return 0 # a and b are equal in terms of concatenation # Sort the numbers with the custom comparator nums_sorted = sorted(nums_str, key=cmp_to_key(compare)) # Edge case: if the largest number is '0', return '0' if nums_sorted[0] == '0': return '0' # Concatenate the sorted strings largest_num = ''.join(nums_sorted) return largest_numExplanation
-
Conversion to Strings:
nums_str = list(map(str, nums)): Converts each integer in thenumslist to a string for easy concatenation.
-
Custom Comparator Function:
- The
comparefunction decides the order of any two elementsaandb. - It compares the concatenated strings
a + bandb + a. - If
a + bis greater, it returns-1to placeabeforeb. - If
a + bis smaller, it returns1to placebbeforea. - If they are equal, it returns
0, indicating no change in order.
- The
-
Sorting the List:
nums_sorted = sorted(nums_str, key=cmp_to_key(compare)): Sorts the list based on the custom comparator.
-
Handling Edge Cases:
- If the first element after sorting is
'0', it means all elements are zeros. Hence, return'0'.
- If the first element after sorting is
-
Concatenating the Sorted Strings:
largest_num = ''.join(nums_sorted): Joins all the sorted strings to form the largest possible number.
Example Walkthrough
Let's walk through the example
nums = [3, 30, 34, 5, 9]:-
Conversion to Strings:
nums_str = ['3', '30', '34', '5', '9']
-
Sorting:
- Compare
'3'and'30':'330'>'303'→'3'comes before'30'. - Compare
'30'and'34':'3034'<'3430'→'34'comes before'30'. - Compare
'34'and'5':'345'<'534'→'5'comes before'34'. - Compare
'5'and'9':'59'<'95'→'9'comes before'5'.
Final sorted order:
['9', '5', '34', '3', '30'] - Compare
-
Concatenation:
'9' + '5' + '34' + '3' + '30' = '9534330'
Thus, the largest number formed is
"9534330".Time and Space Complexity
-
Time Complexity: O(n log n)
- Sorting takes O(n log n) time.
-
Space Complexity: O(n)
- Additional space is used to store the string representations of the numbers.
Conclusion
This solution effectively arranges the numbers to form the largest possible concatenated number by leveraging a custom sorting strategy. By comparing the concatenated results of pairs of numbers, we ensure that each placement contributes to maximizing the overall number.
-