To solve this problem, the idea is to loop over every square in the cookie. Every time you get to a piece of chocolate 1, you should increment the number of chocolate chips you've seen. You should then mark the entire chocolate chip as visited so that you don't count it again. We'll do this by setting the entire chocolate chip to have a value of 0 so that it looks like dough from now on.

Here's the code for this:

This code works, but we still haven't written the function for removing a chocolate chip removeChip. We'll create that function right now.

0. Problem

The function should take in a row and col, and it should set every square on that chocolate chip to have a value of 0.

1. Recursion

To remove the entire chocolate chip, we can first remove the current row and col chip, and set its value to 0. We can then remove all of the neighboring squares that are chocolate. Here's the recursion:

2. Base case

With this recursion, we don't need a base case. This is because we are implicitly keeping track of the squares we've visited by setting them to have a value of 0. This means that we never end up visiting the same square twice, and we do not enter into any infinite loops.

3. Code

To code this up, you can combine all of the code that we created.

Time Complexity $O(nm)$. This might be surprising because there are 2 for loops, and then an additional recursion removeChip. But notice that the total number of times removeChip gets called is always $\le O(nm)$ since once it visits a location, it never visits it again. This means we do $O(nm)$ operations for the for loop, and independently another $O(nm)$ for removeChip, which is a total of $O(nm)$.

Space Complexity $O(nm)$ for the Call Stack. The recursion removeChip can get $n m$ calls deep, which means the Call Stack might grow to a height of $O(nm)$.