101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Dynamic Programming with Difference State - Complex approach
  2. Simplified Dynamic Programming Approach - Complex approach

Approach 1: Dynamic Programming with Difference State

The key insight for solving this problem is to use dynamic programming with a state that represents the difference between the heights of the two supports.

Let's define dp[diff] as the maximum height of the shorter support when the difference between the heights of the two supports is diff. Our goal is to maximize dp[0], which represents the maximum height when both supports have the same height.

For each rod, we have three options:

  1. Add the rod to the taller support, increasing the difference by the rod's length.
  2. Add the rod to the shorter support, decreasing the difference by the rod's length (or creating a new difference if the shorter support becomes taller).
  3. Don't use the rod.

We'll use a hash map to store the state, as the difference can range from -5000 to 5000 (given the constraints).

Algorithm:

  1. Initialize a hash map dp where dp[diff] = height means that with a difference of diff between the two supports, the maximum height of the shorter support is height.
  2. Initialize dp[0] = 0, meaning that with no rods used, both supports have a height of 0.
  3. For each rod in the input:
  4. a. Create a copy of the current dp map to avoid modifying it while iterating.
  5. b. For each difference diff and height h in the current dp map:
  6. i. Option 1: Add the rod to the taller support, increasing the difference by the rod's length.
  7. - If diff >= 0, then dp[diff + rod] = max(dp[diff + rod], h)
  8. - If diff < 0, then dp[diff + rod] = max(dp[diff + rod], h + rod + diff) if diff + rod >= 0, otherwise dp[diff + rod] = max(dp[diff + rod], h)
  9. ii. Option 2: Add the rod to the shorter support, decreasing the difference by the rod&apos;s length.
  10. - If diff >= 0, then dp[diff - rod] = max(dp[diff - rod], h + rod) if diff - rod >= 0, otherwise dp[rod - diff] = max(dp[rod - diff], h + diff)
  11. - If diff < 0, then dp[diff - rod] = max(dp[diff - rod], h)
  12. iii. Option 3: Don&apos;t use the rod (this is implicitly handled by keeping the original dp values).
  13. Return dp[0], which represents the maximum height when both supports have the same height.

Time Complexity:

O(n * sum)

Where n is the number of rods and sum is the sum of all rod lengths. In the worst case, we need to consider all possible differences, which is bounded by the sum of all rod lengths.

Space Complexity:

O(sum)

We use a hash map to store the maximum height for each possible difference, which is bounded by the sum of all rod lengths.

Approach 2: Simplified Dynamic Programming Approach

We can simplify the previous approach by considering the difference between the heights of the two supports in a more direct way.

Let's define dp[diff] as the maximum height of the first support when the difference between the first and second supports is diff. The height of the second support would then be dp[diff] - diff.

For each rod, we have three options:

  1. Add the rod to the first support, increasing the difference by the rod's length.
  2. Add the rod to the second support, decreasing the difference by the rod's length.
  3. Don't use the rod.

Our goal is to find the maximum value of dp[0], which represents the maximum height when both supports have the same height.

Algorithm:

  1. Initialize a hash map dp where dp[diff] = height means that with a difference of diff between the first and second supports, the maximum height of the first support is height.
  2. Initialize dp[0] = 0, meaning that with no rods used, both supports have a height of 0.
  3. For each rod in the input:
  4. a. Create a copy of the current dp map to avoid modifying it while iterating.
  5. b. For each difference diff and height h in the current dp map:
  6. i. Option 1: Add the rod to the first support, increasing the difference by the rod&apos;s length.
  7. - dp[diff + rod] = max(dp[diff + rod], h + rod)
  8. ii. Option 2: Add the rod to the second support, decreasing the difference by the rod&apos;s length.
  9. - dp[diff - rod] = max(dp[diff - rod], h)
  10. iii. Option 3: Don&apos;t use the rod (this is implicitly handled by keeping the original dp values).
  11. Return dp[0], which represents the maximum height when both supports have the same height.

Time Complexity:

O(n * sum)

Where n is the number of rods and sum is the sum of all rod lengths. In the worst case, we need to consider all possible differences, which is bounded by the sum of all rod lengths.

Space Complexity:

O(sum)

We use a hash map to store the maximum height for each possible difference, which is bounded by the sum of all rod lengths.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function tallestBillboard(rods):
    // Initialize dp map
    dp = new HashMap<Integer, Integer>()
    dp.put(0, 0)  // With no rods used, both supports have height 0
 
    for rod in rods:
        // Create a copy of the current dp map
        currentDp = new HashMap<Integer, Integer>(dp)
 
        for (diff, height) in currentDp:
            // Option 1: Add rod to the taller support
            if diff >= 0:
                dp[diff + rod] = max(dp[diff + rod], height)
            else:
                if diff + rod >= 0:
                    dp[diff + rod] = max(dp[diff + rod], height + rod + diff)
                else:
                    dp[diff + rod] = max(dp[diff + rod], height)
 
            // Option 2: Add rod to the shorter support
            if diff >= 0:
                if diff - rod >= 0:
                    dp[diff - rod] = max(dp[diff - rod], height + rod)
                else:
                    dp[rod - diff] = max(dp[rod - diff], height + diff)
            else:
                dp[diff - rod] = max(dp[diff - rod], height)
 
    return dp[0]  // Return the maximum height when both supports have the same height
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone