Largest Number | LeetCode | Java

#java #leetcode #beginners #algorithms

Intuition :

The main intuition behind this problem is sorting. Now, are we gonna apply merge sort, quick sort, selection sort 🤔?
No...
It will be a custom sorting. Means we are gonna sort according to our problem statement.

-> Custom sorting, also known as comparator-based sorting, allows you to define your own comparison logic for sorting elements. In Java, you can achieve custom sorting by providing a comparator function.

Algorithm :

Input: The method takes an array of integers nums[] as input.
Convert Integers to Strings: Initialize a string array arr[] of the same length as nums[]. Iterate through each integer in nums[] and convert it into a string, storing it in the corresponding index of arr[].
Custom Sorting: Sort the string array arr[] in non-ascending order based on a custom comparator. The comparator concatenates two strings s1 and s2 in two different orders (s2+s1 and s1+s2) and compares them lexicographically. This ensures that when sorted, the resulting order will form the largest number.
Build the Largest Number: Initialize a StringBuilder to build the largest number. Append each string from the sorted arr[] to the StringBuilder.
Check for Leading Zeros: If the first element of the sorted array is "0", it means that all elements are zeros. In this case, return "0" as the largest possible number.
Return Largest Number: Convert the StringBuilder to a string and return it as the result.

Code

class Solution {
    public String largestNumber(int[] nums) {

        int n = nums.length;

        String arr[] = new String[n];

        for(int i=0; i<n; i++){
            arr[i] = String.valueOf(nums[i]);
        }


        Arrays.sort(arr, (s1, s2) -> (s2+s1).compareTo(s1+s2));

        StringBuilder sb = new StringBuilder();

        for(String s : arr)
        sb.append(s);


        if(arr[0].equals("0"))
        return "0";

        return sb.toString();

    }
}