How hard is LeetCode 1363. Largest Multiple of Three?

LeetCode 1363. Largest Multiple of Three is rated Hard on LeetCode.

What is the time complexity of LeetCode 1363. Largest Multiple of Three?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1363. Largest Multiple of Three?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1363. Largest Multiple of Three cover?

LeetCode 1363. Largest Multiple of Three is tagged Greedy, Array, Math, Dynamic Programming and Sorting on LeetCode.

Largest Multiple of Three — LeetCode 1363 Python Solution

HardGreedyArrayMathDynamic ProgrammingSorting

Problem: #1363
Pattern: Greedy
Reading time: 4 min
Source: leetcode.com

The problem

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.

Example

Input: digits = [8,1,9]
Output: "981"

Python solution

Python

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort()
        n = len(digits)
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(digits, 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + 1)
        if f[n][0] <= 0:
            return ""
        arr = []
        j = 0
        for i in range(n, 0, -1):
            k = (j - digits[i - 1] % 3 + 3) % 3
            if f[i - 1][k] + 1 == f[i][j]:
                arr.append(digits[i - 1])
                j = k
        i = 0
        while i < len(arr) - 1 and arr[i] == 0:
            i += 1
        return "".join(map(str, arr[i:]))

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1363. Largest Multiple of Three is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1363. Largest Multiple of Three?: LeetCode 1363. Largest Multiple of Three is rated Hard on LeetCode.
What is the time complexity of LeetCode 1363. Largest Multiple of Three?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1363. Largest Multiple of Three?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1363. Largest Multiple of Three cover?: LeetCode 1363. Largest Multiple of Three is tagged Greedy, Array, Math, Dynamic Programming and Sorting on LeetCode.