C++ Pure math solution, O(1) time complexity, compute index directly from coordinates


  • 0
    A

    For any given random coordinates, time complexity is always O(1).
    One pair of coordinates [i, j] outputs one index m.
    No iteration from starting point is needed at all, no matter how gigantic the matrix is.

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> v(n, vector<int>(n));
            for (uint i = 0; i < n; i++) {
                for (uint k, m, j = 0; j < n; j++) {
                    if (i <= j) {
                        k = min(i, n - j - 1);
                        m = 4 * k * (n - k) - 2 * k + i + j + 1; 
                    } else {
                        k = min(j, n - i - 1) + 1;
                        m = 4 * k * (n - k) + 2 * k - i - j - 1;
                    }
                    v[i][j] = m;
                }
            }
            return v;
        }
    };
    

  • 0
    T

    it's not O(1). it's still O(n*n)


  • 0
    A

    @tsipporah5945 What I was talking about is what if the question asked you to return only 1 index of [i,j] given an matrix n x n, say i = 500, j = 800, n = 10000.


Log in to reply
 

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