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.

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

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.