Solve interval deletion and GCD subarray problems
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
1) Given n closed intervals [li, ri] on a number line, remove the fewest intervals so that among the remaining intervals there exists at least one interval that fully covers all other remaining intervals (i.e., there is [L, R] such that for every remaining [l, r], L <= l and r <= R). Return the minimum number of deletions required and describe an algorithm with time and space complexity.
2) Given an integer array nums and an integer k (maximum number of elements you may change within a chosen subarray), find the minimum length of a contiguous subarray such that, after modifying at most k elements inside that subarray to any positive integers of your choice, the subarray’s greatest common divisor is greater than 1. Return the minimal length and outline an efficient approach. Example: nums = [2, 2, 4, 9, 6], k = 1 -> output 1.
Overview: This question evaluates proficiency in combinatorial algorithms, specifically interval covering and GCD-based subarray optimization. It tests the ability to design efficient near-linearithmic solutions for classic greedy and number-theory problems commonly assessed in software engineering interviews.
Fewest Interval Deletions So One Interval Covers the Rest
Given `n` closed intervals `[l_i, r_i]` on a number line, remove the **fewest** intervals so that, among the remaining intervals, at least one interval **fully covers all the others** — i.e. there exists a remaining `[L, R]` such that for every remaining `[l, r]` we have `L <= l` and `r <= R`. Return the minimum number of deletions required.
The covering interval must be one of the remaining intervals (not a virtual super-interval), and an interval is considered to cover itself. Intervals may be identical, nested, or disjoint. Endpoints can be large.
**Reduction:** minimizing deletions equals maximizing how many intervals you keep under a single chosen container. For container `[L, R]`, the keepable intervals are exactly those with `l >= L` and `r <= R`; let `c` be that count (the container counts itself). The answer is `n - max(c)`.
Example: `[[1,10],[2,3],[4,5],[6,7]]` -> `0` (the interval `[1,10]` already covers all others).
Example: `[[1,2],[3,4],[5,6]]` -> `2` (pairwise disjoint, keep only one).
Constraints
- 0 <= n <= 10^5
- Each interval is [l, r] with l <= r (degenerate point intervals l == r allowed)
- Endpoints may exceed 32-bit range; coordinate-compress right endpoints
- Intervals may be identical, nested, or disjoint
Examples
Input: ([[1, 10], [2, 3], [4, 5], [6, 7]],)
Expected Output: 0
Explanation: [1,10] already covers [2,3],[4,5],[6,7], so no deletions are needed.
Input: ([[1, 2], [3, 4], [5, 6]],)
Expected Output: 2
Explanation: All three are pairwise disjoint; the best container holds only itself, so keep 1 and delete 2.
Hints
- Minimizing deletions equals maximizing kept intervals under one chosen container. Fix a container [L, R]; what must every other kept interval satisfy? (l >= L and r <= R.)
- Counting how many intervals a container dominates is a two-sided 2D dominance count. Eliminate one inequality by sorting on the left endpoint, and answer the other with a Fenwick/BIT prefix query over compressed right endpoints.
- Handle ties carefully: insert ALL intervals sharing the same left endpoint into the BIT before querying any of them, so an equal-L interval (including the container itself and exact duplicates) is counted iff its right endpoint <= R.
Shortest Subarray With GCD > 1 After At Most k Changes
Given an integer array `nums` and an integer `k` (the maximum number of elements you may change **inside a chosen contiguous subarray**), find the **minimum length** of a contiguous subarray such that, after modifying at most `k` of its elements to any positive integers of your choice, the subarray's greatest common divisor is greater than 1. Return the minimal length, or `-1` if no valid subarray exists.
**Key insight:** `gcd > 1` iff some prime `p` divides every element. Inside the window you may set up to `k` elements to multiples of `p` for free, so a window is feasible for prime `p` iff at most `k` of its elements are NOT divisible by `p`. Candidate primes can be restricted to the prime factors of array elements (a prime dividing nothing only ever helps a window of length <= k, already covered by the length-1 case when k >= 1).
For each candidate prime, a two-pointer sliding window counting non-multiples finds the shortest feasible window; take the global minimum (plus the universal length-1 window when `k >= 1`).
Example: `nums = [2,2,4,9,6]`, `k = 1` -> `1` (the single element `2` already has gcd 2 > 1, no change needed).
Return `-1` only when `k = 0` and every element equals 1 (no prime divides any element).
Constraints
- 0 <= n <= 10^5
- 1 <= nums[i] (positive integers; may exceed 32-bit — use trial division / Pollard-rho instead of the sieve for very large values)
- 0 <= k <= n
- Return -1 when no valid subarray exists (only when k == 0 and every element equals 1)
Examples
Input: ([2, 2, 4, 9, 6], 1)
Expected Output: 1
Explanation: The single element 2 already has gcd 2 > 1 with zero changes, so the minimum length is 1.
Input: ([6, 10, 15], 0)
Expected Output: 1
Explanation: With k=0, the single element 6 alone has gcd 6 > 1, so length 1 suffices.
Hints
- gcd > 1 over a set means a single prime p divides every element. A changed element can always be made a multiple of p, so changes are free with respect to p — only unchanged non-multiples constrain you.
- You cannot try every prime. A prime is only worth testing if it divides at least one array element; any other prime makes every element a non-multiple, so it only helps windows of length <= k (already covered by the length-1 case when k >= 1). Factor each value with an SPF sieve.
- For each candidate prime, run a two-pointer window counting non-multiples; shrink while the count exceeds k. The shortest feasible window over all primes (and the universal length-1 window when k >= 1) is the answer; impossible only when k == 0 and all elements are 1.
Community answers
Answer by subnr01
#include
using namespace std;
int minDeletions(vector>& intervals) {
int n = intervals.size();
int maxContained = 0;
for (int i = 0; i < n; i++) {
int L = intervals[i].first;
int R = intervals[i].second;
int count = 0;
for (int j = 0; j < n; j++) {
if (L <= intervals[j].first &&
intervals[j].second <= R) {
count++;
}
}
maxContained = max(maxContained, count);
}
return n - maxContained;
}
#include
using namespace std;
// Get unique prime factors of x
vector getPrimeFactors(int x) {
vector primes;
for (int d = 2; d * d <= x; d++) {
if (x % d == 0) {
primes.push_back(d);
while (x % d == 0)
x /= d;
}
}
if (x > 1)
primes.push_back(x);
return primes;
}
int minSubarrayLength(vector& nums, int k) {
int n = nums.size();
// Collect all primes that appear
unordered_set allPrimes;
for (int x : nums) {
vector pf = getPrimeFactors(x);
for (int p : pf)
allPrimes.insert(p);
}
int ans = INT_MAX;
// Try each prime
for (int p : allPrimes) {
int left = 0;
int bad = 0;
for (int right = 0; right < n; right++) {
if (nums[right] % p != 0)
bad++;
while (bad > k) {
if (nums[left] % p != 0)
bad--;
left++;
}
ans = min(ans, right - left + 1);
}
}
return (ans == INT_MAX ? -1 : ans);
}