different take - sorting mines to eliminate searches beats 100% Java by a wide margin
Admittedly this version takes more storage than the solutions that cleverly use a single 2D array to store the minimum results of 4 simultaneous scans for the l
Admittedly this version takes more storage than the solutions that cleverly use a single 2D array to store the minimum results of 4 simultaneous scans for the longest legs in each of 4 directions, but it represents a more direct way to compute the "longest legs" than a scan.\n\nMy concept was to store the longest horizontal and vertical cross-sections rather than separate up/down/left/right legs.  This is done by first creating sorted lists of mines on each row and column.  Then we can visit every pair of mines and fill the space between them concentrically from the mines towards the center between them with increasing values.  This involves 3 steps:\n\n**Step 1 - sorting mines**\nI create 2 arrays of PriorityQueues to sort the mines. This is probably overkill for most mine setups as it will be fairly sparse, but it simplified the code.\n\n**Step 2 - filling in h/v crossbar sizes**\nIt would be more space efficient to do this in the same grid for each direction, but that would mean either initializing both grids to "N" and then doing a "min()" operation as we fill the grids first by row and then by col, or letting the first pass fill them using assignment and then the second pass needing to do the "min()" operation on every fill.  It simplified the code somewhat to simply fill 2 separate grids from the 2 separate lists of sorted mines and then do a final pass finding the minimum intersections between the two.  Note that the row grid is oriented as you would expect ```grid[r][c]```, but the columns grid is transposed, as in ```grid[c][r]```. This allows both grids to be constructed by the same shared code for simplicity.\n\nThe filling operations are done by reading out the sorted list of mines on every row (or column) and then filling concentrically between each pair of mines.  The first mine is also filled from the left/top edge and the last mine also fills to the right/bottom edge using the same concentric fill.\n\nA concentric fill is starting at both ends and fillling a 1 first, then moving both ends towards each other and filling with higher and higher numbers until the ends meet in the middle. In this case, the endpoints are specified as exclusive indices so the "bumping the ends towards each other" happens before the increasing distance is stored.\n\n**Step 3 - min/maxing the cross sizes**\nThe last step simply involves iterating over the two grids, comparing the longest horizontal and vertical crossbars possible at any given position and returning the largest such cross.\n\n**Complexity**\nThis has a very similar O(N^2) complexity to most solutions with the only distinction being that inserting the mines into the PriorityQueues could potentially increase the work for very unfortunately constructed lists of mines.  There is one pass over the mines to insert them into the 2 queue lists.  Then there are N^2 passes over each of the ```byrows``` and ```bycols``` grids, and finally there is one last N^2 pass over the pair of grids looking for a min/max.\n\nThe total running time is much shorter than the shortest recorded Java solutions, though, and it\'s not clear why this is in general, but I can speculate how it might be this way due to the way the test cases might be constructed.\n\nFirst, the insertion of the mine coordinates into the PriorityQueues could perform poorly if there are a lot of mines and/or the mines come in out of order, but I\'m guessing the test cases are focused more on the scan for cross pieces than on the processing of the mines so there are probably a lot of examples with a large ```N``` value, but a small number or a sparse distribution of mines.\n\nSecond, many of the solutions scan in 4 directions for the shortest arm of the cross.  That means there are 4 N^2 scans that happen in the end, but my solution only uses 3 of them (1 for constructing ```byrows```, 1 for constructing ```bycols```, and 1 for iterating and min/maxing). Also, many of those will do min() operations at each grid location because they are accumulating the minimum leg for each of 4 directions.  That technique results in 4xN^2 calls to a ```min()``` function. My solution avoids nearly all of those mins by directly constructing the distance to the nearest mine in both left/right at the same time and both up/down at the same time with no need to call a ```min()``` function.  It does use a single call to ```min()``` per grid element in the final scan, though.  All in all, this solution reduces 4N^2 scans with 4N^2 calls to ```min()``` down to 3N^2 scans and N^2 calls to ```min()```.\n\n**Possible optimizations**\nOne optimization could be to use the same grid for the lengths of the longest horizontal and vertical crossbars.  This could be done by either preinitializing the grid to all values of N and then to use ```min()``` operations as it is filled - increasing the compute time by requiring another pass of ```min()``` calls, but removing one of the grid storage spaces.\n\nA similar optimization would reduce the amount of shared code by having the first pass that fills the grid with the horizontal crossbar lengths do a direct assignment rather than a ```min()``` operation and then having a very similar piece of code handle the second pass for the vertical crossbar lengths, but do a ```min()``` operation as it fills in the values.  This should not increase the time complexity because we eventually do that ```min()``` operation in the final pass anyway, but it would mean a bit of code duplication.\n\n```\n    void insert(PriorityQueue<Integer> vals[], int r, int c) {\n        PriorityQueue<Integer> row = vals[r];\n        if (row == null) {\n            vals[r] = row = new PriorityQueue<>();\n        }\n        row.add(c);\n    }\n    void fill(int row[], int c0, int c1) {\n        int i = 0;\n        while (++c0 <= --c1) {\n            row[c0] = row[c1] = ++i;\n        }\n    }\n    int[][] toGrid(PriorityQueue<Integer> list[]) {\n        int N = list.length;\n        int grid[][] = new int[N][N];\n        for (int r = 0; r < N; r++) {\n            int prev = -1;\n            if (list[r] != null) {\n                for (int c : list[r]) {\n                    fill(grid[r], prev, c);\n                    prev = c;\n                }\n            }\n            fill(grid[r], prev, N);\n        }\n        return grid;\n    }\n    public int orderOfLargestPlusSign(int N, int[][] mines) {\n        PriorityQueue<Integer> rows[] = new PriorityQueue[N];\n        PriorityQueue<Integer> cols[] = new PriorityQueue[N];\n        for (int mine[] : mines) {\n            insert(rows, mine[0], mine[1]);\n            insert(cols, mine[1], mine[0]);\n        }\n        int byrows[][] = toGrid(rows);\n        int bycols[][] = toGrid(cols);\n        int biggest = 0;\n        for (int r = 0; r < N; r++) {\n            for (int c = 0; c < N; c++) {\n                int order = Math.min(byrows[r][c], bycols[c][r]);\n                if (biggest < order) biggest = order;\n            }\n        }\n        return biggest;\n    }\n```
[]