What is the time complexity of the Brute Force approach?

The time complexity is O(d^2), where d is the number of digits in n.

What is the most efficient approach for Maximum Product of Two Digits?

The Counting Sort approach is the most efficient with O(d) time complexity and O(1) space complexity.

Why is the space complexity O(1) for the Counting Sort approach?

Because the counting array has a fixed size of 10 (for digits 0-9), regardless of the input size.

Maximum Product of Two Digits

Difficulty: Easy | Acceptance: 69.40% | Paid: No Topics: Math, Sorting

You are given an integer n. Return the maximum product of two digits that can be obtained from the digits of n.

Examples
Constraints
Brute Force
Sorting
Counting Sort

Examples

Input: n = 1234
Output: 12
Explanation: The maximum product is obtained by multiplying 3 and 4 (3 * 4 = 12).

Input: n = 990
Output: 81
Explanation: The maximum product is obtained by multiplying 9 and 9 (9 * 9 = 81).

Input: n = 4321
Output: 12
Explanation: The maximum product is obtained by multiplying 4 and 3 (4 * 3 = 12).

Constraints

10 <= n <= 10⁹

Brute Force

Intuition Convert the integer to a string to easily access individual digits, then iterate through all possible pairs of digits to find the maximum product.

Steps

Convert the integer n to a string s.
Initialize max_prod to 0.
Use two nested loops to iterate over all pairs of indices (i, j) where i < j.
Convert the characters at s[i] and s[j] back to integers, multiply them, and update max_prod if the result is larger.
Return max_prod.

python

Complexity

Time: O(d²), where d is the number of digits in n. Since d is at most 10, this is effectively O(1).
Space: O(d) to store the string representation.
Notes: Simple to implement but slightly less efficient than sorting or counting.

Sorting

Intuition The maximum product of two digits will always be the product of the two largest digits present in the number. We can extract the digits, sort them, and multiply the two largest ones.

Steps

Convert the integer n into a list or array of its digits.
Sort the digits in ascending order.
The two largest digits will be at the end of the sorted array. Multiply them and return the result.

python

Complexity

Time: O(d log d), where d is the number of digits.
Space: O(d) to store the digits.
Notes: Efficient and clean, leveraging built-in sorting algorithms.

Counting Sort

Intuition Since the digits are limited to 0-9, we can use a counting array (frequency array) to count the occurrences of each digit. We then iterate from 9 down to 0 to find the two largest digits.

Steps

Initialize an array count of size 10 with zeros.
Iterate through the digits of n and increment the corresponding index in count.
Iterate from 9 down to 0 to find the first digit with a count greater than 0 (this is the largest digit). Decrement its count.
Continue iterating from 9 down to 0 to find the next digit with a count greater than 0 (this is the second largest digit).
Return the product of these two digits.

python

Complexity

Time: O(d), where d is the number of digits. We iterate through digits once to count and once through the fixed-size array (10) to find maxes.
Space: O(1), as the count array size is fixed at 10 regardless of input size.
Notes: The most optimal approach in terms of time complexity for this specific constraint.