Largest Number - Practice Coding Problems

Largest Number - Problem

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 instead of an integer.

Example: Given [10,2], return "210" (not "102")

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,2]

› Output: "210"

💡 Note: Compare arrangements: [10,2] gives "102" vs [2,10] gives "210". Since "210" > "102", return "210".

Example 2 — Multiple Numbers

$ Input: nums = [3,30,34,5,9]

› Output: "9534330"

💡 Note: Custom sort compares concatenations: "9"+"5" > "5"+"9", "34"+"3" > "3"+"34", "3"+"30" > "30"+"3", resulting in [9,5,34,3,30] → "9534330".

Example 3 — Edge Case with Zeros

$ Input: nums = [0,0]

› Output: "0"

💡 Note: All numbers are zero, so result is "0" (not "00").

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of non-negative integers [10, 2]

Process

Compare all arrangements to find largest

Output

Return largest number as string "210"

Key Takeaway

🎯 Key Insight: Compare concatenated results (xy vs yx) to determine optimal ordering

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use a custom comparator that compares concatenated strings xy vs yx to determine optimal ordering. Best approach is custom sorting with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Custom Sorting Approach	O(n log n)	O(n)	Sort numbers using custom comparison based on concatenation
Brute Force - All Permutations	O(n! × n)	O(n! × n)	Generate all possible arrangements and find the maximum

Custom Sorting Approach — Algorithm Steps

Step 1: Convert all numbers to strings
Step 2: Sort using custom comparator (x+y vs y+x)
Step 3: Concatenate sorted strings to form result

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Strings

Transform numbers to string format

Custom Sort

Compare xy vs yx for each pair

Concatenate

Join sorted strings to form largest number

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char strNums[100][20];
int numCount;

int compare(const void* a, const void* b) {
    char* x = (char*)a;
    char* y = (char*)b;
    
    char xy[40], yx[40];
    strcpy(xy, x);
    strcat(xy, y);
    strcpy(yx, y);
    strcat(yx, x);
    
    return strcmp(yx, xy); // Reverse order for descending sort
}

char* solution(int* nums, int size) {
    if (size == 0) {
        char* result = (char*)malloc(2);
        strcpy(result, "0");
        return result;
    }
    
    // Convert to strings
    numCount = size;
    for (int i = 0; i < size; i++) {
        sprintf(strNums[i], "%d", nums[i]);
    }
    
    // Sort using custom comparator
    qsort(strNums, size, sizeof(strNums[0]), compare);
    
    // Handle edge case where result starts with 0
    if (strNums[0][0] == '0') {
        char* result = (char*)malloc(2);
        strcpy(result, "0");
        return result;
    }
    
    // Concatenate result
    char* result = (char*)malloc(1000);
    strcpy(result, "");
    for (int i = 0; i < size; i++) {
        strcat(result, strNums[i]);
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    int nums[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char* result = solution(nums, size);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting n elements with O(log n) comparisons each

⚡ Linearithmic

Space Complexity

O(n)

Converting numbers to strings and storing result

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Custom Sorting Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler