Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Problem listSolution
DescriptionHints 4SolutionVideo 14:10

4007. Widest Possible Fence

Hard16.9% acceptance

You are given an integer array planks, where planks[i] represents the height of the ith wooden plank. Each plank has a width of 1 unit.

You want to build a fence consisting of planks that all have the same height.

You may either use a plank as is, or combine exactly two distinct original planks into a single plank whose height equals the sum of their heights. Each original plank can be used at most once, and not all original planks need to be used.

Return the maximum possible width of the fence that can be built.

Example 1:

Input: planks = [1,3,2,5,7,5,4,2,1]

Output: 4

Explanation:

We can have four planks of height 5.

  • planks[3] = 5
  • planks[5] = 5
  • planks[0] + planks[6] = 1 + 4 = 5
  • planks[1] + planks[2] = 3 + 2 = 5

Hence, the maximum width is 4.

Example 2:

Input: planks = [2,3,7]

Output: 1

Explanation:

  • It is impossible to form two planks of the same height, even after combining two distinct original planks.
  • Since not all original planks need to be used, we can choose any one plank as the fence.
  • Therefore, the maximum possible width is 1.

Constraints:

  • 1 <= planks.length <= 1000
  • 1 <= planks[i] <= 109

Topics

ArrayCountingEnumerationHash Table

Hints open one at a time

Hint 1

Fix the common fence height h. Every original plank of height h can be used by itself.

Hint 2

Any remaining plank of height x < h can only be used by pairing it with a plank of height h - x.

Hint 3

Using the frequency of each height, count these disjoint pairs with min(freq[x], freq[h - x]); when x == h - x, use freq[x] / 2.

Hint 4

It is enough to try heights that occur as an original plank height or as the sum of two original plank heights. Take the maximum number of single planks and pairs over all such heights.

14:10
Still stuck?Read the written solution, or watch a walkthrough.
Open solution
Loading editor…
1class Solution:
2 def maximumWidth(self, planks: list[int]) -> int:
3
Starter codePython 3Spaces: 4
Examples
Input
[1,3,2,5,7,5,4,2,1]
Input
[2,3,7]
Your code is saved on this device.Solution