LC: 750. Number Of Corner Rectangles - spiralgo/algorithms GitHub Wiki

750. Number Of Corner Rectangles:

The Essence:

• If there are N objects in an array, adding a new object would create N new subarrays.
• In N different rows above some current row, if there are already two points at some indexes j and k in each of these columns, having also 2 points there in the current row would create N new rectangles.

Details:

The number of rows that so far contain points at i as well as k can be kept using a matrix. The running count is added to the total when a new row also contains both points. The approach described here can also be implemented from a row-first perspective with traversal going from first column to the last.