Quick Overview

This question evaluates algorithmic problem-solving, interval reasoning, and complexity-analysis skills by requiring an efficient method to count how many other segments intersect each interval while accounting for edge cases like equal endpoints and duplicate segments.

Compute intersections for each segment

Company: MathWorks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given n segments on a number line. Segment i is [startsAt[i], endsAt[i]] (inclusive), with 1 ≤ n ≤ 1e5 and 1 ≤ startsAt[i] ≤ endsAt[i] ≤ 1e9. For each segment i (0 ≤ i < n), determine how many other segments intersect it. Two segments intersect if they share at least one common point. Return an integer array counts of length n where counts[i] is the number of intersections for segment i. Design an algorithm faster than O(n^ 2) (aim for O(n log n)), explain its time and space complexity, and implement a function countIntersections(int[] startsAt, int[] endsAt). Clarify how you handle equal endpoints and duplicate segments. Example: startsAt = [1, 3], endsAt = [4, 5] → counts = [1, 1] because [1,4] intersects [3,5] at points 3 and 4.

Overview: This question evaluates algorithmic problem-solving, interval reasoning, and complexity-analysis skills by requiring an efficient method to count how many other segments intersect each interval while accounting for edge cases like equal endpoints and duplicate segments.

You are given n segments on a number line. Segment i is the closed interval [startsAt[i], endsAt[i]] (inclusive endpoints), with 1 <= n <= 1e5 and 1 <= startsAt[i] <= endsAt[i] <= 1e9. For each segment i (0 <= i < n), determine how many OTHER segments intersect it. Two segments intersect if they share at least one common point on the number line (touching at a single shared endpoint counts as an intersection, since the intervals are closed). A segment never counts itself. Return an integer array `counts` of length n, where counts[i] is the number of other segments that intersect segment i. Aim for an O(n log n) algorithm rather than the brute-force O(n^2) pairwise scan. Example: startsAt = [1, 3], endsAt = [4, 5] -> counts = [1, 1], because segment [1,4] and segment [3,5] share the points 3 and 4.

Constraints

  • 1 <= n <= 1e5
  • 1 <= startsAt[i] <= endsAt[i] <= 1e9
  • Segments are closed (inclusive) intervals; touching at one shared endpoint counts as an intersection
  • A segment does not intersect itself; counts[i] is over the other n-1 segments
  • Identity is by index, not value: duplicate/identical segments each intersect the others

Examples

Input: ([1, 3], [4, 5])

Expected Output: [1, 1]

Explanation: Segments [1,4] and [3,5] share points 3 and 4, so each intersects exactly one other segment.

Input: ([5], [10])

Expected Output: [0]

Explanation: A single segment has no other segments to intersect.

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.

Compute intersections for each segment

mediumMathWorksSoftware Engineer

You are given n segments on a number line. Segment i is the closed interval [startsAt[i], endsAt[i]] (inclusive endpoints), with 1 <= n <= 1e5 and 1 <= startsAt[i] <= endsAt[i] <= 1e9.

For each segment i (0 <= i < n), determine how many OTHER segments intersect it. Two segments intersect if they share at least one common point on the number line (touching at a single shared endpoint counts as an intersection, since the intervals are closed). A segment never counts itself.

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

Aim for an O(n log n) algorithm rather than the brute-force O(n^2) pairwise scan.

Example: startsAt = [1, 3], endsAt = [4, 5] -> counts = [1, 1], because segment [1,4] and segment [3,5] share the points 3 and 4.

View full question (all parts)

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

For each segment ii (with 0≤i<n0 \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 nn, where counts[i] is the number of other segments that intersect segment ii.

Design an algorithm that is faster than the brute-force O(n2)O(n^2) — aim for O(nlog⁡n)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][1,4] and segment [3,5][3,5] share the points 33 and 44.

Constraints & Assumptions

  • 1≤n≤1051 \le n \le 10^5, so an O(n2)O(n^2) pairwise scan (∼1010\sim 10^{10} operations) is too slow; target O(nlog⁡n)O(n \log n).
  • 1≤startsAt[i]≤endsAt[i]≤1091 \le \text{startsAt}[i] \le \text{endsAt}[i] \le 10^9. Endpoint values fit in a 32-bit int, but intermediate counts (up to nn) 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−1n-1 segments.

Clarifying Questions to Ask

  • Are endpoints inclusive, so segments that merely touch at one point (e.g. [1,3][1,3] and [3,5][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 ii, not by value, so two segments with the same coordinates each intersect the other.)
  • Should the answer for segment ii include itself? (Assume no — exclude self.)
  • Can a segment be degenerate (startsAt[i]=endsAt[i]\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≤105n \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 endsAt[j]<startsAt[i]\text{endsAt}[j] < \text{startsAt}[i] and startsAt[j]>endsAt[i]\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 2n2n binary searches, for O(nlog⁡n)O(n \log n) time and O(n)O(n) extra space — with a clear complexity argument.
  • Self-exclusion handling: arguing why querying over all nn values and subtracting one yields exactly the count over the other n−1n-1 segments (segment ii 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⇒[0]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 10910^9 but there are at most 10510^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?

Examples

Example 1
Input
([1, 3], [4, 5])
Output
[1, 1]
Notes
Segments [1,4] and [3,5] share points 3 and 4, so each intersects exactly one other segment.
Example 2
Input
([5], [10])
Output
[0]
Notes
A single segment has no other segments to intersect.

Constraints

  • •1 <= n <= 1e5
  • •1 <= startsAt[i] <= endsAt[i] <= 1e9
  • •Segments are closed (inclusive) intervals; touching at one shared endpoint counts as an intersection
  • •A segment does not intersect itself; counts[i] is over the other n-1 segments
  • •Identity is by index, not value: duplicate/identical segments each intersect the others

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def countIntersections(startsAt: list[int], endsAt: list[int]) -> list[int]:
Sample call
countIntersections([1, 3], [4, 5])
Language
Case 1
Input
([1, 3], [4, 5])
Expected
[1, 1]
Case 2
Input
([5], [10])
Expected
[0]

Browse More Questions