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:

m = len(matrix)
n = len(matrix[0])

numChips = 0
for row in range(m):
    for col in range(n):
        if matrix[row][col] == 1:
            numChips += 1
            removeChip(row, col) # set the entire chip to 0 or "dough"
return numChips

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.

removeChip(row, col)

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:

removeChip(row, col) = {
    matrix[row][col] = 0 # set the current value to 0

    # loop through the neighboring squares
    for r,c in [(row+1,col), (row-1, col), (row, col+1), (row, col-1)]:

        if ( # if the neighbor is in bounds, and has a value of 1
            0 <= r < m and 0 <= c < n
            and matrix[r][c] == 1
        ):
            removeChip(r,c) # remove it
}

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.

def numChocolateChips(matrix):
    m = len(matrix)
    n = len(matrix[0])
    
    def removeChip(row, col):
        matrix[row][col] = 0
        # turn the chip to 0s
        for r,c in [(row+1,col), (row-1, col), (row, col+1), (row, col-1)]:
            if 0<=r<m and 0<=c<n and matrix[r][c] == 1:
                removeChip(r,c)

    # iterate through every square
    numChips = 0
    for row in range(m):
        for col in range(n):
            if matrix[row][col] == 1:
                numChips += 1
                removeChip(row,col)

    return numChips

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)$.