3710. Maximum Partition Factor

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.

class Solution {
    int dis(vector<int>& A, vector<int>& B) {
        return abs(A[0] - B[0]) + abs(A[1] - B[1]);
    }
    bool dfs(vector<vector<int>>& adj, vector<int>& vis, int u, int par) {
        for(auto& v : adj[u]) {
            if(vis[v] == vis[u]) return true;
            if(vis[v] == -1) {
                vis[v] = !vis[u];
                if(dfs(adj,vis,v,u)) return true;
            }
            
        }
        return false;
    }
    bool helper(vector<vector<int>>& A, int d) {
        vector<vector<int>> adj(A.size());
        for(int i = 0; i < A.size(); i++) {
            for(int j = i + 1; j < A.size(); j++) {
                if(dis(A[i], A[j]) < d) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        vector<int> vis(A.size(), -1);
        for(int i = 0; i < A.size(); i++) {
            if(vis[i] != -1) continue;
            vis[i] = 0;
            if(dfs(adj,vis, i,-1)) return false;
        }
        return true;
    }
public:
    int maxPartitionFactor(vector<vector<int>>& points) {
        if(points.size() == 2) return 0;
        int l = 0, r = 0, res = 0;
        for(int i = 0; i < points.size(); i++) {
            for(int j = i + 1; j < points.size(); j++) {
                r = max(r, dis(points[i], points[j]));
            }
        }
        while(l <= r) {
            int m = l + (r - l) / 2;
            bool ok = helper(points, m);
            if(ok) {
                res = m;
                l = m + 1;
            } else r = m - 1;
        }
        return res;
    }
};