4035. Maximum Partition Factor¶

Difficulty: Hard

4035. Maximum Partition Factor

Hard

You are given a 2D integer array points, where points[i] = [x_i, y_i] represents the coordinates of the i^th point on the Cartesian plane.

The Manhattan distance between two points points[i] = [x_i, y_i] and points[j] = [x_j, y_j] is |x_i - x_j| + |y_i - y_j|.

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 <= 500
points[i] = [x_i, y_i]
-10⁸ <= x_i, y_i <= 10⁸

Solution¶

class Solution {
    private ArrayList<ArrayList<Integer>> adj;
    private int vis[];
    private int color[];
    public int maxPartitionFactor(int[][] points) {
        int n = points.length;
        if (n <= 2)
            return 0;
        int low = 0, high = (int)(1e9), ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, points)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
    private boolean ok(int target, int points[][]) {
        int n = points.length;
        adj = new ArrayList<>();
        for (int i = 0; i <= n + 1; i++)
            adj.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
                int dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);
                if (dist < target) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }
            }
        }
        boolean res = true;
        vis = new int[n + 1];
        color = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (vis[i] == 0) {
                res &= dfs(i, -1, 1);
            }
        }
        return res;
    }
    private boolean dfs(int u, int par, int currentColor) {
        vis[u] = 1;
        color[u] = currentColor;
        boolean ans = true;
        for (int v : adj.get(u)) {
            if (vis[v] == 0) {
                ans &= dfs(v, u, currentColor ^ 1);
            } else {
                if (color[v] == currentColor) 
                    ans = false;
            }
        }
        return ans;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here