Find the Number of Ways to Place People in Java
Given a 2D array of points of size n x 2, where points[i] = [xi, yi], and the array points represent the integer coordinates of some points on a 2D plane. There are n people, including A and B, are placed at points with one person at every point. Here, the person A wants to be alone with person B, so A builds a rectangular boundary where A’s position as upper left corner and B’s position as the lower right corner. The problem is if any other person is inside the boundary or placed on the boundary, A will be disappointed. The objective is to find the number of pairs of points where A and B can be placed such that A should not be disappointed while constructing the boundary.
Note: A can only construct a boundary with A’s position in the upper left corner and B's position in the lower right corner. Let’s see a few examples to understand it
Example 1:
![Find the Number of Ways to Place People in Java/>
<!-- /wp:html -->
<!-- wp:paragraph -->
<p><strong>Input: </strong>points = [[1, 1], [3, 3], [4, 4]]</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Output:</strong> 0</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Explanation:</strong> We cannot place person A and B such that A is at upper left corner and B at lower right corner to construct a boundary. Therefore, we return 0.</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Example 2: </strong><strong></strong><strong></strong></p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<img data-cke-saved-src=](https://static.tutorialandexample.com/java/find-the-number-of-ways-to-place-people-in-java1.png)
- We can place A at (3,3) and B at (5,2).
- We can place A at (2,5) and B at (3,3).
We cannot place A at (2, 5) and B at (5, 2) because the person at (3, 3) will be inside the boundary. Hence, the output is 2 possible ways.
Example 3:
![Find the Number of Ways to Place People in Java/>
<!-- /wp:html -->
<!-- wp:paragraph -->
<p><strong>Input:</strong> points = [[4, 1], [1, 4], [1, 1]]</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Output</strong>: 2</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Explanation:</strong> we can place person A and B in two ways such that A is not disappointed:</p>
<!-- /wp:paragraph -->
<!-- wp:list {](https://static.tutorialandexample.com/java/find-the-number-of-ways-to-place-people-in-java3.png)
We cannot place A at (1, 4) and B at (4, 1) because the person at (1, 1) will be inside the boundary. Hence, the output is 2 possible ways.
Approach: Using Geometry
Step 1: Sort the array of points in ascending order according to their x-coordinate.
Step 2: If the x-coordinates are equal, sort in descending order using the y-coordinates.
Step 3: Create a variable named ansr to store the count of valid pairs used to place A and B.
Step 4: Iterate through each pair of points named pointA and pointB in the sorted array.
Step 4.1: Determine if A named pointA is above and to the left of B named pointB.
Step 4.2: If the condition is met, verify that there are no other points inside the rectangle boundary created by person named A and person named B positions.
Step 4.3: If all of the conditions are satisfied, increase the count of variable ansr.
Step 5: Finally, return the count value of ansr, which contains the number of valid pair points.
FileName: NoOfWaysToPlaceThePeople.java
// importing Arrays class import java.util.Arrays; public class NoOfWaysToPlaceThePeople { // method to find the count of valid pair points public int numberOfPossiblePairs(int[][] points) { int n = points.length; // sorting the input array Arrays.sort(points, (a, b) -> { if (a[0] != b[0]) { return a[0] - b[0];// sorting by x coordinate } return b[1] - a[1]; // sorting by y coordinate }); int ansr = 0; // iterating each point for (int i = 0; i < n; i++) { int[] pointA = points[i]; for (int j = i + 1; j < n; j++) { int[] pointB = points[j]; if (pointA[0] > pointB[0] || pointA[1] < pointB[1]) { continue; } // verify the intersection of other points between A and B Boolean valid = true; for (int k = i + 1; k < j; k++) { int[] pointC = points[k]; if (pointA[0] <= pointC[0] && pointC[0] <= pointB[0] && pointA[1] >= pointC[1] && pointC[1] >= pointB[1]) { valid = false; break; } } if (valid) { ansr++; } } } return ansr; } // main method public static void main(String[] args) { // provide input pair values int[][] pairPoints = {{3, 1}, {1, 3}, {1, 1}}; NoOfWaysToPlaceThePeople n = new NoOfWaysToPlaceThePeople(); int resl = n.numberOfPossiblePairs(pairPoints); System.out.println("Number of Ways to place A and B are: " + resl); } }
Output:
Number of ways to place A and B are: 2
Complexity analysis: The program takes O(n log n) time to sort the array of points. And O(n ^ 2) time to iterate through each pair of points using nested loops. Therefore, the overall time complexity is O(n log n), where n is number of points. The space complexity is O(n) because sorting and storing of individual points in arrays and other variables takes O(1) space.
- We can place A at (1, 1) and B at (4, 1).
- We can place A at (1, 4) and B at (1, 1).