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.
Overview: 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.
Community answers
Answer by Dharmaraj140291
public class Check {
static int[] minMax(int[][] intervals){
int[] ans = {Integer.MIN_VALUE,Integer.MAX_VALUE};
for (int i = 0; i < intervals.length; i++) {
if(intervals[i][0]>=ans[0]) {
ans[0]=intervals[i][0];
}
if(intervals[i][1]<=ans[1]) {
ans[1]=intervals[i][1];
}
}
return ans;
}
public static void main(String[] args) {
int [] arr={1,3,5,7,8};
int[][] intervals= {{8,10},{5,7},{3,8}};
int[] lapover=minMax(intervals);
int res=0;
for (int i = 0; i < arr.length; i++) {
if(lapover[0]<=arr[i] && arr[i]<=lapover[1]) {
res++;
}
}
System.out.println(res);
}
}