You are given a list cropArray, where each value represents the frequency of one type of crop.
The crop at index 0 is represented by crop id 1, the crop at index 1 is represented by crop id 2, and so on.
You are also given a grid with rowCount rows and columnCount columns. The total number of cells in the grid is exactly equal to the sum of all frequencies in cropArray.
Your task is to fill the grid using the crop ids such that each crop id appears exactly as many times as its frequency, and all cells belonging to the same crop id form one connected group.
Two cells are considered connected if they share an edge horizontally or vertically. Diagonal connection does not count.
To make the output deterministic, fill the grid in a snake order: fill the first row from left to right, the second row from right to left, the third row from left to right, and continue alternating in this way. Place crop ids in increasing order, starting from crop id 1.
Method Signature
Fill Grid
List<String> fillCropGrid(List<Integer> cropArray, int rowCount, int columnCount)
cropArray is a list where cropArray[i] represents the frequency of crop id i + 1.rowCount is the number of rows in the grid.columnCount is the number of columns in the grid.- The method returns the filled grid as a
List<String>.
- Each returned string represents one row of the grid.
- Inside each row string, crop ids must be separated by commas.
Rules
- Each crop id must appear exactly according to its frequency in
cropArray.
- For every crop id, all its cells must be connected horizontally or vertically.
- Crop ids must be assigned in increasing order.
- The grid must be filled using snake order.
- No cell may remain empty.
- No extra crop id may be added.
Snake Order
- For row
0, fill columns from 0 to columnCount - 1.
- For row
1, fill columns from columnCount - 1 to 0.
- For row
2, fill columns from 0 to columnCount - 1.
- Continue alternating direction for every row.
Constraints
1 ≤ cropArray.size() ≤ 10001 ≤ rowCount ≤ 10001 ≤ columnCount ≤ 10001 ≤ cropArray[i] ≤ rowCount * columnCountsum(cropArray) = rowCount * columnCountrowCount * columnCount ≤ 100,000
Examples
Example 1
fillCropGrid(cropArray = List.of(3, 2, 1), rowCount = 2, columnCount = 3)
Output: List.of("1,1,1", "3,2,2")
Explanation: The snake order positions are filled as: (0,0), (0,1), (0,2), (1,2), (1,1), (1,0). The first 3 snake-order cells are filled with crop id 1, the next 2 snake-order cells are filled with crop id 2, and the final 1 snake-order cell is filled with crop id 3. Therefore, the final grid is List.of("1,1,1", "3,2,2").
Example 2
fillCropGrid(cropArray = List.of(2, 4, 2), rowCount = 2, columnCount = 4)
Output: List.of("1,1,2,2", "3,3,2,2")
Explanation: The snake order positions are filled as: (0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1), (1,0). The first 2 snake-order cells are filled with crop id 1. The next 4 snake-order cells are filled with crop id 2. The final 2 snake-order cells are filled with crop id 3. Therefore, the final grid is List.of("1,1,2,2", "3,3,2,2").
Example 3
fillCropGrid(cropArray = List.of(1, 1, 1, 1), rowCount = 1, columnCount = 4)
Output: List.of("1,2,3,4")
Explanation: There is only one row, so the snake order is the same as left to right order. Each crop id appears exactly once. Therefore, the final grid is List.of("1,2,3,4").
Example 4
fillCropGrid(cropArray = List.of(4, 2), rowCount = 3, columnCount = 2)
Output: List.of("1,1", "1,1", "2,2")
Explanation: The snake order positions are filled as: (0,0), (0,1), (1,1), (1,0), (2,0), (2,1). The first 4 snake-order cells are filled with crop id 1. The remaining 2 snake-order cells are filled with crop id 2. Therefore, the final grid is List.of("1,1", "1,1", "2,2").
Example 5
fillCropGrid(cropArray = List.of(2, 3, 4), rowCount = 3, columnCount = 3)
Output: List.of("1,1,2", "2,2,3", "3,3,3")
Explanation: The snake order positions are filled as: (0,0), (0,1), (0,2), (1,2), (1,1), (1,0), (2,0), (2,1), (2,2). The first 2 snake-order cells are filled with crop id 1. The next 3 snake-order cells are filled with crop id 2. The final 4 snake-order cells are filled with crop id 3. Therefore, the final grid is List.of("1,1,2", "2,2,3", "3,3,3").