179. Largest Number

[mah-shamim]

Topics: Array, String, Greedy, Sorting

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

[basharul-siddike]

We need to compare numbers based on their concatenated results. For two numbers a and b, we compare ab (a concatenated with b) and ba (b concatenated with a), and decide the order based on which forms a larger number.

Approach:

1. Custom Sorting: Implement a custom comparator function that sorts the numbers by comparing the concatenated results.
2. Edge Case: If the largest number after sorting is 0, then the result is "0", as all numbers must be zero.
3. Concatenation: After sorting, concatenate the numbers to form the final result.

Let's implement this solution in PHP: 179. Largest Number

<?php
/**
 * @param Integer[] $nums
 * @return String
 */
function largestNumber($nums) {
    // Custom comparison function for sorting
    usort($nums, function($a, $b) {
        $order1 = $a . $b;
        $order2 = $b . $a;
        return strcmp($order2, $order1);  // Sort in descending order based on concatenation
    });

    // Join the sorted numbers into a single string
    $result = implode('', $nums);

    // Handle the case where the largest number is "0"
    return $result[0] === '0' ? '0' : $result;
}

// Example usage:
$nums1 = [10, 2];
echo largestNumber($nums1);  // Output: "210"

$nums2 = [3, 30, 34, 5, 9];
echo largestNumber($nums2);  // Output: "9534330"
?>

Explanation:

1. usort($nums, $comparator): We sort the array using a custom comparator. For each pair of numbers a and b, we compare the concatenated strings a . b and b . a.
2. Comparison Logic: The strcmp($order2, $order1) ensures that we get a descending order based on the concatenated strings.
3. Edge Case Handling: If the first character of the resulting concatenated string is 0, we return "0", which happens when all elements of the array are zeros.
4. Time Complexity: Sorting the numbers takes O(n log n), and concatenating them takes O(n), where n is the number of numbers in the input array.

This solution handles the constraints efficiently and returns the largest possible number as a string.

[mah-shamim]

Thanks tTo solve the problem of arranging a list of non-negative integers such that they form the largest possible number, the key idea is to define a custom sorting logic. Instead of simply sorting the numbers in their natural order

[basharul-siddike]

Thanks