algoadvance

Leetcode 179. Largest Number

Problem Statement

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

Example 1:

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

Example 2:

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

Note:

• The result may be very large, so you need to return a string instead of an integer.
• The integers in the given list can be non-negative integers.

Clarifying Questions

1. Q: Are there any constraints on the size of the list (number of integers) or the value of the integers?
   • A: The problem statement does not specify constraints, so assume typical constraints like those usually in coding problems (e.g., inputs are within reasonable bounds for a coding challenge).
2. Q: Should the function handle empty lists?
   • A: For the purposes of this problem, assume the input list will always contain at least one non-negative integer.
3. Q: Can the list contain duplicate integers?
   • A: Yes, the list can contain duplicate integers.

Strategy

The problem requires forming the largest number possible from concatenation of given numbers. The approach involves sorting the numbers based on a custom comparator:

1. Custom Comparator: Compare two numbers by checking their concatenated results in both possible orders (e.g., for numbers a and b, check if ab is greater than ba).
2. Sort: Use the custom comparator to sort the numbers in descending order.
3. Concatenate Result: Combine the sorted numbers into a single string.
4. Edge Case: Handle the case where the highest number is 0 (e.g., [0, 0] should return “0”).

Code

import java.util.*;

public class LargestNumber {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        
        String[] asStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            asStrs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(asStrs, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                String order1 = a + b;
                String order2 = b + a;
                return order2.compareTo(order1);
            }
        });
        
        // If the largest number is 0, the result is "0".
        if (asStrs[0].equals("0")) {
            return "0";
        }
        
        StringBuilder sb = new StringBuilder();
        for (String numAsStr : asStrs) {
            sb.append(numAsStr);
        }
        
        return sb.toString();
    }
    
    public static void main(String[] args) {
        LargestNumber solution = new LargestNumber();
        int[] nums1 = {10, 2};
        int[] nums2 = {3, 30, 34, 5, 9};
        
        System.out.println(solution.largestNumber(nums1)); // Output: "210"
        System.out.println(solution.largestNumber(nums2)); // Output: "9534330"
    }
}

Time Complexity

• Sorting: The dominant factor is sorting the array, which has a time complexity of (O(n \log n)), where (n) is the number of elements in the input list.
• Concatenation: The concatenation of sorted strings is linear relative to the input size, (O(nm)), where (m) is the average length of the numbers when converted to strings.

Thus, the overall time complexity is (O(n \log n + nm)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?