cswork / libraryOpen practice workspace

Coding questions · Squarespace

Count Numbers Inside All Intervals

This question evaluates the ability to compute intersections of numeric intervals and perform efficient counting over an array, testing competencies in range handling, multiplicity accounting, and time-complexity-aware algorithm design.

You are given:

  1. An integer array nums.
  2. A list of intervals intervals, where each interval is represented as [start, end]. The intervals are not sorted.

Count how many elements in nums belong to every interval.

Additional assumptions for clarity:

  • Interval boundaries are inclusive.
  • Each interval satisfies start <= end.
  • If a value appears multiple times in nums, count each occurrence separately.

Example:

  • nums = [1, 3, 5, 7]
  • intervals = [[2, 6], [1, 5], [3, 8]]

The overlap of all intervals is [3, 5], so the valid numbers are 3 and 5. The answer is 2.

Design an efficient algorithm to solve this problem.

Count Numbers Inside All Intervals

Constraints

  • 0 <= len(nums) <= 200000
  • 1 <= len(intervals) <= 200000
  • -1000000000 <= nums[i], start, end <= 1000000000
  • Each interval satisfies start <= end

Hints

  1. A number belongs to every interval only if it lies in the common intersection of all intervals.
  2. Track the largest interval start and the smallest interval end, then count how many numbers fall within that inclusive range.