Jobs

Interviews

Discussions

Largest Number

Medium

Asked by:

+11

More companies

62 views

Topics:

ArraysStringsGreedy Algorithms

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⁹

Try coding it in LeetCode

Largest Number

Medium

Asked by:

More companies

62 views

Topics:

ArraysStringsGreedy Algorithms

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⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for each integer in the input array? Are they strictly non-negative, and is there an upper bound?
Can the input array `nums` be empty or null?
If the input array contains only zeros, what should the output string be: "0" or some other value?
Are we concerned about integer overflow when concatenating the numbers as strings during comparison?
If there are multiple valid arrangements that result in the largest number, is any one of them acceptable?

Brute Force Solution

Approach

The goal is to find the largest number that can be formed by concatenating a given set of numbers represented as strings. The brute force approach tries every single possible ordering of the numbers, and then picks the best result.

Here's how the algorithm would work step-by-step:

Consider all the different ways you could arrange the numbers in a line.
For each arrangement, glue the numbers together to form one large number (string).
Compare all of the resulting numbers to see which one is the largest.
Return the largest one you found.

Code Implementation

from itertools import permutations

def largest_number_brute_force(numbers):
    all_possible_arrangements = permutations(numbers)

    largest_number_found = ""

    for arrangement in all_possible_arrangements:
        # Build the concatenated string
        concatenated_number = "".join(arrangement)

        # Check if current arrangement is the largest
        if largest_number_found == "" or concatenated_number > largest_number_found:
            # Ensures we handle the initial empty case.
            largest_number_found = concatenated_number

    return largest_number_found

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach considers every possible permutation of the input numbers. Generating all permutations of n numbers takes O(n!) time. For each permutation, we concatenate the numbers, which takes O(n) time in the worst case, assuming the average length of a number is constant, since we're concatenating n strings. Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach considers all possible permutations of the N input numbers. Generating all permutations requires storing them, leading to a space complexity proportional to the number of permutations. In the worst case, where we store all N! permutations simultaneously (or construct each one), we would need space to hold these permutations. Therefore, the space complexity for storing all possible orderings is O(N!).

Optimal Solution

Approach

The goal is to arrange a collection of numbers to form the largest possible number. Instead of trying all possible orderings, we can compare numbers based on how they look when placed next to each other to determine the correct order.

Here's how the algorithm would work step-by-step:

Think about how to compare two numbers: Instead of comparing their value, compare what happens when you put them next to each other in different orders.
For example, if you have '3' and '30', compare '330' with '303'. '330' is bigger, so you want '3' to come before '30'.
Use this comparison method to sort all the numbers. The 'bigger' combinations should float to the top.
Once the numbers are sorted in this special way, simply join them together in order.
Be careful when all the numbers are zero. In this special case, the output must be a single zero.

Code Implementation

def largest_number(numbers):
    # Custom comparison function for sorting.
    def compare(number1, number2):
        if number1 + number2 > number2 + number1:
            return 1
        elif number1 + number2 < number2 + number1:
            return -1
        else:
            return 0

    # Convert numbers to strings for comparison.
    numbers_as_strings = [str(number) for number in numbers]

    # Sort the numbers based on custom comparison logic.
    # This puts numbers in order to maximize combined value.
    numbers_as_strings.sort(key=cmp_to_key(compare), reverse=True)

    # Handle the all-zeros edge case.
    if numbers_as_strings[0] == '0':
        return '0'

    # Join the sorted strings to form the largest number.
    largest_combined_number = ''.join(numbers_as_strings)

    return largest_combined_number

from functools import cmp_to_key

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input list of n numbers using a custom comparison function. The standard sorting algorithms (like those used by `sort` in most languages) have a time complexity of O(n log n). The custom comparison function involves string concatenation and comparison, which takes O(k) time, where k is the average length of the number strings. However, since k is bounded by the maximum length of a single number, which is independent of n, we can consider it a constant factor. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm sorts the input numbers based on a custom comparison. Most sorting algorithms (like merge sort or timsort which are common in standard libraries) require auxiliary space for temporary storage during the sorting process. In the worst case, an array of size N (where N is the number of input numbers) might be needed to store temporary values during the sort. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty or null input array	Return an empty string or handle the null case according to requirements, potentially throwing an exception.
Array with a single element	Return the string representation of that single element.
Array contains only zeros	Return '0' to avoid leading zeros or an incorrect concatenated result.
Large input array with many elements	The solution should use an efficient sorting algorithm (e.g., merge sort or quicksort with custom comparison) to avoid quadratic time complexity.
Array contains integers of varying lengths (number of digits)	The custom comparison logic should correctly handle the concatenation of strings with differing lengths to avoid incorrect ordering.
Integer overflow during string concatenation (though highly unlikely in practical scenarios)	String concatenation handles large number representation effectively, avoiding integer overflow issues.
Array contains duplicate numbers that, when concatenated, may result in a different 'largest' result based on order.	The custom comparator needs to handle duplicate numbers correctly when creating the ordered result.
Input array with mixed positive integers and zeros	Zeros need to be handled carefully in combination with other integers to form the maximum number

Empty or null input array

How to Handle:

Return an empty string or handle the null case according to requirements, potentially throwing an exception.

Array with a single element

How to Handle:

Return the string representation of that single element.

Array contains only zeros

How to Handle:

Return '0' to avoid leading zeros or an incorrect concatenated result.

Large input array with many elements

How to Handle:

The solution should use an efficient sorting algorithm (e.g., merge sort or quicksort with custom comparison) to avoid quadratic time complexity.

Array contains integers of varying lengths (number of digits)

How to Handle:

The custom comparison logic should correctly handle the concatenation of strings with differing lengths to avoid incorrect ordering.

Integer overflow during string concatenation (though highly unlikely in practical scenarios)

How to Handle:

String concatenation handles large number representation effectively, avoiding integer overflow issues.

Array contains duplicate numbers that, when concatenated, may result in a different 'largest' result based on order.

How to Handle:

The custom comparator needs to handle duplicate numbers correctly when creating the ordered result.

Input array with mixed positive integers and zeros

How to Handle:

Zeros need to be handled carefully in combination with other integers to form the maximum number

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for each integer in the input array? Are they strictly non-negative, and is there an upper bound?
Can the input array `nums` be empty or null?
If the input array contains only zeros, what should the output string be: "0" or some other value?
Are we concerned about integer overflow when concatenating the numbers as strings during comparison?
If there are multiple valid arrangements that result in the largest number, is any one of them acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all the different ways you could arrange the numbers in a line.
For each arrangement, glue the numbers together to form one large number (string).
Compare all of the resulting numbers to see which one is the largest.
Return the largest one you found.

Code Implementation

from itertools import permutations

def largest_number_brute_force(numbers):
    all_possible_arrangements = permutations(numbers)

    largest_number_found = ""

    for arrangement in all_possible_arrangements:
        # Build the concatenated string
        concatenated_number = "".join(arrangement)

        # Check if current arrangement is the largest
        if largest_number_found == "" or concatenated_number > largest_number_found:
            # Ensures we handle the initial empty case.
            largest_number_found = concatenated_number

    return largest_number_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think about how to compare two numbers: Instead of comparing their value, compare what happens when you put them next to each other in different orders.
For example, if you have '3' and '30', compare '330' with '303'. '330' is bigger, so you want '3' to come before '30'.
Use this comparison method to sort all the numbers. The 'bigger' combinations should float to the top.
Once the numbers are sorted in this special way, simply join them together in order.
Be careful when all the numbers are zero. In this special case, the output must be a single zero.

Code Implementation

def largest_number(numbers):
    # Custom comparison function for sorting.
    def compare(number1, number2):
        if number1 + number2 > number2 + number1:
            return 1
        elif number1 + number2 < number2 + number1:
            return -1
        else:
            return 0

    # Convert numbers to strings for comparison.
    numbers_as_strings = [str(number) for number in numbers]

    # Sort the numbers based on custom comparison logic.
    # This puts numbers in order to maximize combined value.
    numbers_as_strings.sort(key=cmp_to_key(compare), reverse=True)

    # Handle the all-zeros edge case.
    if numbers_as_strings[0] == '0':
        return '0'

    # Join the sorted strings to form the largest number.
    largest_combined_number = ''.join(numbers_as_strings)

    return largest_combined_number

from functools import cmp_to_key

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return an empty string or handle the null case according to requirements, potentially throwing an exception.
Array with a single element	Return the string representation of that single element.
Array contains only zeros	Return '0' to avoid leading zeros or an incorrect concatenated result.
Large input array with many elements	The solution should use an efficient sorting algorithm (e.g., merge sort or quicksort with custom comparison) to avoid quadratic time complexity.
Array contains integers of varying lengths (number of digits)	The custom comparison logic should correctly handle the concatenation of strings with differing lengths to avoid incorrect ordering.
Integer overflow during string concatenation (though highly unlikely in practical scenarios)	String concatenation handles large number representation effectively, avoiding integer overflow issues.
Array contains duplicate numbers that, when concatenated, may result in a different 'largest' result based on order.	The custom comparator needs to handle duplicate numbers correctly when creating the ordered result.
Input array with mixed positive integers and zeros	Zeros need to be handled carefully in combination with other integers to form the maximum number

Empty or null input array

How to Handle:

Return an empty string or handle the null case according to requirements, potentially throwing an exception.

Array with a single element

How to Handle:

Return the string representation of that single element.

Array contains only zeros

How to Handle:

Return '0' to avoid leading zeros or an incorrect concatenated result.

Large input array with many elements

How to Handle:

The solution should use an efficient sorting algorithm (e.g., merge sort or quicksort with custom comparison) to avoid quadratic time complexity.

Array contains integers of varying lengths (number of digits)

How to Handle:

The custom comparison logic should correctly handle the concatenation of strings with differing lengths to avoid incorrect ordering.

Integer overflow during string concatenation (though highly unlikely in practical scenarios)

How to Handle:

String concatenation handles large number representation effectively, avoiding integer overflow issues.

Array contains duplicate numbers that, when concatenated, may result in a different 'largest' result based on order.

How to Handle:

The custom comparator needs to handle duplicate numbers correctly when creating the ordered result.

Input array with mixed positive integers and zeros

How to Handle:

Zeros need to be handled carefully in combination with other integers to form the maximum number