LeetCode Problem 1449

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

LeetCode 1449 - Form Largest Integer With Digits That Add up to Target

Problem Understanding

This problem asks us to construct the numerically largest possible integer such that the total painting cost of its digits is exactly equal to a given target.

We are given an array cost of length 9. Each index corresponds to a digit from 1 to 9:

• cost[0] is the cost of digit 1
• cost[1] is the cost of digit 2
• ...
• cost[8] is the cost of digit 9

We may use any digit any number of times, as long as the sum of the chosen digit costs equals target.

The key requirement is that we want the numerically largest integer, not necessarily the integer with the largest sum of digits. Numerical comparison between integers represented as strings follows two important rules:

1. A number with more digits is always larger.
2. If two numbers have the same number of digits, the lexicographically larger one is larger.

For example:

• "7772" is larger than "977" because it has 4 digits instead of 3.
• "98" is larger than "89" because the first differing digit is larger.

The constraints are important:

• target can be as large as 5000
• There are only 9 possible digits

These constraints strongly suggest that exhaustive generation of all possible digit combinations is infeasible. Instead, we need a dynamic programming solution that efficiently computes the best possible result for every intermediate target value.

Several edge cases are important:

• It may be impossible to form any number exactly equal to target, in which case we return "0".
• Multiple digits can have the same cost.
• Greedily choosing the largest digit does not always work.
• Maximizing digit count is more important than maximizing individual digit values.

For example, "11111" is larger than "99" because it has more digits.

Approaches

Brute Force Approach

A brute force solution would try every possible sequence of digits whose costs sum to target.

At each step, we could choose any digit from 1 to 9, subtract its cost from the remaining target, and recursively continue building the number. Whenever the remaining target becomes zero, we compare the constructed number against the current best answer.

This approach is correct because it explores every valid combination of digits. Eventually, it will discover the optimal answer.

However, the search space grows exponentially. Since we can reuse digits arbitrarily, the number of possible combinations becomes enormous for large targets such as 5000. Even with pruning, this approach is far too slow.

Optimal Dynamic Programming Approach

The key observation is that this is fundamentally an unbounded knapsack problem.

For every target value from 0 to target, we want to know:

• What is the best number we can form with exactly this cost?

Instead of storing the actual string immediately, we first optimize for the number of digits.

Why?

Because any number with more digits is always larger than a number with fewer digits.

So we define:

• dp[t] = maximum number of digits possible using total cost t

Once we know the maximum possible digit count, we reconstruct the actual largest number greedily.

During reconstruction:

• We try digits from 9 down to 1
• We pick the largest digit that still allows an optimal solution

This guarantees lexicographical maximality while preserving the optimal digit count.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all digit combinations recursively
Optimal Dynamic Programming	O(target × 9)	O(target)	Uses unbounded knapsack DP and greedy reconstruction

Algorithm Walkthrough

1. Create a DP array of size target + 1.

We define dp[t] as the maximum number of digits that can be formed with total cost t.

Initialize:

• dp[0] = 0, because zero cost forms zero digits
• All other entries become negative infinity, representing impossible states

2. Iterate through all target values from 1 to target.

For each target value t, try every digit from 1 to 9.

If the digit's cost is less than or equal to t, and the previous state is valid, update:

dp[t] = max(dp[t], dp[t - digit_cost] + 1)

This transition means:

• Build the best number for cost t - digit_cost
• Add one more digit

3. After filling the DP table, check dp[target].

If it is negative, no valid number exists, so return "0". 4. Reconstruct the actual largest number.

We now know the maximum number of digits possible.

Start from digit 9 down to 1.

For each digit:

• Let its cost be c
• Check whether choosing this digit preserves optimality:

dp[current_target] == dp[current_target - c] + 1

If true:

• Append this digit to the answer
• Reduce the target by c
• Continue

5. Continue until the remaining target becomes zero.

Since we always try larger digits first while preserving optimal digit count, the constructed number is the lexicographically largest valid answer.

Why it works

The DP phase guarantees that dp[t] stores the maximum possible number of digits for every target cost t.

A number with more digits is always numerically larger than one with fewer digits, so maximizing digit count guarantees the highest magnitude.

During reconstruction, we greedily choose the largest digit that still preserves the optimal digit count. Since lexicographical order determines the larger number among equal-length numbers, this produces the globally largest valid integer.

Python Solution

from typing import List

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [-10**9] * (target + 1)
        dp[0] = 0

        # Build DP table
        for current_target in range(1, target + 1):
            for digit in range(1, 10):
                digit_cost = cost[digit - 1]

                if current_target >= digit_cost:
                    dp[current_target] = max(
                        dp[current_target],
                        dp[current_target - digit_cost] + 1
                    )

        # Impossible case
        if dp[target] < 0:
            return "0"

        # Reconstruct largest number
        result = []
        remaining_target = target

        for digit in range(9, 0, -1):
            digit_cost = cost[digit - 1]

            while (
                remaining_target >= digit_cost
                and dp[remaining_target] ==
                dp[remaining_target - digit_cost] + 1
            ):
                result.append(str(digit))
                remaining_target -= digit_cost

        return "".join(result)

The implementation begins by initializing the DP array. Impossible states are represented using a very negative number so they never accidentally become optimal.

The nested loops fill the DP table. For every possible target cost, we try adding each digit. Since digits may be reused infinitely many times, this is an unbounded knapsack transition.

After computing the DP table, we check whether target is reachable. If not, we immediately return "0".

The reconstruction phase is greedy. We iterate from digit 9 down to 1, because larger digits should appear earlier whenever possible.

The critical condition:

dp[remaining_target] == dp[remaining_target - digit_cost] + 1

ensures that selecting the digit still allows us to maintain the optimal number of digits.

Finally, we join all selected digits into the final string.

Go Solution

package main

import "strings"

func largestNumber(cost []int, target int) string {
	dp := make([]int, target+1)

	for i := 1; i <= target; i++ {
		dp[i] = -1000000000
	}

	dp[0] = 0

	// Build DP table
	for currentTarget := 1; currentTarget <= target; currentTarget++ {
		for digit := 1; digit <= 9; digit++ {
			digitCost := cost[digit-1]

			if currentTarget >= digitCost {
				candidate := dp[currentTarget-digitCost] + 1

				if candidate > dp[currentTarget] {
					dp[currentTarget] = candidate
				}
			}
		}
	}

	// Impossible case
	if dp[target] < 0 {
		return "0"
	}

	// Reconstruct answer
	var builder strings.Builder
	remainingTarget := target

	for digit := 9; digit >= 1; digit-- {
		digitCost := cost[digit-1]

		for remainingTarget >= digitCost &&
			dp[remainingTarget] == dp[remainingTarget-digitCost]+1 {

			builder.WriteByte(byte('0' + digit))
			remainingTarget -= digitCost
		}
	}

	return builder.String()
}

The Go implementation follows the same logic as the Python solution.

One important difference is string construction. Since Go strings are immutable, repeatedly concatenating strings would be inefficient. Instead, strings.Builder is used for efficient incremental construction.

The DP array is initialized with a large negative number to represent impossible states, similar to the Python implementation.

Go also requires explicit manual maximum comparisons instead of using Python's built-in max() function.

Worked Examples

Example 1

cost = [4,3,2,5,6,7,2,5,5]
target = 9

Digit costs:

Digit	Cost
1	4
2	3
3	2
4	5
5	6
6	7
7	2
8	5
9	5

DP Construction

Target	Best Digit Count
0	0
1	impossible
2	1
3	1
4	2
5	2
6	3
7	3
8	4
9	4

The maximum digit count for target 9 is 4.

Reconstruction

Start with target = 9.

Try digit 9:

• cost = 5
• dp[9] != dp[4] + 1
• cannot use

Try digit 8:

• same issue

Try digit 7:

• cost = 2
• dp[9] == dp[7] + 1
• choose 7

Remaining target = 7

Again choose 7:

• remaining target = 5

Again choose 7:

• remaining target = 3

Now digit 7 no longer works.

Try digit 2:

• cost = 3
• valid

Remaining target = 0

Result:

"7772"

Example 2

cost = [7,6,5,5,5,6,8,7,8]
target = 12

DP Result

The optimal digit count is 2.

Reconstruction

Try digit 9:

• cost 8
• remaining 4 impossible

Try digit 8:

• cost 7
• remaining 5 possible
• choose 8

Remaining target = 5

Try digit 9:

• impossible

Try digit 5:

• cost 5
• choose 5

Remaining target = 0

Result:

"85"

Example 3

cost = [2,4,6,2,4,6,4,4,4]
target = 5

Every available cost is even, but target is odd.

No combination can sum to 5.

The DP entry for dp[5] remains impossible.

Result:

"0"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(target × 9)	For each target value, we try all 9 digits
Space	O(target)	DP array of size target + 1

The algorithm is efficient because the number of digits is fixed at 9. Even with target = 5000, the total work is only about 45,000 DP transitions, which is very manageable.

The reconstruction step is also linear in the number of digits of the answer, which is at most target.

Test Cases

from typing import List

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [-10**9] * (target + 1)
        dp[0] = 0

        for current_target in range(1, target + 1):
            for digit in range(1, 10):
                digit_cost = cost[digit - 1]

                if current_target >= digit_cost:
                    dp[current_target] = max(
                        dp[current_target],
                        dp[current_target - digit_cost] + 1
                    )

        if dp[target] < 0:
            return "0"

        result = []
        remaining_target = target

        for digit in range(9, 0, -1):
            digit_cost = cost[digit - 1]

            while (
                remaining_target >= digit_cost
                and dp[remaining_target] ==
                dp[remaining_target - digit_cost] + 1
            ):
                result.append(str(digit))
                remaining_target -= digit_cost

        return "".join(result)

solution = Solution()

assert solution.largestNumber(
    [4,3,2,5,6,7,2,5,5], 9
) == "7772"  # Provided example 1

assert solution.largestNumber(
    [7,6,5,5,5,6,8,7,8], 12
) == "85"  # Provided example 2

assert solution.largestNumber(
    [2,4,6,2,4,6,4,4,4], 5
) == "0"  # Impossible target

assert solution.largestNumber(
    [1,1,1,1,1,1,1,1,1], 3
) == "999"  # Prefer lexicographically largest digits

assert solution.largestNumber(
    [5,5,5,5,5,5,5,5,5], 1
) == "0"  # No valid digit can be formed

assert solution.largestNumber(
    [2,2,2,2,2,2,2,2,2], 4
) == "99"  # Largest digits chosen among equal costs

assert solution.largestNumber(
    [1,2,3,4,5,6,7,8,9], 9
) == "111111111"  # Maximum digit count dominates

assert solution.largestNumber(
    [9,9,9,9,9,9,9,9,1], 3
) == "999"  # Single cheap digit repeated

assert solution.largestNumber(
    [6,10,15,40,40,40,40,40,40], 47
) == "111112"  # Mixed combination case

Test Summary

Test	Why
Example 1	Validates standard DP reconstruction
Example 2	Validates lexicographical maximization
Example 3	Validates impossible case
All costs equal to 1	Ensures larger digits are preferred
Target smaller than all costs	Ensures "0" is returned
Equal costs for all digits	Ensures greedy reconstruction works
Cheap small digit	Verifies digit count priority
One extremely cheap digit	Tests repeated digit usage
Mixed cost combination	Tests non-trivial reconstruction

Edge Cases

One important edge case occurs when no valid combination exists. For example, if all digit costs are larger than the target, or if the target cannot be formed by any combination of costs, the DP entry for that target remains invalid. A naive implementation might accidentally construct an empty string or crash during reconstruction. This implementation explicitly checks dp[target] < 0 and returns "0" immediately.

Another subtle edge case occurs when multiple digits share the same cost. In such situations, we must prefer the larger digit to maximize lexicographical order. During reconstruction, iterating from 9 down to 1 guarantees that larger digits are selected first whenever multiple optimal solutions exist.

A third important edge case involves the distinction between digit count and digit value. Many greedy solutions incorrectly try to maximize large digits first. However, a longer number is always larger than a shorter one. For example, "11111" is larger than "99". The DP formulation correctly prioritizes maximizing the number of digits before considering lexicographical order.

A fourth edge case appears when the answer becomes extremely large. Since target can reach 5000, the resulting number may contain thousands of digits. Converting such values into integers would overflow standard numeric types. Returning the answer as a string avoids overflow issues entirely and matches the problem requirements.