Compute intersections for each segment

You are given $n$ segments on a number line. Segment $i$ is the closed interval $[\text{startsAt}[i], \text{endsAt}[i]]$ (inclusive endpoints), with $1 \le n \le 10^5$ and $1 \le \text{startsAt}[i] \le \text{endsAt}[i] \le 10^9$.

For each segment $i$ (with $0 \le i < n$), determine how many other segments intersect it. Two segments intersect if they share at least one common point on the number line.

Return an integer array counts of length $n$, where counts[i] is the number of other segments that intersect segment $i$.

Design an algorithm that is faster than the brute-force $O(n^2)$ — aim for $O(n \log n)$ — analyze its time and space complexity, and implement:

int[] countIntersections(int[] startsAt, int[] endsAt)

Example. startsAt = [1, 3], endsAt = [4, 5] → counts = [1, 1], because segment $[1,4]$ and segment $[3,5]$ share the points $3$ and $4$.

Hint: Reframe via the complement

Counting intersections directly is awkward because the overlap condition $\text{startsAt}[i] \le \text{endsAt}[j] \text{ and } \text{startsAt}[j] \le \text{endsAt}[i]$ couples both endpoints. It is far easier to count the segments that do not intersect segment $i$ and subtract from $n-1$. Two segments fail to intersect iff one lies entirely to the left of the other.

Hint: Split the non-intersecting set in two

A segment $j$ misses segment $i$ in exactly one of two disjoint ways: $j$ ends strictly before $i$ begins ($\text{endsAt}[j] < \text{startsAt}[i]$), or $j$ begins strictly after $i$ ends ($\text{startsAt}[j] > \text{endsAt}[i]$). These two groups cannot overlap, so you can count each independently and add them.

Hint: Turn each count into a search on a sorted array

"How many $\text{endsAt}[j] < \text{startsAt}[i]$?" and "how many $\text{startsAt}[j] > \text{endsAt}[i]$?" are order-statistic queries. Sort the array of all start values and the array of all end values once, then answer every query with a binary search (lower_bound / upper_bound). Segment $i$ never counts itself, so you can query over all $n$ values and rely on the $-1$ to remove it.

Constraints & Assumptions

• $1 \le n \le 10^5$, so an $O(n^2)$ pairwise scan ($\sim 10^{10}$ operations) is too slow; target $O(n \log n)$.
• $1 \le \text{startsAt}[i] \le \text{endsAt}[i] \le 10^9$. Endpoint values fit in a 32-bit int, but intermediate counts (up to $n$) fit comfortably in int as well; the result array is int[].
• Segments are closed (inclusive) intervals; touching at a single shared endpoint counts as an intersection.
• A segment does not intersect itself; counts[i] is over the other $n-1$ segments.

Clarifying Questions to Ask

• Are endpoints inclusive, so segments that merely touch at one point (e.g. $[1,3]$ and $[3,5]$) count as intersecting? (Assume yes.)
• How should duplicate segments be treated — does each identical segment count the others, including identical copies? (Assume yes: identity is by index $i$, not by value, so two segments with the same coordinates each intersect the other.)
• Should the answer for segment $i$ include itself? (Assume no — exclude self.)
• Can a segment be degenerate ($\text{startsAt}[i] = \text{endsAt}[i]$, a single point)? (Assume yes; it still intersects anything covering that point.)
• Is the array small enough that the output fits in memory and ordinary 32-bit integers, or do we need 64-bit counts? (With $n \le 10^5$ the counts fit in 32-bit.)

What a Strong Answer Covers

• Complement insight: recognizing that intersection is hard to count directly but non-intersection decomposes cleanly into two disjoint, easy-to-count groups (segments entirely left, segments entirely right).
• Correct strict vs. non-strict boundaries: using $\text{endsAt}[j] < \text{startsAt}[i]$ and $\text{startsAt}[j] > \text{endsAt}[i]$ (strict) so that touching/equal endpoints are correctly not excluded, matching inclusive-interval semantics.
• Order-statistic queries via sorting + binary search: sorting starts and ends once, then $2n$ binary searches, for $O(n \log n)$ time and $O(n)$ extra space — with a clear complexity argument.
• Self-exclusion handling: arguing why querying over all $n$ values and subtracting one yields exactly the count over the other $n-1$ segments (segment $i$ is never in its own left or right group).
• Edge cases: duplicates, degenerate single-point segments, all-identical segments, and a single segment ($n=1 \Rightarrow [0]$) handled correctly.
• Working implementation with the stated complexity, plus verification on the given example.

Follow-up Questions

• Suppose instead of a per-segment count you only need the total number of intersecting pairs. How does your approach simplify, and what is the relationship between the per-segment counts and that total?
• If segments arrived as a stream and you had to maintain, after each insertion, the number of currently-stored segments intersecting the newest one, what data structure would you use (e.g. a balanced BST / order-statistic tree / Fenwick tree over compressed coordinates)?
• The coordinate range is up to $10^9$ but there are at most $10^5$ segments. How would coordinate compression let you replace binary search with a Fenwick (BIT) / prefix-sum approach, and when is that preferable?
• How would you extend the idea to axis-aligned rectangles in 2D (count, for each rectangle, how many others it overlaps)? What changes in the complement decomposition?

Compute intersections for each segment

Hints

1. Counting intersections directly is awkward because the overlap condition couples both endpoints. Count the segments that do NOT intersect segment i and subtract from n-1. Two segments fail to intersect iff one lies entirely to the left of the other.
2. A segment j misses segment i in exactly one of two disjoint ways: j ends strictly before i begins (endsAt[j] < startsAt[i]), or j begins strictly after i ends (startsAt[j] > endsAt[i]). These two groups cannot overlap, so count each independently and add them.
3. 'How many endsAt[j] < startsAt[i]?' and 'how many startsAt[j] > endsAt[i]?' are order-statistic queries. Sort all start values and all end values once, then answer every query with a binary search (lower_bound / upper_bound). Segment i is never in its own left or right group, so query over all n values and rely on the -1 to remove self.
4. Use STRICT inequalities (< and >) so segments that merely touch at a shared endpoint stay counted as intersecting, matching the inclusive-interval semantics.

Solution

Solution

1. The key observation: count the complement

Counting, for each segment $i$, how many other segments intersect it is awkward to attack head-on. Two closed intervals $[\text{startsAt}[i], \text{endsAt}[i]]$ and $[\text{startsAt}[j], \text{endsAt}[j]]$ intersect iff

$\text{startsAt}[i] \le \text{endsAt}[j] \quad\text{and}\quad \text{startsAt}[j] \le \text{endsAt}[i],$

which couples both endpoints of both segments — hard to count with a single sort.

The complement is much cleaner. Two segments do not intersect iff one lies entirely to the left of the other. For a fixed segment $i$, a different segment $j$ misses it in exactly one of two mutually exclusive ways:

• $j$ is entirely to the left of $i$: $\text{endsAt}[j] < \text{startsAt}[i]$, or
• $j$ is entirely to the right of $i$: $\text{startsAt}[j] > \text{endsAt}[i]$.

A segment cannot be both to the left and to the right of $i$, so these two sets are disjoint. Therefore, over all $n-1$ other segments:

$\text{counts}[i] = (n - 1) - L_i - R_i,$

where

$L_i = \#\{\,j : \text{endsAt}[j] < \text{startsAt}[i]\,\}, \qquad R_i = \#\{\,j : \text{startsAt}[j] > \text{endsAt}[i]\,\}.$

Why strict inequalities are correct. The intervals are inclusive, so segments that merely touch at a single point (e.g. $[1,3]$ and $[3,5]$ sharing $3$) do intersect and must not be subtracted. Using strict < and > ensures a segment whose end equals $i$'s start (or whose start equals $i$'s end) is not placed in the left/right group, so it correctly remains counted as an intersection.

Self-exclusion comes for free. When we compute $L_i$ and $R_i$ we may safely range $j$ over all $n$ indices, including $i$ itself: segment $i$ has $\text{endsAt}[i] \ge \text{startsAt}[i]$, so $\text{endsAt}[i] \not< \text{startsAt}[i]$ (not in the left group) and $\text{startsAt}[i] \not> \text{endsAt}[i]$ (not in the right group). Thus $i$ contributes $0$ to both $L_i$ and $R_i$, and the lone $-1$ in $(n-1)$ removes the self-pair.

2. Turning the counts into binary searches

$L_i$ asks: how many end-points are strictly less than $\text{startsAt}[i]$? $R_i$ asks: how many start-points are strictly greater than $\text{endsAt}[i]$? These are classic order-statistic queries answered in $O(\log n)$ on a sorted array:

• Sort a copy of all end values, sortedEnds. Then $L_i = \texttt{lowerBound}(\text{sortedEnds}, \text{startsAt}[i])$ — the index of the first element $\ge \text{startsAt}[i]$, i.e. the number of ends strictly below it.
• Sort a copy of all start values, sortedStarts. Then $R_i = n - \texttt{upperBound}(\text{sortedStarts}, \text{endsAt}[i])$ — upperBound is the index of the first element $> \text{endsAt}[i]$, so $n$ minus it is the number of starts strictly above it.

Sorting is done once (two arrays), then each of the $n$ segments costs two binary searches.

3. Complexity

• Time: two sorts at $O(n \log n)$, then $n$ segments $\times$ two $O(\log n)$ binary searches $= O(n \log n)$. Total $O(n \log n)$, comfortably handling $n = 10^5$.
• Space: $O(n)$ for the two sorted copies and the $O(n)$ output array. The input is not modified.

4. Reference implementation (Java)

import java.util.Arrays;

public int[] countIntersections(int[] startsAt, int[] endsAt) {
    int n = startsAt.length;
    int[] counts = new int[n];
    if (n == 0) return counts;

    int[] sortedStarts = startsAt.clone();
    int[] sortedEnds   = endsAt.clone();
    Arrays.sort(sortedStarts);
    Arrays.sort(sortedEnds);

    for (int i = 0; i < n; i++) {
        // L = number of segments ending strictly before i starts:
        //     count of sortedEnds[j] < startsAt[i]  ==  index of first element >= startsAt[i]
        int left = lowerBound(sortedEnds, startsAt[i]);
        // R = number of segments starting strictly after i ends:
        //     count of sortedStarts[j] > endsAt[i]  ==  n - index of first element > endsAt[i]
        int right = n - upperBound(sortedStarts, endsAt[i]);
        counts[i] = (n - 1) - left - right;
    }
    return counts;
}

// first index with a[idx] >= key  (count of elements strictly < key)
private int lowerBound(int[] a, int key) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] < key) lo = mid + 1; else hi = mid;
    }
    return lo;
}

// first index with a[idx] > key  (count of elements <= key)
private int upperBound(int[] a, int key) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] <= key) lo = mid + 1; else hi = mid;
    }
    return lo;
}

The same logic in Python (using bisect):

from bisect import bisect_left, bisect_right

def countIntersections(startsAt, endsAt):
    n = len(startsAt)
    if n == 0:
        return []
    sorted_starts = sorted(startsAt)
    sorted_ends = sorted(endsAt)
    counts = [0] * n
    for i in range(n):
        left = bisect_left(sorted_ends, startsAt[i])    # ends < startsAt[i]
        right = n - bisect_right(sorted_starts, endsAt[i])  # starts > endsAt[i]
        counts[i] = (n - 1) - left - right
    return counts

5. Walking the given example

startsAt = [1, 3], endsAt = [4, 5], so sortedStarts = [1, 3], sortedEnds = [4, 5], $n = 2$.

• Segment 0 $[1,4]$: $L = \#\{\text{ends} < 1\} = 0$; $R = 2 - \texttt{upperBound}([1,3], 4) = 2 - 2 = 0$. counts[0] = 1 - 0 - 0 = 1.
• Segment 1 $[3,5]$: $L = \#\{\text{ends} < 3\} = 0$; $R = 2 - \texttt{upperBound}([1,3], 5) = 2 - 2 = 0$. counts[1] = 1 - 0 - 0 = 1.

Result [1, 1], matching the expected output (the two segments share points $3$ and $4$).

6. Edge cases and how they are handled

• Touching endpoints (e.g. $[1,3]$ and $[3,5]$): strict < / > keep them out of the left/right groups, so they correctly count as intersecting.
• Duplicate / identical segments: identity is by index, not value. Two segments with the same coordinates each satisfy the intersection condition for the other, and since neither is in the other's strict-left or strict-right group, each adds $1$ to the other's count — exactly what we want.
• Degenerate single-point segments ($\text{startsAt}[i] = \text{endsAt}[i]$): handled identically; the point intersects anything covering it.
• All identical (e.g. all $[2,2]$): every pair intersects, so each counts[i] = n - 1. Check: $L_i = \#\{\text{ends} < 2\} = 0$, $R_i = \#\{\text{starts} > 2\} = 0$, giving $(n-1)-0-0 = n-1$. ✓
• Single segment ($n = 1$): returns [0] since there are no other segments. ✓
• Integer range: endpoints up to $10^9$ fit in 32-bit int; counts up to $n - 1 < 10^5$ fit in int, so no overflow concerns.

7. Addressing the follow-ups

• Total number of intersecting pairs. $\sum_i \text{counts}[i]$ counts each intersecting pair twice (once from each endpoint), so the total number of distinct intersecting pairs is $\tfrac{1}{2}\sum_i \text{counts}[i]$. You can also get it directly: total pairs $\binom{n}{2}$ minus the non-intersecting pairs, where non-intersecting pairs are counted by sorting segments and, for each, the number entirely to its left — a single sweep.
• Streaming insertion. Maintain an order-statistic structure (a balanced BST / Fenwick tree over compressed coordinates) of the stored starts and ends. On inserting a new segment, query "ends $<$ newStart" and "starts $>$ newEnd" in $O(\log n)$ to get its current intersection count, then insert its endpoints. Each operation is $O(\log n)$.
• Coordinate compression + Fenwick. With $\le 10^5$ segments but coordinates up to $10^9$, compress the distinct endpoint values to ranks $0..m-1$, then use a Fenwick tree (BIT) for prefix counts. This matches the $O(n \log n)$ bound and is preferable when the queries are interleaved with updates (the streaming case) rather than answered all at once against a static, pre-sorted array.
• 2D axis-aligned rectangles. Two rectangles overlap iff they overlap on both the $x$- and $y$-projections. The clean 1D complement no longer decomposes into two independent strict-left/right counts, so a plane sweep (sort rectangle edges by $x$, maintain an interval/segment tree over active $y$-intervals, and count active overlaps as you sweep) is the standard $O(n \log n)$ generalization.