LeetCode-in-Java

3873. Maximum Points Activated with One Addition

Hard

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

If a point is activated, then all points that have the same x-coordinate or y-coordinate become activated as well.

Activation continues until no additional points can be activated.

You may add one additional point at any integer coordinate (x, y) not already present in points. Activation begins by activating this newly added point.

Return an integer denoting the maximum number of points that can be activated, including the newly added point.

Example 1:

Input: points = [[1,1],[1,2],[2,2]]

Output: 4

Explanation:

Adding and activating a point such as (1, 3) causes activations:

(1, 3) shares x = 1 with (1, 1) and (1, 2) -> (1, 1) and (1, 2) become activated.
(1, 2) shares y = 2 with (2, 2) -> (2, 2) becomes activated.

Thus, the activated points are (1, 3), (1, 1), (1, 2), (2, 2), so 4 points in total. We can show this is the maximum activated.

Example 2:

Input: points = [[2,2],[1,1],[3,3]]

Output: 3

Explanation:

Adding and activating a point such as (1, 2) causes activations:

(1, 2) shares x = 1 with (1, 1) -> (1, 1) becomes activated.
(1, 2) shares y = 2 with (2, 2) -> (2, 2) becomes activated.

Thus, the activated points are (1, 2), (1, 1), (2, 2), so 3 points in total. We can show this is the maximum activated.

Example 3:

Input: points = [[2,3],[2,2],[1,1],[4,5]]

Output: 4

Explanation:

Adding and activating a point such as (2, 1) causes activations:

(2, 1) shares x = 2 with (2, 3) and (2, 2) -> (2, 3) and (2, 2) become activated.
(2, 1) shares y = 1 with (1, 1) -> (1, 1) becomes activated.

Thus, the activated points are (2, 1), (2, 3), (2, 2), (1, 1), so 4 points in total.

Constraints:

1 <= points.length <= 10⁵
points[i] = [x_i, y_i]
-10⁹ <= x_i, y_i <= 10⁹
points contains all distinct coordinates.

Solution

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int maxActivated(int[][] points) {
        return maxEnergized(points);
    }

    private int maxEnergized(int[][] relays) {
        int n = relays.length;
        int[] parent = new int[n];
        int[] size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        Map<Integer, Integer> firstInCol = HashMap.newHashMap(n * 2);
        Map<Integer, Integer> firstInRow = HashMap.newHashMap(n * 2);
        for (int i = 0; i < n; i++) {
            int col = relays[i][0];
            int row = relays[i][1];
            Integer c = firstInCol.putIfAbsent(col, i);
            if (c != null) {
                union(parent, size, c, i);
            }
            Integer r = firstInRow.putIfAbsent(row, i);
            if (r != null) {
                union(parent, size, r, i);
            }
        }
        int best1 = 0;
        int best2 = 0;
        for (int i = 0; i < n; i++) {
            if (find(parent, i) == i) {
                int s = size[i];
                if (s >= best1) {
                    best2 = best1;
                    best1 = s;
                } else if (s > best2) {
                    best2 = s;
                }
            }
        }
        return best1 + best2 + 1;
    }

    private int find(int[] parent, int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    private void union(int[] parent, int[] size, int a, int b) {
        int ra = find(parent, a);
        int rb = find(parent, b);
        if (ra == rb) {
            return;
        }
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;
        size[ra] += size[rb];
    }
}

This site is open source. Improve this page.