You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the ith point on the Cartesian plane.
The Manhattan distance between two points points[i] = [xi, yi] and points[j] = [xj, yj] is |xi - xj| + |yi - yj|.
Split the n points into exactly two non-empty groups. The partition factor of a split is the minimum Manhattan distance among all unordered pairs of points that lie in the same group.
Return the maximum possible partition factor over all valid splits.
Note: A group of size 1 contributes no intra-group pairs. When n = 2 (both groups size 1), there are no intra-group pairs, so define the partition factor as 0.
Example 1:
Input: points = [[0,0],[0,2],[2,0],[2,2]]
Output: 4
Explanation:
We split the points into two groups: {[0, 0], [2, 2]} and {[0, 2], [2, 0]}.
In the first group, the only pair has Manhattan distance |0 - 2| + |0 - 2| = 4.
In the second group, the only pair also has Manhattan distance |0 - 2| + |2 - 0| = 4.
The partition factor of this split is min(4, 4) = 4, which is maximal.
Example 2:
Input: points = [[0,0],[0,1],[10,0]]
Output: 11
Explanation:
We split the points into two groups: {[0, 1], [10, 0]} and {[0, 0]}.
In the first group, the only pair has Manhattan distance |0 - 10| + |1 - 0| = 11.
The second group is a singleton, so it contributes no pairs.
The partition factor of this split is 11, which is maximal.
Constraints:
2 <= points.length <= 500points[i] = [xi, yi]-108 <= xi, yi <= 108Problem Overview: You are given an array and must determine the largest factor k such that the array can be partitioned according to constraints derived from that factor. The core task is verifying whether elements can be grouped or connected when a candidate factor is applied, then maximizing that factor.
Approach 1: Brute Force Factor Testing with Graph Traversal (O(n^2 log V) time, O(n) space)
Start by enumerating all possible candidate factors from the smallest value up to the maximum feasible value in the array. For each factor k, build relationships between elements that satisfy the partition condition (for example, divisibility or compatibility based on the factor). Represent these relationships as a graph and run a traversal using Depth‑First Search or Breadth‑First Search to check whether valid partitions exist. This approach works but repeatedly scanning the array and rebuilding connectivity makes it expensive for large inputs.
Approach 2: Binary Search on Factor + Connectivity Check (O(n log V) time, O(n) space)
The key observation is monotonicity: if a factor k allows a valid partition, then smaller factors usually remain feasible. That means you can binary search the answer instead of testing every value. Use binary search on the factor range and validate each candidate by constructing connections between compatible elements. During validation, track connectivity using either graph traversal or a disjoint set structure. This reduces the number of expensive validation passes from linear to logarithmic.
Approach 3: Binary Search + Union-Find Optimization (O(n log V) time, O(n) space)
Instead of running repeated DFS/BFS traversals, maintain connectivity using a Union-Find (Disjoint Set Union) structure. For a candidate factor k, iterate through the array and union indices that satisfy the factor constraint. Path compression and union-by-rank make each union/find operation nearly constant time. After processing all edges, verify that the resulting components satisfy the partition requirements. This approach keeps validation fast even when the input size grows.
Recommended for interviews: Binary search combined with Union-Find is the approach most interviewers expect. Brute force factor testing shows you understand the problem constraints, but the optimized solution demonstrates the ability to exploit monotonic search space and efficient connectivity tracking.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Factor Testing + Graph Traversal | O(n^2 log V) | O(n) | Small inputs or when validating the partition condition conceptually |
| Binary Search + DFS/BFS Validation | O(n log V) | O(n) | General solution when graph traversal is easy to implement |
| Binary Search + Union-Find | O(n log V) | O(n) | Best choice for large arrays and repeated connectivity checks |
Leetcode Biweekly Contest 167 Editorials | Maximum Partition Factor | Design Exam Scores Tracker • Abhinav Awasthi • 1,478 views views
Watch 4 more video solutions →Practice Maximum Partition Factor with our built-in code editor and test cases.
Practice on FleetCode