We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Number of Ways to Place People II

Difficulty: Hard

Problem Description

You are given a 2D array points of size n x 2 representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. You need to place n people, including Alice and Bob, at these points such that there is exactly one person at every point. Alice will build a rectangular fence with her position as the upper left corner and Bob's position as the lower right corner. If any person other than Alice and Bob is either inside or on the fence, Alice will be sad. Return the number of pairs of points where you can place Alice and Bob, such that Alice does not become sad on building the fence.

Key Insights

  • Alice's position must have a smaller x-coordinate and y-coordinate than Bob's position.
  • Points must be sorted based on their coordinates to facilitate easier pair evaluation.
  • We need to check for each pair of points if any other point lies within or on the fence defined by Alice and Bob.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

The solution involves iterating through each possible pair of points to determine valid placements for Alice and Bob. The approach can be broken down into the following steps:

  1. Sort the Points: First, sort the points based on their x-coordinates, and in case of a tie, by their y-coordinates.
  2. Enumerate Pairs: For each pair of points (A, B), check if A can be the upper-left corner and B the lower-right corner.
  3. Check Validity: For points in between A and B, ensure that no point lies within or on the fence defined by the coordinates of A and B.
  4. Count Valid Pairs: If a pair is valid, increase the count.

By efficiently checking the conditions for each pair, we can obtain the final count of valid placements for Alice and Bob.

Code Solutions

def countValidPairs(points):
    n = len(points)
    points.sort()  # Sort by x, then by y
    count = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            A = points[i]
            B = points[j]
            valid = True
            
            # Check if any other point is within or on the fence
            for k in range(n):
                if k != i and k != j:
                    P = points[k]
                    if A[0] <= P[0] <= B[0] and A[1] <= P[1] <= B[1]:
                        valid = False
                        break
            
            if valid:
                count += 1
                
    return count
← Back to All Questions