LeetCode 956 (Hard). Solution of the day. Tallest Billboard. Swift. DP.

Description

You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.

You are given a collection of rods that can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.

Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.

Example 1: Input: rods = [1,2,3,6]. Output: 6.

Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.

Example 2: Input: rods = [1,2,3,4,5,6]. Output: 10.

Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.

Example 3: Input: rods = [1,2]. Output: 0.

Explanation: The billboard cannot be supported, so we return 0.

Constraints:

1 <= rods.length <= 20

1 <= rods[i] <= 1000

sum(rods[i]) <= 5000

Approach

The code uses dynamic programming to solve the problem. It maintains a dictionary dp, where the keys represent the possible height differences between the two billboards, and the values represent the maximum sum of heights achieved for each height difference.

The code iterates through each rod in the given input rods. For each rod i, it creates a new dictionary cur to store the updated values for dp. Then, it iterates through the existing entries in dp and updates the values in cur based on three cases:

1. Adding the current rod i to the same height difference: cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])
2. Keeping the same height difference: cur[sum] = max(dp[sum]!, cur[sum, default: 0])
3. Subtracting the current rod i from the height difference: cur[sum - i] = max(dp[sum]!, cur[sum - i, default: 0])

After iterating through all the rods, the final result is obtained from dp[0], which represents the maximum possible sum of heights for a height difference of 0 (i.e., the two billboards have equal heights).

Complexity

Time complexity: O(n * m).

Code (Swift)

class Solution {
    func tallestBillboard(_ rods: [Int]) -> Int {
        var dp = [0: 0]

        for i in rods {
            var cur = [Int: Int]()
            for (sum, height) in dp {
                cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])
                cur[sum] = max(dp[sum]!, cur[sum, default: 0])
                cur[sum - i] = max(dp[sum]!, cur[sum - i, default: 0])
            }
            dp = cur
        }

        return dp[0, default: 0]
    }
}        

Sources:?Github

Full Version / DEV Community

https://dev.to/sergeyleschev/leetcode-956-hard-tallest-billboard-swift-dp-on-16bg

Contacts

I have a clear focus on time-to-market and don't prioritize technical debt. And I took part in the Pre-Sale/RFX activity as a System Architect, assessment efforts for Mobile (iOS-Swift, Android-Kotlin), Frontend (React-TypeScript) and Backend (NodeJS-.NET-PHP-Kafka-SQL-NoSQL). And I also formed the work of Pre-Sale as a CTO from Opportunity to Proposal via knowledge transfer to Successful Delivery.

??? #startups #management #cto #swift #typescript #database

?? Email:?[email protected]

?? LinkedIn:?https://linkedin.com/in/sergeyleschev/

?? LeetCode:?https://leetcode.com/sergeyleschev/

?? Twitter:?https://twitter.com/sergeyleschev

?? Github:?https://github.com/sergeyleschev

?? Website:?https://sergeyleschev.github.io

?? Reddit:?https://reddit.com/user/sergeyleschev

?? Quora:?https://quora.com/sergey-leschev

?? Medium:?https://medium.com/@sergeyleschev

??? Design Patterns (PDF):?Download