DEV Community

Cover image for 179. Largest Number
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1

179. Largest Number

179. Largest Number

Difficulty: Medium

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

Solution:

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) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

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

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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →