DEV Community: BigO Lab

Maximum Points Activated with One Addition - LeetCode-3873 Solution

BigO Lab — Mon, 16 Mar 2026 06:43:18 +0000

Today we're looking at a hard problem from a recent LeetCode contest: Maximum Points Activated with One Addition. It looks intimidating at first, but once you map out how the points interact with each other, it boils down to a classic graph problem.

Let's break it down.

The Problem

Problem link

We're given an array of points on a 2D plane. If you activate a point, every other point that shares its exact X or Y coordinate also gets activated — creating a chain reaction until nothing new can trigger.

We're allowed to add exactly one new point at any empty integer coordinate. Place it to maximize the total number of activated points.

Example:

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

Points [1,1] and [3,1] share y = 1, so they're in the same component.

[2,2] is isolated.

Add a point at [2,1] → bridges both components → all 4 points activate.

Intuition: Think in Graphs

When a problem says "if A connects to B, and B connects to C, they all trigger together" — that's a connected components problem.

Treat every point as a node. If two points share an X or Y coordinate, draw an edge between them. Points naturally cluster into isolated islands. Activate any point in an island and the whole island lights up.

Now, where does our new point fit?

Our new point has exactly one X and one Y coordinate. It acts as a bridge — hooking its X into one component and its Y into a completely different one. A single new point can connect at most two distinct components.

So the strategy is simple: find the two largest components and bridge them together.

But wait — what if that (x, y) spot is already occupied?

If it were already a point, those two components would already share a point, meaning they'd already be merged into one. So grabbing an X from component A and a Y from component B is guaranteed to land on an empty coordinate. No need to validate it.

Algorithm

Build components using Union-Find (DSU)
Group points by shared X or Y coordinates and union them
Collect all component sizes
Sort descending, take the top two and add 1 for the new point

Walkthrough

points = [[1,1], [2,2], [3,1], [2,5]]

Processing:

i=0: (1,1) → x_first[1]=0, y_first[1]=0
i=1: (2,2) → x_first[2]=1, y_first[2]=1
i=2: (3,1) → x_first[3]=2, y=1 seen → union(2, 0)  [shares y=1 with point 0]
i=3: (2,5) → x=2 seen → union(3, 1)  [shares x=2 with point 1]

Components after union:

Component A: {[1,1], [3,1]}  →  size 2
Component B: {[2,2], [2,5]}  →  size 2

Best move: bridge A and B with a new point (e.g. [1,2] — shares x=1 with A, y=2 with B)

Answer = 2 + 2 + 1 = 5

Solution

Python

class Solution:
    def maxActivated(self, points: List[List[int]]) -> int:
        n = len(points)
        parent = list(range(n))
        size = [1] * n

        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])  # path compression
            return parent[i]

        def union(i, j):
            root_i, root_j = find(i), find(j)
            if root_i != root_j:
                parent[root_i] = root_j
                size[root_j] += size[root_i]

        x_first = {}
        y_first = {}

        for i, (x, y) in enumerate(points):
            if x in x_first:
                union(i, x_first[x])
            else:
                x_first[x] = i

            if y in y_first:
                union(i, y_first[y])
            else:
                y_first[y] = i

        comp_sizes = [size[i] for i in range(n) if parent[i] == i]
        comp_sizes.sort(reverse=True)

        if len(comp_sizes) >= 2:
            return comp_sizes[0] + comp_sizes[1] + 1
        return comp_sizes[0] + 1

C++

class Solution {
public:
    int maxActivated(vector<vector<int>>& points) {
        int n = points.size();
        vector<int> parent(n), size(n, 1);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find = [&](int i) {
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        };

        auto unite = [&](int i, int j) {
            int ri = find(i), rj = find(j);
            if (ri != rj) {
                parent[ri] = rj;
                size[rj] += size[ri];
            }
        };

        unordered_map<int, int> x_first, y_first;

        for (int i = 0; i < n; ++i) {
            int x = points[i][0], y = points[i][1];

            if (x_first.count(x)) unite(i, x_first[x]);
            else x_first[x] = i;

            if (y_first.count(y)) unite(i, y_first[y]);
            else y_first[y] = i;
        }

        vector<int> comp_sizes;
        for (int i = 0; i < n; ++i)
            if (parent[i] == i)
                comp_sizes.push_back(size[i]);

        sort(comp_sizes.rbegin(), comp_sizes.rend());

        if (comp_sizes.size() >= 2)
            return comp_sizes[0] + comp_sizes[1] + 1;
        return comp_sizes[0] + 1;
    }
};

Complexity

	Complexity	Notes
Time	O(N log N)	Union-Find is ~O(N), sorting component sizes dominates
Space	O(N)	parent/size arrays + coordinate hash maps

Common Mistakes

Forgetting the +1 — The new point itself counts toward the total. Easy to miss when you're focused on bridging components.

Checking if the bridge coordinate is empty — You don't need to. As explained above, it's mathematically guaranteed to be empty. Don't waste time validating it.

Using BFS/DFS instead of Union-Find — BFS/DFS works but you'd need to build an adjacency list first, which adds complexity. Union-Find here is cleaner and faster since we're just grouping by shared coordinates.

Only checking parent[i] == i for roots — After path compression, this is the correct way to identify component roots. Don't re-use size[] values from non-root nodes.

Key Takeaway

The insight that unlocks this problem is recognizing the chain-activation rule as a graph structure. Once you see that shared coordinates create edges, Union-Find handles the rest.

The second insight — that a new point bridges at most two components and is always a valid empty cell — turns a seemingly complex optimization into just finding the two largest component sizes.

This pattern shows up in a family of problems:

Connecting islands with one bridge
Merging groups with one extra element
"What's the best single addition/connection?" problems

Whenever you see chain reactions or transitive grouping, think Union-Find first.

Longest Arithmetic Sequence After Changing At Most One Element - LeetCode-3872 Solution

BigO Lab — Mon, 16 Mar 2026 06:28:31 +0000

Today we're looking at Longest Arithmetic Sequence After Changing At Most One Element. This is one of those problems that tests your ability to take a step back and precompute states rather than trying to simulate everything brute-force.

Let's break it down.

The Problem

Problem link

We're given an integer array nums. A subarray is arithmetic if the difference between consecutive elements is constant. We're allowed to replace at most one element with any integer we want.

Return the maximum length of an arithmetic subarray we can form after making this single replacement.

Example:

Input:  nums = [9, 7, 5, 10, 1]
Output: 5

Replace 10 with 3 → [9, 7, 5, 3, 1]. Common difference of -2. Length = 5.

Brute Force

The obvious approach: iterate through every index, try replacing it, and check how long of an arithmetic subarray you can form.

What do you change it to? You look at the surrounding elements to guess the common difference, then scan left and right.

Doing this for every index is O(n²). Given constraints of N ≤ 10^5, that's a TLE. We need O(N).

Intuition

Here's the key observation.

The element we replace acts as a bridge — connecting a valid arithmetic sequence on its left to one on its right.

So instead of simulating every replacement, precompute two arrays:

left[i] — length of the longest arithmetic subarray ending at index i
right[i] — length of the longest arithmetic subarray starting at index i

Both can be built in a single O(N) pass.

Then for each index i (treated as the element we replace), look at neighbors l = i - 1 and r = i + 1. We have three options:

Extend left only — append our replaced element to the sequence ending at l. Length = left[l] + 1
Extend right only — prepend our replaced element to the sequence starting at r. Length = right[r] + 1
Bridge both sides — make nums[i] the exact middle value between nums[l] and nums[r]. This requires (nums[r] - nums[l]) % 2 == 0. The needed diff = (nums[r] - nums[l]) / 2. If the sequences on both sides share this diff, we can merge them through our replaced element.

Walkthrough

nums = [9, 7, 5, 10, 1]

Build left:

left[0] = 1
left[1] = 2  (7-9 == 9-? no, just start fresh → diff -2, length 2)
left[2] = 3  (5-7 == 7-9 ✓, diff -2, extend)
left[3] = 2  (10-5 ≠ 7-5, reset)
left[4] = 2  (1-10 ≠ 10-5, reset)

Build right:

right[4] = 1
right[3] = 2  (1-10 = -9, length 2)
right[2] = 2  (10-5 ≠ 1-10, reset)
right[1] = 3  (5-7 == 7-9 ✓, diff -2, extend)
right[0] = 4

Try bridging at i = 3 (value 10), l = 2, r = 4:

nums[l] = 5, nums[r] = 1
(1 - 5) = -4, -4 % 2 == 0 ✓
diff = -4 / 2 = -2

curr_len = 3  (nums[2], replaced nums[3], nums[4])

Check left: nums[2] - nums[1] = 5 - 7 = -2 == diff ✓
  → curr_len += left[2] - 1 = 3 - 1 = 2  →  curr_len = 5

ans = max(ans, 5) = 5 ✓

Solution

Python

class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n

        # left[i] = length of longest arithmetic subarray ending at i
        left = [2] * n
        left[0] = 1
        for i in range(2, n):
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                left[i] = left[i-1] + 1

        # right[i] = length of longest arithmetic subarray starting at i
        right = [2] * n
        right[-1] = 1
        for i in range(n-3, -1, -1):
            if nums[i+1] - nums[i] == nums[i+2] - nums[i+1]:
                right[i] = right[i+1] + 1

        ans = 2

        # Edge case: modifying first or last element
        ans = max(ans, right[1] + 1)
        ans = max(ans, left[n-2] + 1)

        # Try modifying each middle element
        for i in range(1, n - 1):
            l, r = i - 1, i + 1

            # Option 1 & 2: extend from one side only
            ans = max(ans, left[l] + 1, right[r] + 1)

            # Option 3: bridge both sides
            if (nums[r] - nums[l]) % 2 == 0:
                diff = (nums[r] - nums[l]) // 2
                curr_len = 3  # nums[l], replaced nums[i], nums[r]

                if l > 0 and (nums[l] - nums[l-1]) == diff:
                    curr_len += left[l] - 1

                if r < n - 1 and (nums[r+1] - nums[r]) == diff:
                    curr_len += right[r] - 1

                ans = max(ans, curr_len)

        return ans

C++

class Solution {
public:
    int longestArithmetic(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) return n;

        vector<int> left(n, 2), right(n, 2);
        left[0] = 1; right[n-1] = 1;

        for (int i = 2; i < n; ++i) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2])
                left[i] = left[i-1] + 1;
        }

        for (int i = n - 3; i >= 0; --i) {
            if (nums[i+1] - nums[i] == nums[i+2] - nums[i+1])
                right[i] = right[i+1] + 1;
        }

        int ans = 2;
        ans = max(ans, right[1] + 1);
        ans = max(ans, left[n-2] + 1);

        for (int i = 1; i < n - 1; ++i) {
            int l = i - 1, r = i + 1;
            ans = max({ans, left[l] + 1, right[r] + 1});

            if ((nums[r] - nums[l]) % 2 == 0) {
                int diff = (nums[r] - nums[l]) / 2;
                int curr_len = 3;

                if (l > 0 && (nums[l] - nums[l-1]) == diff)
                    curr_len += left[l] - 1;

                if (r < n - 1 && (nums[r+1] - nums[r]) == diff)
                    curr_len += right[r] - 1;

                ans = max(ans, curr_len);
            }
        }

        return ans;
    }
};

Complexity

	Complexity	Notes
Time	O(N)	Three sequential passes, no nested loops
Space	O(N)	Two extra arrays of size N

Common Mistakes

Forgetting the edge cases — The first and last elements are a special case since they don't have neighbors on both sides. Handle right[1] + 1 and left[n-2] + 1 separately before the main loop.

Even check for bridging — When trying to bridge, (nums[r] - nums[l]) must be even for an integer middle value to exist. Skip it if it's odd.

Off-by-one when merging — When adding the left sequence length into curr_len, it's left[l] - 1 (not left[l]), because nums[l] is already counted in the base curr_len = 3.

Key Takeaway

When you're allowed to change one element, that element becomes a bridge. The trick is to precompute what exists on each side so you can evaluate every possible bridge position in O(1).

This pattern — precomputing prefix/suffix states and combining them at each index — shows up constantly in problems involving:

At most one replacement / deletion
Merging two valid subarrays through a single element
Sliding window variants with one "free pass"

Whenever you see "change at most one element", think about what you can precompute from the left and from the right.

Count Commas in Range - LeetCode-3870 Solution

BigO Lab — Sun, 15 Mar 2026 11:17:45 +0000

Today we're looking at Count Commas in Range. It's a pretty interesting problem that can easily trick you into writing a slow solution, especially once the constraints get big.

Let's break it down.

The Problem

Problem Link

We're given an integer n. We need to figure out the total number of commas used when writing all integers from 1 to n in standard format.

999 → 0 commas
1,000 → 1 comma
1,000,000 → 2 commas

We just return the total sum of all those commas.

Example 1:

Input:  n = 1000
Output: 1

Example 2:

Input:  n = 1000000
Output: 2998001

Brute Force

The most obvious way is to just loop through every number from 1 to n, count its commas, and add to a running total.

def countCommas(n: int) -> int:
    total = 0
    for i in range(1, n + 1):
        digits = len(str(i))
        total += (digits - 1) // 3
    return total

Does that work? Technically, yes.

But look at the constraints. If n goes up to 10^15, an O(n) solution is way too slow. Time Limit Exceeded. We need a math approach.

Intuition

Instead of iterating through numbers and asking "how many commas does this number have?", let's flip the question.

Think about the comma thresholds:

The first comma appears at 1,000. So every number from 1,000 to n contributes at least 1 comma.
The second comma appears at 1,000,000. So every number from 1,000,000 to n contributes 1 more comma.
The third comma appears at 1,000,000,000. Same idea.

So we don't need to look at individual numbers at all. We just ask: how many numbers crossed each threshold?

Count of numbers >= threshold in [1, n] is simply n - threshold + 1.

Walkthrough

Let's trace n = 1,500,000:

threshold = 1,000

n >= 1000 ✓
count = 1500000 - 1000 + 1 = 1,499,001

threshold = 1,000,000

n >= 1000000 ✓
count = 1500000 - 1000000 + 1 = 500,001

threshold = 1,000,000,000

n >= 1000000000 ✗  →  stop

Total = 1,499,001 + 500,001 = 1,999,002

Two iterations. Done.

Solution

Python

class Solution:
    def countCommas(self, n: int) -> int:
        total = 0
        threshold = 1000

        while n >= threshold:
            total += n - threshold + 1
            threshold *= 1000

        return total

JavaScript

var countCommas = function(n) {
    let total = 0;
    let threshold = 1000;

    while (n >= threshold) {
        total += n - threshold + 1;
        threshold *= 1000;
    }

    return total;
};

Java

class Solution {
    public long countCommas(long n) {
        long total = 0;
        long threshold = 1000;

        while (n >= threshold) {
            total += n - threshold + 1;
            threshold *= 1000;
        }

        return total;
    }
}

⚠️ Use long in Java. For n = 10^15 the result can exceed Integer.MAX_VALUE.

Verification

n = 1000:

threshold = 1000:    ✓  →  total += 1000 - 1000 + 1 = 1
threshold = 1000000: ✗  →  stop

Output: 1 ✓

n = 9999:

threshold = 1000:    ✓  →  total += 9999 - 1000 + 1 = 9000
threshold = 1000000: ✗  →  stop

Output: 9000 ✓

Numbers 1,000 through 9,999 — exactly 9,000 four-digit numbers, each with one comma. Makes sense.

Complexity

	Complexity	Notes
Time	O(log n)	Loop runs ~5 times even for n = 10^15
Space	O(1)	Just two variables

Common Mistakes

Off-by-one — count is n - threshold + 1, not n - threshold. Easy to miss.
Wrong starting threshold — start at 1000, not 100. Numbers like 100 don't get commas.
Integer overflow — in Java/C++, use long. Python handles big integers natively.

Key Takeaway

The pattern here is counting contributions layer by layer. Instead of iterating over every number, iterate over the boundaries.

You'll see this same pattern in:

Count digits in a range
Count integers with a specific digit count in [1, n]
Number of set bits across all integers from 1 to n

Whenever a problem asks you to count some property across all integers in [1, n], think thresholds first. The brute force loops over numbers. The optimal solution loops over boundaries.

Did anyone else get stuck trying to do this with string formatting, or was it just me? Let me know in the comments!