Problem of The Day: Largest Number

Problem Statement

Notes:

• Need to review
• Good problem to review sorting techniques
• Just memorize merge sort and quick sort for interview

Editorial

Approach 1: Using Built-in Function

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # Convert each integer to a string
        num_strings = [str(num) for num in nums]

        # Sort strings based on concatenated values
        num_strings.sort(key=lambda a: a * 10, reverse=True)

        # Handle the case where the largest number is zero
        if num_strings[0] == "0":
            return "0"

        # Concatenate sorted strings to form the largest number
        return "".join(num_strings)

Let n be the size of the nums array.

• Time Complexity: O(n log n)

  The most time-consuming operation is the sorting step, which uses a custom comparator. The sorting algorithm has a time complexity of O(n log n). The conversion of numbers to strings and concatenation operations are linear with respect to the number of elements.

• Space Complexity: O(n + S)

  Additional space is used for storing the string representations of the numbers and the final concatenated result, which scales linearly with the size of the input array.

  Some extra space is used when we sort an array of size n in place. The space complexity of the sorting algorithm (S) depends on the programming language. The value of S depends on the programming language and the sorting algorithm being used:

  • In Python, the sort method sorts a list using the Timsort algorithm, which is a combination of Merge Sort and Insertion Sort and has a space complexity of O(n).
  • In C++, the sort() function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worst-case space complexity of O(log n).
  • In Java, Arrays.sort() is implemented using a variant of the Quick Sort algorithm which has a space complexity of O(log n).

Thus, the total space complexity of the algorithm is O(n + S).

Approach 2: Quick Sort

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # Sort the numbers using Quick Sort
        self._quick_sort(nums, 0, len(nums) - 1)
        # Concatenate sorted numbers to form the largest number
        largest_num = "".join(map(str, nums))
        # Handle the case where the largest number is zero
        return "0" if largest_num[0] == "0" else largest_num

    def _quick_sort(self, nums: List[int], left: int, right: int) -> None:
        # Base case: if the range has one or no elements, it is already sorted
        if left >= right:
            return

        # Partition the array and get the pivot index
        pivot_index = self._partition(nums, left, right)

        # Recursively sort the sub-arrays
        self._quick_sort(nums, left, pivot_index - 1)
        self._quick_sort(nums, pivot_index + 1, right)

    def _partition(self, nums: List[int], left: int, right: int) -> int:
        pivot = nums[right]
        low_index = left

        # Rearrange elements so that those greater than the pivot are on the left
        for i in range(left, right):
            if self._compare(nums[i], pivot):
                nums[i], nums[low_index] = nums[low_index], nums[i]
                low_index += 1

        # Place the pivot in its correct position
        nums[low_index], nums[right] = nums[right], nums[low_index]
        return low_index

    def _compare(self, first_num: int, second_num: int) -> bool:
        # Compare concatenated strings to decide the order
        return str(first_num) + str(second_num) > str(second_num) + str(
            first_num
        )

• time: O(n log n)
• space: O(log n)

Approach 3: Merge Sort

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # Sort the numbers using Merge Sort
        sorted_nums = self._merge_sort(nums, 0, len(nums) - 1)
        # Concatenate sorted numbers to form the largest number
        largest_num = "".join(map(str, sorted_nums))
        # Handle the case where the largest number is zero
        return "0" if largest_num[0] == "0" else largest_num

    def _merge_sort(self, nums: List[int], left: int, right: int) -> List[int]:
        # Base case: a single element is already sorted
        if left >= right:
            return [nums[left]]
        mid = left + (right - left) // 2

        # Recursively sort the left and right halves
        left_half = self._merge_sort(nums, left, mid)
        right_half = self._merge_sort(nums, mid + 1, right)

        # Merge the sorted halves
        return self._merge(left_half, right_half)

    def _merge(self, left_half: List[int], right_half: List[int]) -> List[int]:
        sorted_nums = []
        left_index, right_index = 0, 0

        # Merge the two halves based on custom comparison
        while left_index < len(left_half) and right_index < len(right_half):
            if self._compare(left_half[left_index], right_half[right_index]):
                sorted_nums.append(left_half[left_index])
                left_index += 1
            else:
                sorted_nums.append(right_half[right_index])
                right_index += 1

        # Append remaining elements from left half
        sorted_nums.extend(left_half[left_index:])

        # Append remaining elements from right half
        sorted_nums.extend(right_half[right_index:])
        return sorted_nums

    def _compare(self, first_num: int, second_num: int) -> bool:
        # Compare concatenated strings to decide the order
        return str(first_num) + str(second_num) > str(second_num) + str(
            first_num
        )

• time: O(n log n)
• space: O(n)

Approach 4: HeapSort

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # Edge case: if all numbers are zero, return "0"
        if not any(nums):
            return "0"

        # Custom comparison function for heapq (simulating the comparator in Java)
        class LargerStrComparator(str):
            def __lt__(self, other):
                # Custom comparison: return True if self+other > other+self
                return self + other > other + self

        # Priority queue (min-heap), but we push elements using a custom comparator
        heap = []
        for num in nums:
            heapq.heappush(heap, LargerStrComparator(str(num)))

        # Build the result string by popping from the heap
        result = []
        while heap:
            result.append(heapq.heappop(heap))

        # Concatenate and return the result
        largest_num = "".join(result)

        # Handle case where all elements are "0"
        return "0" if largest_num[0] == "0" else largest_num

• time: O(n log n)
• space: O(n log k)