Introduction

The intersecting-discs problem asks how many disc pairs overlap when disc i is centered at index i with radius A[i]. A brute-force check of every pair is too slow for large input. The standard efficient solution converts each disc into an interval and counts overlaps with a sweep-style algorithm.

Convert discs into intervals

Disc i spans from i - A[i] to i + A[i]. Two discs intersect when those intervals overlap.

For example, if A = [1, 5, 2]:

• disc 0 spans -1 to 1
• disc 1 spans -4 to 6
• disc 2 spans 0 to 4

Once you think in intervals, the geometry becomes much simpler. You are no longer comparing circles directly. You are comparing start and end points on a line.

Why the naive solution is too slow

The obvious method compares every disc with every later disc:

1def slow_count(a):
2    total = 0
3    for i in range(len(a)):
4        for j in range(i + 1, len(a)):
5            if i + a[i] >= j - a[j]:
6                total += 1
7    return total

This is O(N^2), which is far too slow for typical interview or challenge constraints. The expected approach is usually O(N log N).

Sort starts and ends separately

The efficient solution builds two arrays:

• 'starts: every disc's left boundary'
• 'ends: every disc's right boundary'

Then sort both arrays and walk through them.

1def count_intersections(a):
2    n = len(a)
3    starts = [i - radius for i, radius in enumerate(a)]
4    ends = [i + radius for i, radius in enumerate(a)]
5
6    starts.sort()
7    ends.sort()
8
9    intersections = 0
10    open_discs = 0
11    start_idx = 0
12
13    for end_idx in range(n):
14        while start_idx < n and starts[start_idx] <= ends[end_idx]:
15            intersections += open_discs
16            if intersections > 10_000_000:
17                return -1
18            open_discs += 1
19            start_idx += 1
20
21        open_discs -= 1
22
23    return intersections
24
25
26print(count_intersections([1, 5, 2, 1, 4, 0]))

That example returns 11.

Why the sweep logic works

Think of the sorted boundaries as events:

• a start event means a new disc opens
• an end event means a disc closes

When a new disc opens, it intersects every disc that is already open. So if open_discs is currently 3, the new disc contributes 3 new intersections immediately.

After counting those new pairs, increment open_discs because the new disc is now active too. When you pass an end boundary, decrement open_discs because one disc is no longer active.

This avoids checking pairs explicitly. Instead of asking whether disc i intersects disc j, you count intersections in groups using how many discs are currently open.

Handle boundary details correctly

There are a few details that matter:

• touching counts as intersecting, so use <= rather than <
• boundaries can be large, so use a wide numeric type in fixed-width languages
• some versions of the problem require returning -1 if the count exceeds 10_000_000

That last rule is why the early return appears inside the counting loop rather than after everything finishes.

In Java or C#, store interval endpoints in long rather than int if the radius values may be large.

This is a sweep-line pattern, not a geometry trick

The deeper lesson is not just about discs. This is a classic sweep-line or event-counting pattern:

1. turn each object into start and end events
2. sort the events
3. count how many objects are active as you sweep

The same idea appears in interval overlap problems, meeting-room scheduling, maximum concurrent sessions, and similar tasks.

Common Pitfalls

The most common mistake is sticking with the quadratic pairwise solution when the problem clearly needs better performance.

Another common issue is forgetting that intervals that only touch at a boundary still count as intersections in the standard version of the problem.

People also update the active-disc counter in the wrong order. The count should be added before the new disc is marked open, because the new disc intersects the discs that were already active.

Finally, fixed-width languages can overflow if the endpoints are stored in a type that is too small.

Summary

• Model each disc as an interval from i - A[i] to i + A[i].
• Sort interval starts and ends separately.
• Count intersections by tracking how many discs are currently open.
• The efficient solution runs in O(N log N) because sorting dominates the work.
• The core idea is a sweep-line event algorithm, not pairwise geometry checks.