Skip to content

Vegetable Garden

Level: L3 Topics: Backtracking, Flood Fill, Connected Components, Grid Problems

Problem Statement

You have an N x M garden grid and K types of crops. For each crop type, you are given the exact number of cells it should occupy. You must plant the garden such that:

  1. Every cell is planted with exactly one crop type.
  2. Each crop type occupies exactly its required count of cells.
  3. All cells of the same crop type must form a single connected patch (connected horizontally or vertically — not diagonally).

Find any valid arrangement, or report that none exists.

Background & Constraints

  • N * M equals the total sum of all crop counts.
  • K is typically small (2 to 5 crop types).
  • The grid dimensions can vary (e.g., 3x4, 5x5, or even 1xM).
  • A crop count of 0 means that crop type is not planted at all.
  • Connectivity is defined by 4-directional adjacency (up, down, left, right).

Examples

Input: Grid 3x4, crops: {A: 5, B: 4, C: 3}

One valid output:

A  A  A  B
A  A  B  B
C  C  C  B
  • A occupies cells (0,0), (0,1), (0,2), (1,0), (1,1) — 5 cells, connected.
  • B occupies cells (0,3), (1,2), (1,3), (2,3) — 4 cells, connected.
  • C occupies cells (2,0), (2,1), (2,2) — 3 cells, connected.

Hints & Common Pitfalls

  • Use backtracking: fill the grid cell by cell (e.g., left-to-right, top-to-bottom). For each cell, try each crop type that still has remaining count.
  • After placing a crop in a cell, check that connectivity is still achievable. A useful check: ensure the placed cells of each type are still contiguous (no isolated islands that cannot merge).
  • Pruning is essential for performance. If a crop type's placed cells become disconnected with no way to bridge them, backtrack immediately.
  • Flood fill (BFS/DFS) is useful for verifying connectivity of a crop's region.
  • A greedy approach (grow one crop at a time by expanding from a seed cell) can be simpler to implement and often works well.

Edge Cases

  • Vertical or horizontal line gardens (N x 1 or 1 x M): Connectivity reduces to a 1D problem. Each crop must occupy a contiguous segment. This is equivalent to partitioning a line into K contiguous segments — a much simpler subproblem.
  • Crop count of zero: Simply skip that crop type. Make sure your solution handles arrays with zeros without crashing.
  • Single crop type: The entire grid is one crop. Trivially valid.

Follow-Up Questions

  1. Two separate gardens: Instead of one N x M grid, you have two square gardens side by side: an N x N garden and an M x M garden. The same crop types and counts apply across both gardens combined. Each crop must still be fully connected — but now connectivity can only exist within a single garden (crops cannot span across both). How do you partition the crop counts between the two gardens and solve each independently?