Skip to main content
Talentd

Widest Possible Fence - Solution & Explanation

HardArrayHash TableCountingEnumeration10 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given a set of fence posts, determine the maximum width of a fence that can be built without any gaps between posts.

Approach 1: Brute Force (O(n^2))

Check all possible pairs of fence posts to find the maximum width. For each pair, verify if all intermediate posts exist. This requires nested loops and results in quadratic time complexity.

Approach 2: Sorting and Greedy (O(n log n))

Sort the fence posts first. Then iterate through the sorted list, keeping track of the maximum gap between consecutive posts. The key insight is that sorting allows you to check adjacent posts efficiently, reducing the problem to a linear scan after sorting.

Recommended for interviews: The optimal approach is sorting followed by a greedy scan. Interviewers expect this solution as it demonstrates both algorithmic thinking and efficiency. Brute force shows basic understanding but lacks optimization.

Solution

We first use a hash table cnt to count the number of planks of each height.

For a target height h, the number of planks of height h we can obtain consists of three parts:

  • Using planks of height h directly, giving cnt[h] planks;
  • If h is even, two planks of height h/2 can be combined into one, giving \lfloor cnt[h/2] / 2 \rfloor planks;
  • For each pair of heights x + y = h with x < y, we can combine min(cnt[x], cnt[y]) planks.

For a fixed h, these three parts and the different height pairs (x, h - x) involve disjoint sets of original planks, so they can be summed directly.

We iterate over each height x in cnt and accumulate the contributions into another hash table t:

  • t[x] \mathrel{+}= cnt[x], using planks of height x directly;
  • t[2x] \mathrel{+}= \lfloor cnt[x] / 2 \rfloor, pairing up two planks of height x;
  • For each height y > x, t[x + y] \mathrel{+}= min(cnt[x], cnt[y]), combining planks of heights x and y.

The answer is the maximum value in t.

The time complexity is O(n + m^2), and the space complexity is O(m), where n is the number of planks and m is the number of distinct heights, with m leq n.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2)O(1)When input size is very small
Sorting and GreedyO(n log n)O(1)General case, optimal solution

Video Solution

Leetcode 4007 | Widest Possible Fence | Greedy | Leetcode biweekly contest 188 • CodeWithMeGuys • 259 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Widest Possible Fence easy or hard?
With a 13.6% acceptance rate, this problem is considered medium difficulty. It requires understanding of sorting and greedy algorithms.
How to solve Widest Possible Fence in O(n log n)?
Sort the fence posts first, then perform a linear scan to find the maximum gap between consecutive posts. This ensures O(n log n) time complexity.
What is the best approach for Widest Possible Fence?
The optimal approach is sorting the fence posts followed by a greedy scan. This achieves O(n log n) time complexity and O(1) space complexity.
Is Widest Possible Fence asked at Google/Amazon/Meta?
This problem tests sorting and greedy algorithms, which are common in interviews at top tech companies like Google and Amazon.
What data structure is used in Widest Possible Fence?
The optimal solution uses sorting, which typically relies on an array or list data structure for efficient access and manipulation.
What is the time complexity of Widest Possible Fence?
The best time complexity is O(n log n) due to the sorting step. The subsequent scan is O(n), but sorting dominates.

Ready to solve this problem?

Practice Widest Possible Fence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays