LeetCode 3710 - Maximum Partition Factor
The problem asks us to split a set of n points in a 2D Cartesian plane into exactly two non-empty groups, such that the minimum Manhattan distance among all pairs of points within each group (the partition factor) is maximized.
Difficulty: 🔴 Hard
Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory
Solution
Problem Understanding
The problem asks us to split a set of n points in a 2D Cartesian plane into exactly two non-empty groups, such that the minimum Manhattan distance among all pairs of points within each group (the partition factor) is maximized. The Manhattan distance between points [xi, yi] and [xj, yj] is defined as |xi - xj| + |yi - yj|.
The input is a list of points, where each point is a pair of integers. The output is a single integer representing the maximum possible partition factor achievable with any valid split.
Key constraints are that n ranges from 2 to 500 and point coordinates can be very large negative or positive integers. Because n can be up to 500, a brute-force approach that considers all possible splits (which would be 2^n combinations) is infeasible.
Important edge cases include n = 2, where both groups must be singletons, so the partition factor is defined as 0, and cases where all points are collinear or have overlapping coordinates, which could lead to minimum Manhattan distances of 0 within groups.
Approaches
The brute-force approach would generate all possible partitions of the points into two non-empty groups. For each split, we would compute all intra-group Manhattan distances and take the minimum within each group. Finally, the split with the maximum minimum distance would be returned. While correct, this approach has exponential time complexity, O(2^n * n^2), and is impractical for n = 500.
The optimal approach relies on graph theory and binary search. We can treat the problem as a graph where nodes are points and edges exist between points whose Manhattan distance is less than a candidate distance d. The key insight is that if a candidate partition factor is achievable, the graph must be bipartite, meaning we can assign points to two groups such that no edge exists within a group. Using binary search on possible distances and a bipartite check via DFS or BFS allows us to find the maximum partition factor efficiently.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n * n^2) | O(n^2) | Generate all splits and compute intra-group distances |
| Optimal | O(n^2 * log D) | O(n^2) | Binary search on candidate distances with bipartite graph check; D is the range of Manhattan distances |
Algorithm Walkthrough
- Compute all pairwise Manhattan distances between the points and store them in a matrix. This helps quickly check if a candidate distance is achievable.
- Initialize binary search variables. Set
low = 0andhigh = max possible distance. The maximum possible Manhattan distance between points can be computed usingmax(|xi - xj| + |yi - yj|)over all pairs. - Binary search loop: while
low < high, setmid = (low + high + 1) // 2as the candidate partition factor. - Build a graph for the candidate distance: create edges between points whose Manhattan distance is less than the candidate distance.
- Check if the graph is bipartite using BFS or DFS. A bipartite graph allows assigning nodes to two groups without intra-group edges. If the graph is bipartite, the candidate distance is achievable.
- Adjust binary search bounds: if bipartite, set
low = mid; otherwise, sethigh = mid - 1. - Return
lowafter the binary search ends. This represents the maximum partition factor.
Why it works: The bipartite check ensures that no two points in the same group have a distance smaller than the candidate, which matches the definition of the partition factor. Binary search efficiently converges to the largest achievable minimum distance.
Python Solution
from typing import List
from collections import deque
class Solution:
def maxPartitionFactor(self, points: List[List[int]]) -> int:
n = len(points)
# Function to compute Manhattan distance
def manhattan(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
# Compute maximum possible Manhattan distance
max_dist = 0
for i in range(n):
for j in range(i+1, n):
max_dist = max(max_dist, manhattan(points[i], points[j]))
# Check if candidate distance can be a partition factor using bipartite check
def can_partition(candidate):
graph = [[] for _ in range(n)]
for i in range(n):
for j in range(i+1, n):
if manhattan(points[i], points[j]) < candidate:
graph[i].append(j)
graph[j].append(i)
color = [0] * n
for i in range(n):
if color[i] == 0:
queue = deque([i])
color[i] = 1
while queue:
node = queue.popleft()
for nei in graph[node]:
if color[nei] == 0:
color[nei] = -color[node]
queue.append(nei)
elif color[nei] == color[node]:
return False
return True
# Binary search on possible partition factors
low, high = 0, max_dist
while low < high:
mid = (low + high + 1) // 2
if can_partition(mid):
low = mid
else:
high = mid - 1
return low
Explanation: The solution first computes all Manhattan distances to determine the search range. It uses a binary search combined with a bipartite check to efficiently find the maximum partition factor. BFS ensures that every connected component is bipartite and can be separated into two groups.
Go Solution
package main
func maxPartitionFactor(points [][]int) int {
n := len(points)
manhattan := func(i, j int) int {
xi, yi := points[i][0], points[i][1]
xj, yj := points[j][0], points[j][1]
dx := xi - xj
if dx < 0 { dx = -dx }
dy := yi - yj
if dy < 0 { dy = -dy }
return dx + dy
}
maxDist := 0
for i := 0; i < n; i++ {
for j := i+1; j < n; j++ {
d := manhattan(i, j)
if d > maxDist { maxDist = d }
}
}
canPartition := func(candidate int) bool {
graph := make([][]int, n)
for i := 0; i < n; i++ {
for j := i+1; j < n; j++ {
if manhattan(i, j) < candidate {
graph[i] = append(graph[i], j)
graph[j] = append(graph[j], i)
}
}
}
color := make([]int, n)
for i := 0; i < n; i++ {
if color[i] == 0 {
queue := []int{i}
color[i] = 1
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, nei := range graph[node] {
if color[nei] == 0 {
color[nei] = -color[node]
queue = append(queue, nei)
} else if color[nei] == color[node] {
return false
}
}
}
}
}
return true
}
low, high := 0, maxDist
for low < high {
mid := (low + high + 1) / 2
if canPartition(mid) {
low = mid
} else {
high = mid - 1
}
}
return low
}
Go-specific notes: Slices are used to represent the adjacency list. Integer overflow is not an issue since coordinates are within 10^8. BFS is implemented using a slice as a queue.
Worked Examples
Example 1: points = [[0,0],[0,2],[2,0],[2,2]]
| Step | mid | can_partition(mid)? | low | high |
|---|---|---|---|---|
| 1 | 4 | True | 4 | 4 |
Bipartite check succeeds; maximum partition factor = 4.
Example 2: points = [[0,0],[0,1],[10,0]]
| Step | mid | can_partition(mid)? | low | high |
|---|---|---|---|---|
| 1 | 11 | True | 11 | 11 |
Bipartite check succeeds; maximum partition factor = 11.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2 * log D) | There are O(log D) binary search steps, each building a graph in O(n^2) time. D is the range of |