Largest Multiple of Three

This optimal approach enhances the previous method by eliminating the need for sorting, which reduces the time complexity from O(N log N) to O(N). It leverages a frequency map (an array of size 10) to count the occurrences of each digit. This is a form of counting sort.

The core logic remains the same: calculate the sum of digits, find its remainder modulo 3, and remove the minimum number of smallest-valued digits to make the sum a multiple of 3. However, instead of manipulating lists of digits, we simply decrement the counts in our frequency array. For example, to remove the smallest digit with a remainder of 1, we check counts[1], then counts[4], then counts[7] and decrement the first one we find.

After adjusting the counts, we can construct the final, largest number by iterating through our frequency array from 9 down to 0 and appending each digit the number of times it appears. This avoids a final sorting step and is highly efficient.

1. Instead of storing digits in lists, use a frequency array counts of size 10 to store the count of each digit (0-9).
2. Iterate through the input digits once to populate the counts array and calculate the total sum.
3. Determine the remainder rem = sum % 3.
4. If rem is not 0, we must remove certain digits to make the new sum divisible by 3. The goal is to remove the smallest valued digits that satisfy the condition.
   • If rem == 1: We need to remove a total remainder of 1. We first try to remove one digit d where d % 3 == 1 (checking 1, then 4, then 7). If this is not possible, we must remove two digits d where d % 3 == 2 (checking for two from 2, 5, 8).
   • If rem == 2: We need to remove a total remainder of 2. We first try to remove one digit d where d % 3 == 2 (checking 2, then 5, then 8). If not possible, we remove two digits d where d % 3 == 1 (checking for two from 1, 4, 7).
5. The removals are done by decrementing the values in the counts array.
6. After the counts array is finalized, build the result string. Iterate from i = 9 down to 0, appending the digit i to the result counts[i] times. This naturally creates the largest number without explicit sorting.
7. Handle edge cases: If the result string is empty, return "". If it's not empty and starts with '0' (meaning all remaining digits are 0), return "0".

class Solution {
    public String largestMultipleOfThree(int[] digits) {
        int[] counts = new int[10];
        int sum = 0;
        for (int d : digits) {
            counts[d]++;
            sum += d;
        }

        int rem = sum % 3;

        if (rem != 0) {
            // We need to remove digits to make the sum divisible by 3
            if (rem == 1) {
                // Try to remove one digit with rem 1, else two digits with rem 2
                if (!remove(counts, 1)) {
                    remove(counts, 2);
                    remove(counts, 2);
                }
            } else { // rem == 2
                // Try to remove one digit with rem 2, else two digits with rem 1
                if (!remove(counts, 2)) {
                    remove(counts, 1);
                    remove(counts, 1);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 9; i >= 0; i--) {
            for (int j = 0; j < counts[i]; j++) {
                sb.append(i);
            }
        }

        String result = sb.toString();
        if (result.length() > 0 && result.charAt(0) == '0') {
            return "0";
        }

        return result;
    }

    // Tries to remove one smallest digit `d` such that `d % 3 == rem`
    // Returns true if a digit was successfully removed, false otherwise.
    private boolean remove(int[] counts, int rem) {
        for (int i = rem; i < 10; i += 3) {
            if (counts[i] > 0) {
                counts[i]--;
                return true;
            }
        }
        return false;
    }
}