Quick Overview

This question evaluates a candidate's ability to reason about interval overlap counting, manage range endpoints efficiently, and balance time-space trade-offs when identifying points that maximize coverage.

Find integer in most intervals

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question Given N integer intervals [ai, bi] (positive integers), find an integer that belongs to the maximum number of intervals (return any such integer if several exist). Follow-up: When every endpoint is < M and M is small, how would you optimize?

Overview: This question evaluates a candidate's ability to reason about interval overlap counting, manage range endpoints efficiently, and balance time-space trade-offs when identifying points that maximize coverage.

You are given N closed intervals of positive integers, intervals[i] = [ai, bi] with ai <= bi. Find an integer x that lies in the maximum number of intervals. If multiple integers achieve this maximum coverage, return the smallest such integer.

Constraints

  • 1 <= N <= 200000
  • 1 <= ai <= bi <= 10^9
  • Intervals are closed: x is covered by [a,b] if a <= x <= b
  • If multiple integers tie for maximum coverage, return the smallest integer

Hints

  1. Transform intervals into events: +1 at ai and -1 at bi+1 (difference array idea for inclusive intervals).
  2. Sort event positions and compute a running sum (prefix) to track active intervals; the first position reaching a new maximum is your answer.
  3. If all endpoints are less than a small M, use an array of length M+2 for O(N+M) time via difference array and prefix sums.

Loading coding console...

Show the approach

Approach

Use a sweep-line over integer coordinates with a difference map: for each [a,b], add +1 at a and -1 at b+1. After sorting the event positions, a running prefix sum gives the number of active intervals at each integer. Track the maximum prefix value and record the smallest position where it occurs. This corresponds to the smallest integer covered by the most intervals. For the follow-up where all endpoints are less than a small M, build an array diff of size M+2, apply the same +1/-1 updates, compute a prefix sum, and find the index with the maximum value in O(N+M) time.

Time complexity:
O(N log N)
Space complexity:
O(N)