O(N^2) python solution TLE on 2 test cases?
I read the note about stricter C/C++ time limit, so I wrote an N^2 python solution. Why was this rejected?\n\nMinor optimizations won't change the order O(N^2).
I read the note about stricter C/C++ time limit, so I wrote an N^2 python solution. Why was this rejected?\n\nMinor optimizations won't change the order O(N^2).\n\n\n```\nclass Solution(object):\n    def orderOfLargestPlusSign(self, N, mines):\n        """\n        :type N: int\n        :type mines: List[List[int]]\n        :rtype: int\n        """\n        left=[[0]*N for __ in xrange(N)]\n        right=[[0]*N for __ in xrange(N)]\n        up=[[0]*N for __ in xrange(N)]\n        down=[[0]*N for __ in xrange(N)]\n\n        g=[[1]*N for __ in xrange(N)]\n\n        for (r, c) in mines:\n            g[r][c]=0\n\n        for r in xrange(N):\n            last=None\n            for c in xrange(N):\n                if g[r][c]:\n                    last=last or c\n                    left[r][c]=last\n                else:\n                    last=None\n\n            last=None\n            for c in xrange(N-1, -1, -1):\n                if g[r][c]:\n                    last=last or c\n                    right[r][c]=last\n                else:\n                    last=None\n            \n        for c in xrange(N):\n            last=None\n            for r in xrange(N):\n                if g[r][c]:\n                    last=last or c\n                    up[r][c]=last\n                else:\n                    last=None\n\n            last=None\n            for r in xrange(N-1, -1, -1):\n                if g[r][c]:\n                    last=last or c\n                    down[r][c]=last\n                else:\n                    last=None\n\n        mx=0\n        for r in xrange(N):\n            for c in xrange(N):\n                if g[r][c]:\n                    horz=min(right[r][c]-c,c-left[r][c])+1\n                    vert=min(down[r][c]-r,r-up[r][c])+1\n                    val=min(horz, vert)\n                    mx=max(val, mx)\n            \n        return mx\n```
[]