Widest Possible Fence - Video Solutions
Leetcode 4007 | Widest Possible Fence | Greedy | Leetcode biweekly contest 188
Widest Possible Fence - Video Solution
Watch 2 video solutions for Widest Possible Fence, a hard level problem involving Array, Hash Table, Counting. This walkthrough by CodeWithMeGuys has 259 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] = 5planks[5] = 5planks[0] + planks[6] = 1 + 4 = 5planks[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 <= 10001 <= 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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | When input size is very small |
| Sorting and Greedy | O(n log n) | O(1) | General case, optimal solution |