algoadvance

Leetcode 179. Largest Number

Problem Statement

You are 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, you need to return a string representation of this largest number.

Example:

• Input: nums = [10, 2]

• Output: "210"

• Input: nums = [3, 30, 34, 5, 9]
• Output: "9534330"

Clarification Questions:

1. Q: Are there any constraints on the size of the array?
   A: The length of nums is between 1 and 10^4, and each number in nums is between 0 and 10^9.

2. Q: Can the result contain leading zeros?
   A: No, the result should not contain leading zeros unless the number itself is zero.

3. Q: Should the output always be a non-negative number?
   A: Yes, since the input only contains non-negative numbers.

Strategy

The main challenge is to order the numbers such that they form the largest concatenated result. Here’s our approach:

1. Custom Comparison:
   • To decide which number should come first, compare two numbers by concatenating them in both possible orders.
   • For example, to compare num1 and num2, we compare num1+num2 with num2+num1. If num1+num2 is greater, num1 should come before num2.
2. Sort:
   • Sort the numbers based on the custom comparison function defined above.
3. Concatenate:
   • After sorting, concatenate the numbers to form the largest number.
4. Edge Cases:
   • If the highest value after sorting is 0, return "0" (handles cases with multiple zeros).

Code

Here is the implementation of the above strategy in C++:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string largestNumber(vector<int>& nums) {
    // Convert all integers to strings for comparison
    vector<string> numStrs;
    for (int num : nums) {
        numStrs.push_back(to_string(num));
    }

    // Sort based on the custom comparator
    sort(numStrs.begin(), numStrs.end(), [](string& s1, string& s2) {
        return s1 + s2 > s2 + s1;
    });

    // Handle edge case where all numbers are zeros
    if (numStrs[0] == "0") {
        return "0";
    }

    // Concatenate the results
    string largestNum;
    for (string& numStr : numStrs) {
        largestNum += numStr;
    }

    return largestNum;
}

int main() {
    vector<int> nums1 = {10, 2};
    vector<int> nums2 = {3, 30, 34, 5, 9};

    cout << "Largest Number from {10, 2}: " << largestNumber(nums1) << endl;
    cout << "Largest Number from {3, 30, 34, 5, 9}: " << largestNumber(nums2) << endl;

    return 0;
}

Time Complexity

• Conversion from int to string: O(n)
• Sorting: O(n log n), where n is the number of elements in the array.
• String concatenation: O(n), as there is only one loop to concatenate all the strings.

Therefore, the overall time complexity is O(n log n), which is efficient given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?