Area of the largest rectangle formed by lines parallel to X and Y axis from given set of points

Given an array arr[] consisting of N pair of integers representing coordinates of N points, the task is to find the area of the largest rectangle formed by straight lines drawn parallel to X and Y-axis from a given set of points.

Examples:

Input: arr[] = , >
Output: 1
Explanation: The area of the largest rectangle is 1 formed by the coordinates (0, 0), (0, 1), (1, 0), (1, 1).

Input: arr[] = , , , >
Output: 8
Explanation: The area of the largest rectangle possible is 8 ( length = 4 and breadth = 2 ) by the coordinates (-2, 0), (2, 0), (2, 2), (-2, 2).

Approach: The problem can be solved using the sorting technique. Follow the steps below to solve the problem:

1. Store X and Y coordinates in two different arrays, say x[] and y[].
2. Sort the arrays x[] and y[].
3. Find the maximum adjacent difference from both arrays and store in variables X_Max and Y_Max.
4. The maximum rectangle area possible is the product of X_Max and Y_Max.

Below is the implementation of the above approach: