3. Form the Largest Number.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	Arrays

🚀 3. Form the Largest Number 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given an array of integers arr[] representing non-negative integers, arrange them so that after concatenating all of them in order, it results in the largest possible number. Since the result may be very large, return it as a string.

🔍 Example Walkthrough:

Input:

arr[] = [3, 30, 34, 5, 9]

Output:

"9534330"

Explanation:
The arrangement "9534330" gives the largest value.

Input:

arr[] = [54, 546, 548, 60]

Output:

"6054854654"

Explanation:
The arrangement "6054854654" gives the largest value.

Input:

arr[] = [3, 4, 6, 5, 9]

Output:

"96543"

Constraints:

• $1 \leq arr.size() \leq 10^5$
• $0 \leq arr[i] \leq 10^5$

🎯 My Approach:

Step-by-Step:

1. Convert Integers to Strings:
   Since concatenation involves strings, we first convert all integers to strings to facilitate the sorting and concatenation.

2. Custom Sorting:
   Sort the string array based on the rule: for two numbers x and y, compare x + y and y + x.

   • If x + y > y + x, then x should come before y in the sorted order.

3. Handle Leading Zeros:
   If the largest number (after sorting) is 0, return "0" as the result to avoid cases like "000".

4. Concatenate Strings:
   Join all the strings in the sorted array to form the final result.

🕒 Time and Auxiliary Space Complexity:

• Expected Time Complexity:

  • Sorting the array using a custom comparator takes O(n log n).
  • Concatenating the strings takes O(n).
  • Overall time complexity is O(n log n).

• Expected Auxiliary Space Complexity:

  • Storing the string representations of numbers requires O(n) space.
  • Additional temporary space for sorting is O(n).
  • Total auxiliary space is O(n).

📝 Solution Code:

Code (C++)

class Solution {
public:
    std::string findLargest(std::vector<int>& arr) {
        std::vector<std::string> strArr(arr.size());
        std::transform(arr.begin(), arr.end(), strArr.begin(), [](int num) {
            return std::to_string(num);
        });
        std::sort(strArr.begin(), strArr.end(), [](const std::string& x, const std::string& y) {
            return x + y > y + x;
        });
        if (strArr[0] == "0") return "0";
        std::string result;
        for (const std::string& s : strArr) {
            result += s;
        }
        return result;
    }
};

👨‍💻 Alternative Approaches

🏷️ Alternative Approach (Using Custom Comparator)

class Solution {
public:
    string findLargest(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [](int x, int y) {
            return to_string(x) + to_string(y) > to_string(y) + to_string(x);
        });
        string ans;
        for (int num : arr) {
            ans += to_string(num);
        }
        return ans[0] == '0' ? "0" : ans;
    }
};

🏷️ Alternative Approach (Using String Sorting)

class Solution {
public:
    std::string findLargest(std::vector<int>& arr) {
        std::vector<std::string> strArr(arr.size());
        std::transform(arr.begin(), arr.end(), strArr.begin(), [](int num) {
            return std::to_string(num);
        });
        std::sort(strArr.begin(), strArr.end(), [](const std::string& x, const std::string& y) {
            return x + y > y + x;
        });
        if (strArr[0] == "0") return "0";
        std::string result;
        result.reserve(arr.size() * 10); 
        for (const std::string& s : strArr) {
            result += s;
        }

        return result;
    }
};

Code (Java)

class Solution {
    String findLargest(int[] arr) {
        String[] strArr = Arrays.stream(arr)
                                 .mapToObj(String::valueOf)
                                 .toArray(String[]::new);
        Arrays.sort(strArr, (x, y) -> (y + x).compareTo(x + y));
        if (strArr[0].equals("0")) return "0";
        return String.join("", strArr);
    }
}

Code (Python)

class Solution:
    def findLargest(self, arr):
        arr = sorted(map(str, arr), key=lambda x: x * 10, reverse=True)
        if arr[0] == "0":
            return "0"
        return ''.join(arr)

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count