Short BF solution


  • 2
    K

    The idea is that on each diagonal we have that row + col = constant. So we just iterate over all the possible diagonal sums and check for possible combination of rows and cols that sum to the current diagonal value

    class Solution {
    public:
        vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
            if(matrix.size() == 0) return {};
            vector<int> ele;
            int n = matrix.size();
            int m = matrix[0].size();
            int maxSum = n + m - 2;
    
            for (int sum = 0; sum <= maxSum; ++sum) {
                int delta = 1 - 2*(sum%2 == 0);
                int iStart = (n-1) * (sum%2 == 0);
                int jStart = (m-1) * (sum%2 == 0);
                
                for (int i = iStart; i >= 0 && i < n; i += delta) {
                    for (int j = jStart; j>= 0 && j < m; j += delta) {
                        if (i + j - sum == 0) {
                            ele.push_back(matrix[i][j]);
                        }
                    }
                }
            }
            return ele;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.