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:

Image of AssemblyAI tool

Transforming Interviews into Publishable Stories with AssemblyAI

Insightview is a modern web application that streamlines the interview workflow for journalists. By leveraging AssemblyAI's LeMUR and Universal-2 technology, it transforms raw interview recordings into structured, actionable content, dramatically reducing the time from recording to publication.

Key Features:
🎥 Audio/video file upload with real-time preview
🗣️ Advanced transcription with speaker identification
⭐ Automatic highlight extraction of key moments
✍️ AI-powered article draft generation
📤 Export interview's subtitles in VTT format

Read full post

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay