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

# 🚀 _3. Form the Largest Number_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/sorting-bonus-problems/problem/largest-number-formed-from-an-array1117)

## 💡 **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++)

```cpp
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;
    }
};
```

<details>
  <summary><h2 align='center'>👨‍💻 Alternative Approaches</h2></summary>

### 🏷️ Alternative Approach (Using Custom Comparator)

```cpp
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)

```cpp
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;
    }
};
```

</details>

## Code (Java)

```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)

```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

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

---

<div align="center">  
  <h3><b>📍Visitor Count</b></h3>  
</div>

<p align="center">  
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />  
</p>