I appeared for phone screening of Google L4. There was a question asked where I am given a grid of size (n-1) * (n) where n is number of columns. The value at each index of matrix could either be 0 or 1.
I am allowed to move top down or bottom right of the matrix. I need to reach the position (n-2, n). We need to return true if number on 1s encounterd on the path is same as number of 0's.

Was able to solve using DFS by exploring all the paths and counting 0 and 1 from source to destination.

**Follow up: **

Now you're allowed to move in any 4-directions(left, right, top, bottom) in the matrix. Return true if number of 1s encounterd is same as number of 0s.

Could not solve the follow up question.