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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Number of Ways to Place People II

Number: 3277

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given n distinct points on a 2D-plane, assign one person to each point. Among these people are Alice and Bob. Alice will try to build a rectangular fence with her position as the upper left corner and Bob’s position as the lower right corner. The fence (including its boundary) must not contain any of the other people. Return the number of valid pairs of points (Alice, Bob) where the placement meets the following conditions:

  • Alice’s x-coordinate is less than or equal to Bob’s x-coordinate.
  • Alice’s y-coordinate is greater than or equal to Bob’s y-coordinate.
  • No other point lies inside or on the boundary of the rectangle determined by Alice’s and Bob’s positions.

Key Insights

  • For a candidate pair (A, B), the rectangle is defined with A’s position as the top-left corner and B’s as the bottom-right.
  • The valid configuration requires A.x <= B.x and A.y >= B.y.
  • Any other point inside or on the perimeter of the rectangle invalidates the placement.
  • By “compressing” coordinates (since there are at most 1000 points), we can build a grid where each cell indicates whether a point is present.
  • With a 2D prefix sum (cumulative frequency grid) on the compressed grid, we can efficiently query the number of points inside any axis-aligned rectangle.
  • Finally, iterate through all valid pairs (A, B) (O(n^2)) and use the prefix sum to check that exactly two points are present (A and B themselves) within the defined rectangle.

Space and Time Complexity

Time Complexity: O(n^2 + G) where n is the number of points and G is the number of cells (at most O(n^2)) to compute the prefix sum grid. In worst-case, it is approximately O(n^2).
Space Complexity: O(n^2) for the compressed grid and its prefix sum.

Solution

We first compress the x and y coordinates to create a small grid (since the points are sparse but coordinates can be very large). Then we build a 2D grid with 1’s marking where points exist. We compute a 2D prefix sum over this grid so that any axis-aligned subrectangle can be queried in constant time. For every pair of points that satisfy the ordering conditions for being top‐left and bottom‐right, we query the count of points in the corresponding rectangle. If the count equals 2 (only the pair of points itself), we count this pair as valid.
The solution uses coordinate compression, a 2D prefix sum data structure, and a brute-force check over all candidate pairs with the prefix sum query as the “trick” to bring down the query time.

Code Solutions

# Python solution with detailed line-by-line comments

def numWays(points):
    # Extract all x's and y's for coordinate compression
    xs = sorted(set(x for x, y in points))
    ys = sorted(set(y for x, y in points))
    
    # Create mapping dictionaries for x and y
    compX = {x: idx for idx, x in enumerate(xs)}
    compY = {y: idx for idx, y in enumerate(ys)}
    
    # Dimensions for compressed grid
    maxX, maxY = len(xs), len(ys)
    
    # Build grid and mark points
    grid = [[0] * (maxY) for _ in range(maxX)]
    for x, y in points:
        grid[compX[x]][compY[y]] = 1
        
    # Build 2D prefix sum array.
    prefix = [[0] * (maxY + 1) for _ in range(maxX + 1)]
    for i in range(1, maxX + 1):
        for j in range(1, maxY + 1):
            # Note: grid indices are shifted by 1 in prefix array
            prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
    
    # Function to perform range sum query on prefix sum array for rectangle 
    # spanning [x1, x2] in x and [y1, y2] in y (both inclusive) in grid indices.
    def query(x1, y1, x2, y2):
        # Shift indices by 1 for prefix access
        return prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]
    
    count = 0
    n = len(points)
    # For each pair of points, check if they satisfy the ordering condition.
    for i in range(n):
        x1, y1 = points[i][0], points[i][1]
        for j in range(n):
            # Skip if same point
            if i == j:
                continue
            x2, y2 = points[j][0], points[j][1]
            # Ensure point i can serve as Alice (upper left) and point j as Bob (lower right)
            if x1 <= x2 and y1 >= y2:
                # Compressed indices
                cx1, cy1 = compX[x1], compY[y1]
                cx2, cy2 = compX[x2], compY[y2]
                # In compressed grid the rectangle spans x from cx1 to cx2 and y from cy2 to cy1
                # Ensure cx1 <= cx2 and cy2 <= cy1 (this holds because of the ordering of points).
                if cx1 <= cx2 and cy2 <= cy1:
                    # Get the number of points in the rectangle defined by (cx1, cy2) and (cx2, cy1)
                    total = query(cx1, cy2, cx2, cy1)
                    # Only the two endpoints should be present.
                    if total == 2:
                        count += 1
    return count

# Example test
print(numWays([[6,2],[4,4],[2,6]]))  # Expected output: 2
← Back to All Questions