Techno Blender
Digitally Yours.
0 6

Given an array arr[] of size N, the array represents N / 2 coordinates of a rectangle randomly shuffled with its X and Y coordinates. The task for this problem is to construct N / 2 pairs of (X, Y) coordinates by choosing X and Y from array arr[] in such a way that a rectangle that contains all these points has a minimum area.

Examples:

Input: arr[] = {4, 1, 3, 2, 3, 2, 1, 3}
Output: 1
Explanation: let pairs formed be (1, 3), (1, 3), (2, 3) and (2, 4) then the rectangle that contains these points will have a lower Left coordinate (1, 3) and upper right coordinate (2, 4). Hence area of rectangle = (xUpper – xLower) * (yUpper – yLower) = (2 – 1) * (4 – 3) = 1

Input: arr[] = {5, 8, 5, 5, 7, 5}
Output: 0
Explanation: let pairs formed be (5, 5), (5, 7) and (5, 8) then the rectangle that contains these points will have a lower Left coordinate (5, 5) and upper right coordinate (5, 8). Hence area of rectangle = (xUpper – xLower) * (yUpper – yLower) = (5 – 5) * (8 – 5) = 0

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Time Complexity: O(N!)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea:

Observation: Sort the array arr[] and it will always be better to take X coordinate’s as subarray of size N / 2 from sorted array A[] and Y coordinates as leftover elements.
The answer can be tracked for all subarrays of size N / 2 by using the sliding window technique.

Follow the steps below to solve the problem:

• Sort the array arr[].
• Create a variable ans to store the potential answer.
• Initialize window size from 0 to (N/2) – 1 by declaring low = 1 and high = N/2 – 1.
• Start a while loop and check if low==0 if yes,
• then, update the answer for the first slide
• Otherwise, break when the slide reaches the end high == N-1
• else, update the ans for ith slide and update the low and high pointers.

Below is the implementation of the above approach:

## C++

 `#include ` `using` `namespace` `std;` ` `  `int` `minArea(``int` `A[], ``int` `N)` `{` `    ` `    ``sort(A, A + N);` ` `  `    ` `    ``int` `ans = INT_MAX;` ` `  `    ` `    ` `    ``int` `low = 0, high = N / 2 - 1;` ` `  `    ``while` `(1) {` ` `  `        ``if` `(low == 0) {` ` `  `            ` `            ` `            ``ans = (A[N / 2 - 1] - A)` `                  ``* (A[N - 1] - A[N / 2]);` `        ``}` ` `  `        ` `        ` `        ``else` `if` `(high == N - 1)` `            ``break``;` ` `  `        ``else` `{` ` `  `            ` `            ` `            ``ans = min(ans, (A[high] - A[low])` `                               ``* (A[N - 1] - A));` `        ``}` ` `  `        ` `        ` `        ``low++, high++;` `    ``}` ` `  `    ` `    ``return` `ans;` `}` ` `  `int` `main()` `{` ` `  `    ` `    ``int` `A[] = { 4, 1, 3, 2, 3, 2, 1, 3 };` `    ``int` `N = ``sizeof``(A) / ``sizeof``(A);` ` `  `    ` `    ``cout << minArea(A, N) << endl;` ` `  `    ` `    ``int` `A1[] = { 5, 8, 5, 5, 7, 5 };` `    ``int` `N1 = ``sizeof``(A1) / ``sizeof``(A1);` ` `  `    ` `    ``cout << minArea(A1, N1) << endl;` `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles:

Given an array arr[] of size N, the array represents N / 2 coordinates of a rectangle randomly shuffled with its X and Y coordinates. The task for this problem is to construct N / 2 pairs of (X, Y) coordinates by choosing X and Y from array arr[] in such a way that a rectangle that contains all these points has a minimum area.

Examples:

Input: arr[] = {4, 1, 3, 2, 3, 2, 1, 3}
Output: 1
Explanation: let pairs formed be (1, 3), (1, 3), (2, 3) and (2, 4) then the rectangle that contains these points will have a lower Left coordinate (1, 3) and upper right coordinate (2, 4). Hence area of rectangle = (xUpper – xLower) * (yUpper – yLower) = (2 – 1) * (4 – 3) = 1

Input: arr[] = {5, 8, 5, 5, 7, 5}
Output: 0
Explanation: let pairs formed be (5, 5), (5, 7) and (5, 8) then the rectangle that contains these points will have a lower Left coordinate (5, 5) and upper right coordinate (5, 8). Hence area of rectangle = (xUpper – xLower) * (yUpper – yLower) = (5 – 5) * (8 – 5) = 0

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Time Complexity: O(N!)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea:

Observation: Sort the array arr[] and it will always be better to take X coordinate’s as subarray of size N / 2 from sorted array A[] and Y coordinates as leftover elements.
The answer can be tracked for all subarrays of size N / 2 by using the sliding window technique.

Follow the steps below to solve the problem:

• Sort the array arr[].
• Create a variable ans to store the potential answer.
• Initialize window size from 0 to (N/2) – 1 by declaring low = 1 and high = N/2 – 1.
• Start a while loop and check if low==0 if yes,
• then, update the answer for the first slide
• Otherwise, break when the slide reaches the end high == N-1
• else, update the ans for ith slide and update the low and high pointers.

Below is the implementation of the above approach:

## C++

 `#include ` `using` `namespace` `std;` ` `  `int` `minArea(``int` `A[], ``int` `N)` `{` `    ` `    ``sort(A, A + N);` ` `  `    ` `    ``int` `ans = INT_MAX;` ` `  `    ` `    ` `    ``int` `low = 0, high = N / 2 - 1;` ` `  `    ``while` `(1) {` ` `  `        ``if` `(low == 0) {` ` `  `            ` `            ` `            ``ans = (A[N / 2 - 1] - A)` `                  ``* (A[N - 1] - A[N / 2]);` `        ``}` ` `  `        ` `        ` `        ``else` `if` `(high == N - 1)` `            ``break``;` ` `  `        ``else` `{` ` `  `            ` `            ` `            ``ans = min(ans, (A[high] - A[low])` `                               ``* (A[N - 1] - A));` `        ``}` ` `  `        ` `        ` `        ``low++, high++;` `    ``}` ` `  `    ` `    ``return` `ans;` `}` ` `  `int` `main()` `{` ` `  `    ` `    ``int` `A[] = { 4, 1, 3, 2, 3, 2, 1, 3 };` `    ``int` `N = ``sizeof``(A) / ``sizeof``(A);` ` `  `    ` `    ``cout << minArea(A, N) << endl;` ` `  `    ` `    ``int` `A1[] = { 5, 8, 5, 5, 7, 5 };` `    ``int` `N1 = ``sizeof``(A1) / ``sizeof``(A1);` ` `  `    ` `    ``cout << minArea(A1, N1) << endl;` `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles: