Largest Multiple of Three - Solution & Explanation
Problem Statement
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] <= 9
Approach Overview
Problem 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 1: Greedy Approach with Sorting
This approach involves sorting the digits in descending order to form the largest number possible and checking its divisibility by 3.
1. Compute the sum of all the digits to determine if the whole number is divisible by 3.
2. If the sum % 3 == 0, the digits form a valid multiple of 3; otherwise, remove the smallest number of digits to make it divisible by 3.
The key is to strategically remove digits with minimal impact on the resulting number’s magnitude by leveraging sorting and divisibility rules.
Sort digits in descending order to form the largest number possible. Check if the sum of the digits is divisible by 3. If not, attempt to remove digits minimally to make the sum divisible by 3.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting can be done in-place.
Approach 2: Digit Counting and Modulo Manipulation
In this approach, rather than sorting, we leverage digit frequency and modulo properties to construct the number that is a multiple of three.
1. Count the frequency of each digit.
2. Calculate the sum of the digits.
3. Depending on sum % 3, remove the minimal digits based on their digital value to correct the sum to be divisible by 3.
Calculate the sum of digits, and adjust by removing the least significant digits with appropriate modulo to ensure divisibility by 3.
Complexity
Time Complexity: O(n), since we have to pass through the array elements a few times without sorting.
Space Complexity: O(1), utilizes fixed utility space to construct numbers.
Approach 3: Greedy + Dynamic Programming + Backtracking
We define f[i][j] as the maximum length of selecting several numbers from the first i numbers, so that the sum of the selected numbers modulo 3 equals j. To make the selected numbers as large as possible, we need to select as many numbers as possible, so we need to make f[i][j] as large as possible. We initialize f[0][0] = 0, and the rest of f[0][j] = -infty.
Consider how f[i][j] transitions. We can choose not to select the i-th number, in which case f[i][j] = f[i - 1][j]; we can also choose to select the i-th number, in which case f[i][j] = f[i - 1][(j - x_i bmod 3 + 3) bmod 3] + 1, where x_i represents the value of the i-th number. Therefore, we have the following state transition equation:
$
f[i][j] = max { f[i - 1][j], f[i - 1][(j - x_i bmod 3 + 3) bmod 3] + 1 }
If f[n][0] \le 0, then we cannot select any number, so the answer string is empty. Otherwise, we can backtrack through the f array to find out the selected numbers.
Define i = n, j = 0, start backtracking from f[i][j], let k = (j - x_i bmod 3 + 3) bmod 3, if f[i - 1][k] + 1 = f[i][j], then we have selected the i-th number, otherwise we have not selected the i-th number. If we have selected the i-th number, then we update j to k, otherwise we keep j unchanged. To make the number of the same length as large as possible, we should prefer to select larger numbers, so we should sort the array first.
The time complexity is O(n times log n), and the space complexity is O(n). Where n$ is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as sorting can be done in-place. |
| Digit Counting and Modulo Manipulation | Time Complexity: O(n), since we have to pass through the array elements a few times without sorting. Space Complexity: O(1), utilizes fixed utility space to construct numbers. |
| Greedy + Dynamic Programming + Backtracking | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Largest Multiple of Three || Leetcode • Pepcoding • 5,823 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Largest Multiple of Three easy or hard?
Largest Multiple of Three Python/Java solution
How to solve Largest Multiple of Three in O(n)?
What is the best approach for Largest Multiple of Three?
Is Largest Multiple of Three asked at Google/Amazon/Meta?
What data structure is used in Largest Multiple of Three?
What is the time complexity of Largest Multiple of Three?
Ready to solve this problem?
Practice Largest Multiple of Three with our built-in code editor and test cases.
Practice on FleetCode