[Leetcode 542] Poorly Worded and Misleading Question
Anon
134
C++

Hello,

This leetcode question is very poorly worded. I believe my solution below is correct since, after observing the test case it failed on, I noticed that the expected results of the testcase are totally off. Either not enough detail in the question was given, or this example is totally contrived.

To see this for yourself, drawn the following grid by hand.

[[0,0,1,0,1,1,1,0,1,1],[1,1,1,1,0,1,1,1,1,1],[1,1,1,1,1,0,0,0,1,1],[1,0,1,0,1,1,1,0,1,1],[0,0,1,1,1,0,1,1,1,1],[1,0,1,1,1,1,1,1,1,1],[1,1,1,1,0,1,0,1,0,1],[0,1,0,0,0,1,0,0,1,1],[1,1,1,0,1,1,0,1,0,1],[1,0,1,1,1,0,1,1,1,0]]

See the expected answer, in particular, the last number in index 1 (number 3).

[[0,0,1,0,1,2,1,0,1,2],[1,1,2,1,0,1,1,1,2,3],[2,1,2,1,1,0,0,0,1,2],[1,0,1,0,1,1,1,0,1,2],[0,0,1,1,1,0,1,1,2,3],[1,0,1,2,1,1,1,2,1,2],[1,1,1,1,0,1,0,1,0,1],[0,1,0,0,0,1,0,0,1,2],[1,1,1,0,1,1,0,1,0,1],[1,0,1,1,1,0,1,2,1,0]]

The closest zero is NOT three away at that position, not even close. The closest zero is five digits away in any left, right, up, or down direction.

Below is my solution.

class Solution {
private:
    
    enum class direction {UP, DOWN, LEFT, RIGHT};
    
    int distanceAway(int x, int y, direction d, const vector<vector<int>>& matrix) {

        int matrixHeight = matrix.size();
        int matrixWidth = matrix[0].size();
        if (y >= matrixWidth || y < 0) return matrixWidth;
        if (x < 0 || x >= matrixHeight) return matrixHeight;

        if (matrix[x][y] == 0) return 1;

        switch (d) {
            case direction::RIGHT :
                return 1 + distanceAway(x, y + 1, direction::RIGHT, matrix);
                break;
            case direction::UP :
                return 1 + distanceAway(x + 1, y, direction::UP, matrix);
                break;
            case direction::LEFT : 
                return 1 + distanceAway(x, y - 1, direction::LEFT, matrix);
                break;
            case direction::DOWN : 
                return 1 + distanceAway(x - 1, y, direction::DOWN, matrix);
                break;
        }
        
        return 0;
    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int matrixHeight = matrix.size();
        int matrixWidth = matrix[0].size();
        for (int x{}; x < matrixHeight; x++) {
            for (int y{}; y < matrixWidth; y++) {
                if (matrix[x][y] == 1) {
                    matrix[x][y] = min({distanceAway(x, y + 1, direction::RIGHT, matrix),
                                        distanceAway(x + 1, y, direction::UP, matrix),
                                        distanceAway(x, y - 1, direction::LEFT, matrix),
                                        distanceAway(x - 1, y, direction::DOWN, matrix)});
                }
            }
        }
        return matrix;
    }
};
Comments (1)