NUHMAN.com

Introduction

LeetCode 179 asks you to arrange a list of non-negative integers to form the largest possible number. The challenge is to determine how to sort the numbers such that their concatenation forms the largest value.

The problem is solved by sorting the numbers in a custom way to create the largest number when concatenated. It's not just about sorting the numbers in descending order but figuring out which order of concatenating two numbers produces the larger result.

Problem Statement

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

Function Signature:

go

func largestNumber(nums []int) string

Example 1:

go

nums := []int{10, 2}
result := largestNumber(nums) // Output: "210"

Example 2:

go

nums := []int{3, 30, 34, 5, 9}
result := largestNumber(nums) // Output: "9534330"

Example 3:

go

nums := []int{0, 0}
result := largestNumber(nums) // Output: "0"

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

Approach

Greedy Approach with Custom Comparator:

1. Custom Sorting Logic:

• To determine which order produces the larger number, we can compare two numbers x and y by concatenating them in both possible ways: xy and yx. We treat these concatenated strings as numbers and compare them lexicographically. The one that is larger determines the order.
• For example, for x = 9 and y = 34, we compare the strings xy = "934" and yx = "349". Since "934" > "349", 9 should come before 34.

1. Edge Case (Leading Zeros):

• If all the numbers are zeros, the largest number should be "0". For example, [0, 0] should return "0".

1. Implementation Details:

• Convert integers to strings for easy comparison.
• Sort the strings using a custom comparator.
• Join the sorted strings to form the largest number.
• Handle the edge case where the result starts with "0".

Time Complexity:

• Sorting Complexity: O(n log n), where n is the number of integers in the array. This is the time complexity for sorting the array using a custom comparator.
• String Concatenation: O(n), where n is the number of elements in the array (to concatenate all strings into the result).

Space Complexity:

• O(n), where n is the number of elements, as we store the sorted strings.

Go Implementation

go

import (
	"fmt"
	"sort"
	"strconv"
)

// customComparator is a helper function to compare two strings x and y
func customComparator(x, y string) bool {
	return x+y > y+x
}

func largestNumber(nums []int) string {
	// Convert the integer array to a string array
	strNums := make([]string, len(nums))
	for i, num := range nums {
		strNums[i] = strconv.Itoa(num)
	}

	// Sort the string array using the custom comparator
	sort.Slice(strNums, func(i, j int) bool {
		return customComparator(strNums[i], strNums[j])
	})

	// If the largest number is "0", return "0"
	if strNums[0] == "0" {
		return "0"
	}

	// Join the sorted string array to form the final result
	return fmt.Sprintf("%s", strNums)
}

Explanation of the Code:

1. customComparator function:

• This function compares two strings x and y by checking if x+y > y+x. This ensures that the string that forms the larger number when concatenated comes first.

1. largestNumber function:

• Convert each integer in the nums array into a string using strconv.Itoa.
• Sort the string array using the customComparator.
• If the first string in the sorted array is "0", we know all numbers are zeros, so we return "0".
• Finally, we concatenate all the sorted strings into one large number using fmt.Sprintf and return the result.

Example Walkthrough

Example 1:

go

nums := []int{3, 30, 34, 5, 9}
result := largestNumber(nums)
fmt.Println(result) // Output: "9534330"

• Convert nums to strings: ["3", "30", "34", "5", "9"]
• Sort them using the custom comparator:
• ["9", "5", "34", "3", "30"]
• Concatenate the strings to form the largest number: "9534330"

Example 2:

go

nums := []int{10, 2}
result := largestNumber(nums)
fmt.Println(result) // Output: "210"

• Convert nums to strings: ["10", "2"]
• Sort them using the custom comparator:
• ["2", "10"]
• Concatenate the strings to form the largest number: "210"

Example 3:

go

nums := []int{0, 0}
result := largestNumber(nums)
fmt.Println(result) // Output: "0"

• Convert nums to strings: ["0", "0"]
• Sort them using the custom comparator:
• ["0", "0"]
• Since the first string is "0", return "0".

Conclusion

LeetCode 179: Largest Number is a problem where you need to arrange numbers to form the largest possible concatenated value. By sorting the numbers using a custom comparator that compares concatenated strings, we can efficiently solve this problem. The solution also handles edge cases like all zeros properly.