Watch 10 video solutions for Largest Multiple of Three, a hard level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Pepcoding has 5,750 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of digits digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order. If there is no answer return an empty string.
Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.
Example 1:
Input: digits = [8,1,9] Output: "981"
Example 2:
Input: digits = [8,6,7,1,0] Output: "8760"
Example 3:
Input: digits = [1] Output: ""
Constraints:
1 <= digits.length <= 1040 <= digits[i] <= 9Problem Overview: You are given an array of digits (0–9). Rearrange some or all digits to form the largest possible integer that is divisible by 3. If no such number exists, return an empty string. The key constraint comes from divisibility rules: a number is divisible by 3 when the sum of its digits is divisible by 3.
Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)
This approach uses a greedy idea based on the divisibility rule of 3. First, sort the digits in ascending order so you can easily remove the smallest digits when adjustments are needed. Compute the total digit sum and check sum % 3. If the remainder is 1, remove the smallest digit with remainder 1; otherwise remove two digits with remainder 2. If the remainder is 2, remove the smallest digit with remainder 2 or two digits with remainder 1. After removal, sort the remaining digits in descending order to form the largest possible number.
The greedy insight is that removing the smallest possible digits preserves the maximum value of the final number. Sorting helps you quickly identify candidates for removal and construct the final result. Time complexity is O(n log n) due to sorting, and space complexity is O(n) for storing digits. This method works well when you want a straightforward implementation using basic array operations and greedy reasoning.
Approach 2: Digit Counting and Modulo Manipulation (O(n) time, O(1) space)
This approach avoids sorting by counting occurrences of each digit (0–9). First compute the sum of all digits and determine sum % 3. Maintain counts of digits grouped by their modulo with 3. If the remainder is 1, remove the smallest digit whose value % 3 == 1; if none exist, remove two digits whose value % 3 == 2. If the remainder is 2, remove the smallest digit whose value % 3 == 2, or two digits whose value % 3 == 1.
After adjusting the counts, reconstruct the result by iterating from digit 9 down to 0 and appending digits according to their frequency. Because digit range is fixed (0–9), counting and reconstruction run in linear time relative to the input size. Time complexity is O(n) and space complexity is O(1) since the digit frequency array has constant size. This technique combines greedy selection with modulo arithmetic and is often discussed alongside dynamic programming-style remainder reasoning, though the final implementation is purely greedy.
Recommended for interviews: The digit counting and modulo manipulation approach is typically the expected optimal solution. Interviewers want to see that you recognize the divisibility-by-3 rule and adjust the digit set greedily while preserving the largest lexicographic order. Starting with the sorting-based greedy solution shows clear reasoning, while the counting optimization demonstrates stronger algorithmic insight and reduces the complexity to O(n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(n) | Best for a straightforward implementation using sorting and simple greedy removal logic. |
| Digit Counting and Modulo Manipulation | O(n) | O(1) | Optimal approach when you want linear time by avoiding sorting and using digit frequency counting. |