Skip to content

Painting Fence

Level: L3-L5 Topics: Dynamic Programming, Recursion, Divide and Conquer

Problem Statement

You have a fence made of N vertical planks standing side by side. Each plank has a given height (in meters). You need to paint the entire fence using a 1-meter-wide brush. The brush can make two types of strokes:

  • Vertical stroke: Paints one full plank from bottom to top (regardless of plank height) — costs 1 stroke.
  • Horizontal stroke: Paints a 1-meter-high strip across one or more consecutive planks — costs 1 stroke. A horizontal stroke can only extend across planks that are all at least as tall as the strip's height.

You may paint the same area multiple times (overlapping strokes are allowed). Find the minimum number of strokes needed to paint the entire fence.

Background & Constraints

  • Each plank has height h_i >= 1.
  • A vertical stroke covers one plank entirely: 1 stroke per plank.
  • A horizontal stroke covers a 1-meter-high row across any number of consecutive planks (as long as all planks in the range are tall enough at that height level).
  • N can be up to 5000.
  • Plank heights can be up to 10^9, but the recurrence depends on relative heights, not absolute values.

Examples

Example 1:

Plank heights: [2, 2, 2]

Option A (all vertical): 3 strokes
Option B (all horizontal): 2 horizontal strokes (one at height 1, one at height 2)

Minimum: 2 strokes

Example 2:

Plank heights: [1, 3, 1]

Option A (all vertical): 3 strokes
Option B (horizontal + vertical):
  - 1 horizontal stroke at height 1 across all 3 planks
  - 2 vertical strokes for the extra height of plank 2
  Total: 3 strokes
Option C: 1 horizontal at height 1 + 1 vertical for plank 2 (covers remaining 2 meters)
  Total: 2 strokes? Wait — the horizontal covers all 3 at height 1. Plank 2 still
  needs heights 2 and 3. That's one vertical stroke for plank 2. Planks 1 and 3 are done.
  Total: 2 strokes.

Minimum: 2 strokes

Example 3:

Plank heights: [3, 1, 3]

Option A (all vertical): 3 strokes
Option B: Horizontal strokes at height 1 (covers all 3), then vertical for left plank
  (2 remaining) and right plank (2 remaining). But we can do horizontals for those too —
  except plank 2 is only height 1, so horizontal strokes at height 2+ can't span across.
  Best: 1 horizontal + 2 verticals = 3, OR just 3 verticals = 3.

Minimum: 3 strokes

Hints & Common Pitfalls

  • Recursive approach: For a range of planks [l, r], find the minimum height m in that range. You can lay m horizontal strokes to cover the bottom m meters of every plank. The remaining painting is on sub-problems where plank heights are reduced by m. Where a plank had height m (the minimum), it splits the range into independent sub-problems.
  • Recurrence: min_strokes(l, r) = min(r - l + 1, min_height(l,r) - base + sum of min_strokes on sub-ranges). The first option is painting each plank vertically. The second option uses horizontal strokes for the common base and recurses on the segments above.
  • Common mistake: Not comparing horizontal vs. vertical. Sometimes it's cheaper to paint each plank individually rather than using horizontal strokes (e.g., when planks are very tall but narrow).
  • Key observation: At each recursive level, you choose between "paint everything vertically" (cost = number of planks) or "paint horizontal base + recurse on segments above the minimum."

Follow-Up Questions

  1. What is the time complexity of your recursive solution? Can you optimize it with memoization?
  2. How do you efficiently find the minimum height in a range? (Consider sparse tables or segment trees.)
  3. What if the brush width is W meters instead of 1? How does this change horizontal strokes?
  4. What if there is a cost difference between horizontal and vertical strokes?
  5. Can you solve this in O(N log N) time?