FastPrepFastPrep
Problem Brief

Empty Shelf

OA

You are given a 2D vector bookshelf, where each element represents a book type numbered from 1 to k. The task is to empty the bookshelf by selecting a book and removing all books of the same type that lie in the same row or column as the selected book. The goal is to determine the minimum number of turns needed to completely clear the bookshelf.

For instance, if you select a book of type 2 located at row 0 and column 3, you would remove all books of type 2 present in row 0 and column 3, including the selected book.

1Example 1

Input
bookshelf = [[1, 1, 1], [1, 2, 2], [1, 2, 1]], k = 2
Output
3
Explanation
🐈‍⬛🐈‍⬛

2Example 2

Input
bookshelf = [[1, 2, 2], [1, 2, 2], [2, 1, 2]], k = 2
Output
4
Explanation

For each turn, you select a book and remove all books of the same type either in the same row or column. The objective is to minimize the number of turns it takes to completely empty the bookshelf.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= bookshelf.size() <= 100
  • 1 <= bookshelf[0].size() <= 100
  • 1 <= k <= 100
int emptyShelf(int[][] bookshelf, int k) {
  // Your implementation here
}
Input

bookshelf

[[1, 1, 1], [1, 2, 2], [1, 2, 1]]

k

2

Output

3

Sign in to submit your solution.