1449. Form Largest Integer With Digits That Add up to Target


Problem Description

This LeetCode problem asks us to construct the largest possible integer, digit by digit, using a given cost array where each element corresponds to the cost of painting a digit, and a target which is the total cost allowed. The digits are 1-indexed in association to their index in the cost array, meaning the cost of painting the digit 1 is cost[0], the cost of painting the digit 2 is cost[1], and so on. The goal is to maximize the integer value created without exceeding the target cost, which includes ensuring no digits in the number are 0. If it's not possible to paint any integer with the given cost and target constraints, we should return the string "0".

The returned integer should be in the form of a string since it could be very large, beyond standard integer ranges.

Here’s a breakdown of the rules:

  • Use the provided cost array where cost[i] represents the cost to paint the digit i+1.
  • The sum of costs for the digits used must be exactly equal to the target.
  • All digits in the painted integer must be greater than 0.
  • The resulting integer should be as large as possible.

Intuition

To solve the problem, we use dynamic programming because we detect overlapping subproblems and an optimal substructure: each step of constructing our maximum integer depends on the choices made in the previous steps.

The intuition behind the solution is to use dynamic programming to keep track of two pieces of information:

  1. The maximum number of digits (f) we can paint using a certain cost, up to the target.
  2. The remaining cost after painting a digit at the current position (g).

We initialize an array f with negative infinity values to store the maximum number of digits that can be painted for each cost up to target, with the extra element for case 0. Another array g starts with zeros and is used to track the cost remaining after painting the last digit.

We iterate over the cost of each digit and the possible total costs up to the given target. We compare if using the current digit would allow us to paint more digits than skipping it. If adding the current digit does not increase the number of digits or decreases it, we inherit the previous maximum (f[i - 1][j]). Otherwise, we update our maximum and the remaining cost.

Once we filled our dynamic programming arrays, we can build the largest number by starting from the largest digit and the target cost, and backtrack using the transitions stored in g. If we can't construct any number, we return "0", as indicated when f[9][target] is negative.

Finally, we construct the result by appending the digits to the answer as we go through the g array to backtrack the digits that make up the maximum number. We concatenate and return the digits in reverse order since we start with the largest possible digit and go down to the smallest to maximize the integer value.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution provided employs dynamic programming, a method for solving complex problems by breaking them down into simpler subproblems. This is done by storing the results of subproblems, so they do not have to be recalculated every time they are needed. Here are the main steps followed in the implementation:

  1. Initialization: Two two-dimensional arrays f and g are created with 10 rows (digits 0 through 9, including a dummy row for 0) and target + 1 columns (representing costs from 0 to target). The array f is initialized with negative infinity to represent the impossibility of reaching that cost with a combination of digits. This primarily aids in identifying non-viable solutions. The role of array g is to track the previous cost that led to the current digit to facilitate backtracking later.

  2. Filling the DP Arrays: The solution iterates over each digit's cost and each possible total cost up to the target. If the current cost is below the digit's cost (the digit cannot be "painted") or if choosing the current digit does not increase the painted digit count, the value from the previous row is carried forward (f[i - 1][j]). If the current digit can be used and increases the total painted digit count, f[i][j] gets updated to f[i][j - c] + 1 (c is the current digit's cost), and g[i][j] gets updated to j - c — essentially recording what the new total cost would be after using this digit.

  3. Constructing the Solution: After populating the arrays, array f is checked to determine if any solution exists. If f[9][target] is negative, this implies it is impossible to paint any digits to reach the exact target cost, and thus "0" is returned. However, if a viable solution is found, we reconstruct the largest number by backtracking through the g array from the largest digit (9) and the target cost. As long as the current cost does not match the cost stored in g[i][j], we are still using the same digit, so we append it to the answer and update j to g[i][j]. If it matches, we move to the next smaller digit (decrement i).

  4. Backtracking for the Answer: We backtrack through g, appending the corresponding digits until we reach the start. The transition j = g[i][j] means we have used the i-th digit and adjusted our target cost. If j == g[i][j], we move on to the next smaller digit since the current one did not contribute to the number.

  5. Return the Answer: When the iteration is complete, we join the digits appended in reverse order (largest to smallest for maximum value) to form the required maximal integer as a string, which is returned as the final solution.

The algorithm uses dynamic programming with backtracking to solve the problem, ensuring we use the maximum allowable number of digits to form the largest value without exceeding the target cost.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above.

Suppose we are given the following cost array and target:

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

The cost array represents the cost to paint digits 1-9, meaning it costs 4 to paint digit 1, 3 to paint digit 2, and so on. We want to construct the largest possible integer with the total cost not exceeding 9.

Step-by-Step Solution:

  1. Initialization: Create f and g arrays. f[0..9][0..9] initializes with negative infinity -inf except f[0][0] which is 0. g[0..9][0..9] initializes with zeros.

  2. Filling the DP Arrays:

    • For i=1 to 9 (representing digits 1 to 9):
    • For j=1 to 9 (representing current target cost from 1 to 9):
      • Check if the cost of the current digit (cost[i-1]) is less than or equal to j. If it's greater, the digit can't be used.
      • If the current digit can be used, check if f[i-1][j] < f[i][j-cost[i-1]] + 1. If true, update f[i][j] to f[i][j-cost[i-1]] + 1 and g[i][j] to j-cost[i-1].
  3. Constructing the Solution:

    • Starting from f[9][9], we find it is not -inf, meaning we can form a number with the given target.
    • Start backtracking from i=9, j=9 (the largest digit and target cost).
  4. Backtracking for the Answer:

    • While i > 0:
      • If j != g[i][j], append digit i to the answer and update j to g[i][j].
      • Otherwise, decrement i to move to the next smaller digit.
  5. Return the Answer:

    • Reverse the accumulated digits since we started from the largest and decrementing, and return as the final answer.

Example in Action:

Let's follow steps 2-4 with our example:

  • We iterate through each digit's cost and find that for:

    • j=9, digit 7 (cost[6]=2) is the largest digit we can start with.
    • Update f[7][9] from -inf to f[7][7] + 1 (f[7][7] was previously calculated as 3, because it is the sum of three 7s, whose cost is 2 each).
    • Update g[7][9] to 9 - cost[6], which is 7.
  • Now we backtrack from f[9][9]:

    • We find f[9][9] is -inf, but f[7][9] is 4, so we append 7 and update j to g[7][9], which is 7.
    • We move to the next iteration and check f[7][7]. Again, we can use 7, so we append another 7 and update j to g[7][7], which is 5.
    • This process continues until we can no longer use digit 7 or any higher digit without exceeding our remaining target cost.
    • Eventually, we hit j=1, and from our cost array, we see that we can use digit 3 (cost[2]=2), giving us the final digit and using up the remaining target cost.
  • The sequence of chosen digits is 7, 7, 7, 3, and the answer is built as 7733.

Following these steps, we've constructed the largest possible integer with a total cost of 9, which is 7733.

Solution Implementation

1from typing import List
2
3class Solution:
4    def largestNumber(self, cost: List[int], target: int) -> str:
5        # Initialize a table to store maximum digit counts that can be obtained
6        max_digit_counts = [[float('-inf')] * (target + 1) for _ in range(10)]
7        max_digit_counts[0][0] = 0  # Base case: zero cost leads to zero digits
8      
9        # Initialize a table for backtracking the choices made
10        choice_backtrack = [[0] * (target + 1) for _ in range(10)]
11      
12        # Fill the tables with dynamic programming approach
13        for digit, single_cost in enumerate(cost, start=1):
14            for budget in range(target + 1):
15                if budget < single_cost or max_digit_counts[digit][budget - single_cost] + 1 < max_digit_counts[digit - 1][budget]:
16                    # If we don't take the current digit
17                    max_digit_counts[digit][budget] = max_digit_counts[digit - 1][budget]
18                    choice_backtrack[digit][budget] = budget
19                else:
20                    # Take the current digit
21                    max_digit_counts[digit][budget] = max_digit_counts[digit][budget - single_cost] + 1
22                    choice_backtrack[digit][budget] = budget - single_cost
23      
24        # If we cannot reach the target with the given costs, return "0"
25        if max_digit_counts[9][target] < 0:
26            return "0"
27      
28        # Backtrack from the filled tables to find the largest number
29        result = []
30        current_digit, current_budget = 9, target
31        while current_digit > 0:
32            if current_budget == choice_backtrack[current_digit][current_budget]:
33                # Move to the previous digit if no current digit is taken
34                current_digit -= 1
35            else:
36                # Add the current digit to the result and update the budget
37                result.append(str(current_digit))
38                current_budget = choice_backtrack[current_digit][current_budget]
39              
40        # Join the list of digits to form the largest number string
41        return "".join(result)
42
43# Example usage:
44solution = Solution()
45print(solution.largestNumber(cost=[4, 3, 2, 5, 6, 7, 2, 5, 5], target=9))  # Should return the largest possible number formed
46
1import java.util.Arrays;
2
3class Solution {
4  
5    // Method to find the largest number that can be formed from the given 'cost' array and 'target' value.
6    public String largestNumber(int[] cost, int target) {
7      
8        final int NEG_INF = Integer.MIN_VALUE / 2; // A sufficiently small number to represent negative infinity.
9        int[][] dp = new int[10][target + 1]; // dp array to store the max length of number for a given target.
10        int[][] backtrack = new int[10][target + 1]; // array for backtracking to construct the answer.
11      
12        // Initialize the dp array with negative infinity for cases except the zero target.
13        for (int[] row : dp) {
14            Arrays.fill(row, NEG_INF);
15        }
16        dp[0][0] = 0; // Base case: target of zero can be achieved with length 0 number.
17      
18        // Fill the dp array and backtrack array with optimal values.
19        for (int i = 1; i <= 9; ++i) {
20            int c = cost[i - 1]; // Cost to create digit 'i'.
21            for (int j = 0; j <= target; ++j) {
22                // Check if we can't afford the cost of the digit 'i' or not choosing digit 'i' is better.
23                if (j < c || dp[i][j - c] + 1 < dp[i - 1][j]) {
24                    dp[i][j] = dp[i - 1][j]; // Not choosing digit 'i'.
25                    backtrack[i][j] = j; // Reference target remains the same as we didn't choose digit 'i'.
26                } else {
27                    // Choose digit 'i' and update the maximum length.
28                    dp[i][j] = dp[i][j - c] + 1;
29                    backtrack[i][j] = j - c; // Update reference target to the one after choosing digit 'i'.
30                }
31            }
32        }
33      
34        // If we can't achieve the target, return "0".
35        if (dp[9][target] < 0) {
36            return "0";
37        }
38      
39        // Reconstruct the largest number by backtracking.
40        StringBuilder largestNumber = new StringBuilder();
41        for (int i = 9, j = target; i > 0;) {
42            // Check if we have moved to the previous digit.
43            if (j == backtrack[i][j]) {
44                --i; // Move to the previous digit.
45            } else {
46                // Include the digit 'i' in our answer.
47                largestNumber.append(i);
48                j = backtrack[i][j]; // Update j to the previous state.
49            }
50        }
51      
52        // Return the constructed largest number as a string.
53        return largestNumber.toString();
54    }
55}
56
1class Solution {
2public:
3    string largestNumber(vector<int>& costs, int target) {
4        const int INF = 1 << 30; // Define a large value as 'infinity' which is out of reach
5        vector<vector<int>> dp(10, vector<int>(target + 1, -INF)); // DP array
6        vector<vector<int>> backtrack(10, vector<int>(target + 1)); // Backtrack array
7        dp[0][0] = 0; // Base case: zero cost for a target of 0
8
9        // Populate the dp and backtrack arrays
10        for (int digit = 1; digit <= 9; ++digit) {
11            int cost = costs[digit - 1];
12            for (int j = 0; j <= target; ++j) {
13                if (j < cost || dp[digit][j - cost] + 1 < dp[digit - 1][j]) {
14                    // If we cannot take the current digit or taking it results in a number with fewer digits
15                    dp[digit][j] = dp[digit - 1][j];
16                    backtrack[digit][j] = j;
17                } else {
18                    // Taking the current digit results in a number with more digits
19                    dp[digit][j] = dp[digit][j - cost] + 1;
20                    backtrack[digit][j] = j - cost;
21                }
22            }
23        }
24      
25        // If no combination adds up to the target, then return "0"
26        if (dp[9][target] < 0) {
27            return "0";
28        }
29      
30        // Reconstruct the largest number from the backtrack information
31        string answer;
32        for (int i = 9, j = target; i > 0;) { // Start from the largest digit and the target
33            if (backtrack[i][j] == j) {
34                // If we did not use the digit i, go to the next smaller digit
35                --i;
36            } else {
37                // Used the digit, append to answer and update the remaining target
38                answer += '0' + i;
39                j = backtrack[i][j];
40            }
41        }
42      
43        return answer;
44    }
45};
46
1function largestNumber(costs: number[], target: number): string {
2    // Define a large number as a placeholder for the concept of infinity.
3    const INFINITY = 1 << 30;
4    // f will store the maximum number of digits that can be obtained
5    const maxDigits: number[][] = Array.from({ length: 10 }, () => Array(target + 1).fill(-INFINITY));
6    // g will store how we can reach the current state
7    const prevState: number[][] = Array.from({ length: 10 }, () => Array(target + 1).fill(0));
8    // With 0 cost, we can always construct 0
9    maxDigits[0][0] = 0;
10  
11    // Loop through each digit from 1 to 9
12    for (let i = 1; i <= 9; ++i) {
13        const cost = costs[i - 1];
14        for (let j = 0; j <= target; ++j) {
15            // If we cannot spend 'cost' to put the i-th digit or putting it does not increase
16            // the number of digits we found, we just inherit the maxDigits as is from i - 1.
17            if (j < cost || maxDigits[i][j - cost] + 1 < maxDigits[i - 1][j]) {
18                maxDigits[i][j] = maxDigits[i - 1][j];
19                prevState[i][j] = j;
20            } else {
21                // Otherwise, we use the i-th digit, increase the number of digits, and set how
22                // we can reach this state.
23                maxDigits[i][j] = maxDigits[i][j - cost] + 1;
24                prevState[i][j] = j - cost;
25            }
26        }
27    }
28  
29    // If there's no way to obtain the target using any combination of digits, return '0'
30    if (maxDigits[9][target] < 0) {
31        return '0';
32    }
33  
34    // Reconstruct the answer by tracing back the states.
35    const answerDigits: number[] = [];
36    let i = 9, j = target;
37  
38    while (i > 0) {
39        // If the current state is the same as the previous state,
40        // it means the digit i is not used, move to the previous digit.
41        if (prevState[i][j] === j) {
42            --i;
43        } else {
44            // Otherwise, the digit i is used. Add it to the answer and
45            // move to the previous state that leads here.
46            answerDigits.push(i);
47            j = prevState[i][j];
48        }
49    }
50    // Join all digits to form the answer string.
51    return answerDigits.join('');
52}
53

Time and Space Complexity

The given code uses dynamic programming to find the largest number that can be formed by using the cost array where each cost[i] corresponds to the cost of digit i+1, with the goal of exactly matching the target cost.

Time Complexity

The time complexity of the algorithm is determined by two nested loops and the operations within them.

  • The outer loop runs for each digit from 1 to 9, since enumerate(cost, 1) starts from 1 and goes up to the length of the cost, which is 9 for digit-to-cost mapping.
  • The inner loop runs for each value from 0 to the target.

Inside the inner loop, the code performs a constant amount of work, with no loops or recursive calls. Therefore, the time complexity is the product of the number of loops and the work inside them.

Thus, the time complexity is O(9 * target), simplifying to O(target) since 9 is a constant.

Space Complexity

The space complexity is determined by the size of the two-dimensional arrays f and g.

  • There are two arrays f and g, each with dimensions 10 x (target + 1). The 10 comes from the digits 0 to 9, and the target + 1 from the range of possible cost values from 0 to target.

As such, the space complexity is O(2 * 10 * (target + 1)), which simplifies to O(target) since the 10 and 2 are constants.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄