Tap here to switch tabs
Problem
Submissions

Problem: Maximum Points Activated with One Addition

Try to solve the Maximum Points Activated with One Addition problem.

Statement

You are given a 2extD2 ext{D} integer array points, where points[i] =[xi,yi]= [x_i, y_i] represents the coordinates of distinct points on a 2extD2 ext{D} plane.

Two points are connected if they share the same xx coordinate or the same yy coordinate.

You may choose any coordinate (x,y)(x, y) on the plane, add a new point at that location, and activate it. When a point is activated, any unactivated point that shares an xx coordinate or a yy coordinate with an already activated point also becomes activated in a chain reaction.

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

Constraints:

  • 1≤1 \leq points.length ≤105\leq 10^5

  • points[i] =[xi,yi]= [x_i, y_i]

  • −109≤xi,yi≤109-10^9 \leq x_i, y_i \leq 10^9

  • points contains all distinct coordinates.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Points Activated with One Addition

Try to solve the Maximum Points Activated with One Addition problem.

Statement

You are given a 2extD2 ext{D} integer array points, where points[i] =[xi,yi]= [x_i, y_i] represents the coordinates of distinct points on a 2extD2 ext{D} plane.

Two points are connected if they share the same xx coordinate or the same yy coordinate.

You may choose any coordinate (x,y)(x, y) on the plane, add a new point at that location, and activate it. When a point is activated, any unactivated point that shares an xx coordinate or a yy coordinate with an already activated point also becomes activated in a chain reaction.

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

Constraints:

  • 1≤1 \leq points.length ≤105\leq 10^5

  • points[i] =[xi,yi]= [x_i, y_i]

  • −109≤xi,yi≤109-10^9 \leq x_i, y_i \leq 10^9

  • points contains all distinct coordinates.