Leetcode diary: 179. Largest Number

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This question was harder than I thought! The solution to this was ultimately more of a brain teaser than I thought so I'd like to share the small tip of trick that I used to solve this.

Given an array of positive integers, find the largest permutation of the array as concatenated strings.

[1,2,3] = "321"
[3,30,34,5,9] = "9534330"

The first couple of intuition is immediate:
1.) we'd like to have the biggest values leading the strings, so like 9 would always be the first digit in answer[0], so on.

2.) When we have the numbers in the proper sort, you just need to join them together as a string and it'd work

3.) for numbers of equal starts, like [3, 30, 34], we'd like to come up with an ordering for them.

Number 3 is the trouble maker here. What should we do when we have equal starts but ends in different length? It is obvious that if they are the same length then we would just keep comparing the digits until one digit is larger than the other number's digit.

However, that's not true for numbers of different lengths.

What I thought was that
1.) we'd like the shorter string number first, because we can open up the possibility that a number larger than both the initials can be like between 3 and 32, we'd choose 3 so that we can have 4 in between like: 3432.

However, that's not possible, because the larger of the permutations is actually 4332, in other words, we would never have anything bigger in between two numbers starting with the same digits.

2.) when comparing digits down the line, the shorter string will just get the 0 as replacement value. This does not work

3.) the shorter value will stay at the last while the longer value will start again from index 0 until a number is bigger/smaller
This is the speculation for like 1113 vs 11132, but wouldn't work for [34323,3432]
which would get me:
"34323 3432", instead of:
"3432 34323"
I left the space in the middle so you can see the difference clearly

So in the end what gives? how can we deterministically find the solution? I thought maybe at this point it's impossible to tell, so we'd need to do some type of path finding thingy where we just try all the possibilities. That would be fucking absurd though... except not exactly lol...

instead of writing backtracking or recursion all that jazz. All we need to do to "explore all the possibilities" is to create two strings, A+B and B+A. then we just loop through them and see which one has the first bigger digits. Since they are exactly the same length, there is no problem associated with the iteration!

var largestNumber = function(nums) {

    nums.sort(function(numA, numB){
        const stringA = numA + "";
        const stringB = numB + "";

        if(stringA[0] != stringB[0]) 
            return parseInt(stringA[0]) > parseInt(stringB[0]) ? -1 : 1;
        else {
            const fullAB = stringA + stringB;
            const fullBA = stringB + stringA;
            for(let i = 0; i< fullAB.length; i++) {
                if(fullAB[i] === fullBA[i]) continue;
                return fullAB[i] > fullBA[i] ? -1 : 1
            }
        }

        return 0;
    });

    return nums[0] === 0 ? "0" : nums.join("")
};

the last gotcha is that when you have [0,0]. Your interviewer might just ignore that possibility if you can get the sorting right though.

you could technically just create fullAB and fullBA and not have the if statement. I left it there still since it's what I would do during an interview. It documents the thought process and logic of the problem much better. Your interviewer will likely asks about whether you should leave it there, that's when you say "well...actually we don't need it now do we lol"

Let me know anything on your mind after reading through this, THANKS!