Posts Largest Number formed from an Array (geeksforgeeks - SDE Sheet)
Post
Cancel

Largest Number formed from an Array (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

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

geeksforgeeks

SOLUTION

The main idea it to use a custom comparator to compare two strings and use that to sort the given array. Once the array is sorted, we just need to concatenate all the strings from left to right, since we sorted in descending order to get the largest value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

    String printLargest(int n, String[] arr) {

        Arrays.sort(arr, new MyComparator());

        StringBuffer sb = new StringBuffer();

        for(int i=0; i<n; i++)
            sb.append(arr[i]);

        return sb.toString();
    }

}

class MyComparator implements Comparator<String>{

    @Override
    public int compare(String a, String b){

        String s1 = a + b;
        String s2 = b + a;

        return s2.compareTo(s1);

    }

}
This post is licensed under CC BY 4.0 by the author.