DEV Community

Tanuja V
Tanuja V

Posted on • Updated on

Largest Number | LeetCode | Java

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 :

  1. Input: The method takes an array of integers nums[] as input.
  2. 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[].
  3. 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.
  4. Build the Largest Number: Initialize a StringBuilder to build the largest number. Append each string from the sorted arr[] to the StringBuilder.
  5. 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.
  6. 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();

    }
}
Enter fullscreen mode Exit fullscreen mode

PS : Do try to learn more about lambda functions in Java as it might come in handy.

Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

Top comments (0)