Count Numbers Inside All Intervals
Company: Squarespace
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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.
Quick Answer: 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 an integer array `nums` and a list of inclusive 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. A value should be counted once for each time it appears in `nums`. If the common overlap of all intervals is empty, the answer is `0`.
Constraints
- 0 <= len(nums) <= 200000
- 1 <= len(intervals) <= 200000
- -1000000000 <= nums[i], start, end <= 1000000000
- Each interval satisfies start <= end
Examples
Input: ([1, 3, 5, 7], [[2, 6], [1, 5], [3, 8]])
Expected Output: 2
Explanation: The intersection of all intervals is [3, 5]. The numbers 3 and 5 are inside it, so the answer is 2.
Input: ([2, 2, 3, 4, 5], [[1, 4], [2, 6], [2, 3]])
Expected Output: 3
Explanation: The common overlap is [2, 3]. The matching values are 2, 2, and 3. Duplicates are counted separately.
Hints
- A number belongs to every interval only if it lies in the common intersection of all intervals.
- Track the largest interval start and the smallest interval end, then count how many numbers fall within that inclusive range.