4 solutions & best: O(m*n) time and O(1) extra space
\nclass Solution {\npublic:\n    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {\n        // return bruteForceSolution(row
```\nclass Solution {\npublic:\n    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {\n        // return bruteForceSolution(rows, cols, rCenter, cCenter);\n        // return usingOrderedMap(rows, cols, rCenter, cCenter);\n        // return sortResultDirectly(rows, cols, rCenter, cCenter);\n        return distanceOrderConcentricCircles(rows, cols, rCenter, cCenter);\n    }\nprivate:\n    //O(m*n log(m*n)) time, O(m*n) extra space\n    vector<vector<int>> bruteForceSolution(int rows, int cols, int rCenter, int cCenter) {\n        vector<vector<int>> result(rows*cols, vector<int>(2)); // array of coordinates\n        vector<vector<int>> arr(rows*cols, vector<int>(3)); // array of (dist, i, j)\n        \n        //O(rows*cols)\n        for(int i = 0; i < rows; ++i) {\n            for(int j = 0; j < cols; ++j) {\n                int d = abs(i - rCenter) + abs(j - cCenter);\n                int k = i*cols + j;\n                arr[k][0] = d;\n                arr[k][1] = i;\n                arr[k][2] = j;\n            }\n        }\n        \n        //O(rows*cols + log(rows*cols))\n        sort(arr.begin(), arr.end()); //sort by distance\n        \n        //O(rows*cols)\n        for(int k = 0; k < arr.size(); ++k) {\n            result[k][0] = arr[k][1]; //row index\n            result[k][1] = arr[k][2]; //column index;\n        }\n        return result;\n    }\n    //O(m*n log(m*n)) time, O(m*n) extra space\n    vector<vector<int>> usingOrderedMap(int rows, int cols, int rCenter, int cCenter) {\n        multimap<int, vector<int>> a;\n        for(int i = 0; i < rows; ++i) {\n            for(int j = 0; j < cols; ++j) {\n                int d = abs(i - rCenter) + abs(j - cCenter);\n                a.insert({d, {i,j}}); // O(log (rows*cols)) bBST -> sorted linkedlist\n            }\n        }\n        \n        vector<vector<int>> res; // [i,j]\n        for(auto item : a) {\n            res.push_back(item.second);\n        }\n        return res;\n    }\n    //O(m*n log(m*n)) time, O(1) extra space\n    vector<vector<int>> sortResultDirectly(int rows, int cols, int rCenter, int cCenter) {\n        vector<vector<int>> result(rows*cols, vector<int>(2)); //array of coordinates(i,j)\n        \n        //O(rows*cols)\n        for(int i = 0; i < rows; ++i) {\n            for(int j = 0; j < cols; ++j) {\n                int k = i*cols + j;\n                result[k][0] = i;\n                result[k][1] = j;\n            }\n        }\n        \n        //O(rows*cols + lof(rows*cols))\n        sort(result.begin(), result.end(), //lambda function\n             //cell1 and cell2 are parameters and rCenter and cCenter we have to mention even tho they are global variables since lambda funcion is anonymous only complier can see them\n            [rCenter, cCenter]  (vector<int>& cell1, vector<int>& cell2) {\n                int d1 = abs(cell1[0] - rCenter) + abs(cell1[1] - cCenter);\n                int d2 = abs(cell2[0] - rCenter) + abs(cell2[1] - cCenter);\n                return d1 < d2;\n            } \n        );\n        return result;\n    }\n    // O(m*n) time O(1) extra space\n    vector<vector<int>> distanceOrderConcentricCircles(int rows, int cols, int rCenter, int cCenter) {\n        vector<int> cell {rCenter, cCenter};\n        vector<vector<int>> res;\n        res.push_back(cell);\n        \n        int count = 1;\n        int d = 0;\n        while(count < rows * cols) {\n            ++d;\n            int roffset = 0, coffset = d;\n            while(coffset > 0) {\n                cell[0] = rCenter + roffset;\n                cell[1] = cCenter + coffset;\n                if(cell[0] >= 0 && cell[0] < rows && cell[1] >=0 && cell[1] < cols) {\n                    res.push_back(cell);\n                    ++count;\n                }\n                --roffset;\n                --coffset;\n            }\n            while(coffset > -d) {\n                cell[0] = rCenter + roffset;\n                cell[1] = cCenter + coffset;\n                if(cell[0] >= 0 && cell[0] < rows && cell[1] >=0 && cell[1] < cols) {\n                    res.push_back(cell);\n                    ++count;\n                }\n                ++roffset;\n                --coffset;\n            }\n            while(coffset < 0) {\n                cell[0] = rCenter + roffset;\n                cell[1] = cCenter + coffset;\n                if(cell[0] >= 0 && cell[0] < rows && cell[1] >=0 && cell[1] < cols) {\n                    res.push_back(cell);\n                    ++count;\n                }\n                ++roffset;\n                ++coffset;\n            }\n            while(coffset < d) {\n                cell[0] = rCenter + roffset;\n                cell[1] = cCenter + coffset;\n                if(cell[0] >= 0 && cell[0] < rows && cell[1] >=0 && cell[1] < cols) {\n                    res.push_back(cell);\n                    ++count;\n                }\n                --roffset;\n                ++coffset;\n            }\n        }\n        return res;\n    }\n\n};\n```
[]