Infosys
Online AssessmentMaximum Points Covered by a Length-L Window
You are given an array pts of N integers representing point positions on a number line. You are also given a window length L and a modulo factor K.
You must select a subset of points from pts that satisfies two conditions:
1. All points in your selected subset must yield the exact same remainder when divided by K.
2. The difference between the absolute maximum position and the absolute minimum position in your selected subset must be less than or equal to L (i.e. max(subset) - min(subset) <= L).
Find the maximum number of points you can include in a valid subset.
- ▸First line: integer N, denoting the number of points.
- ▸Second line: integer L, denoting window length.
- ▸Third line: integer K, denoting modulo factor.
- ▸Fourth line: N space-separated integers representing point positions pts[i].
- ▸Print a single integer representing the maximum number of points in a valid subset.
- 1 <= N <= 10^5
- 1 <= L <= 10^9
- 1 <= K <= 10^9
- -10^9 <= pts[i] <= 10^9
8 6 3 1 4 7 10 13 2 5 8
3
Points with remainder 1 modulo 3: [1, 4, 7, 10, 13].
Subarrays with range <= 6:
- [1, 4, 7]: 7 - 1 = 6 <= 6 (3 points)
- [4, 7, 10]: 10 - 4 = 6 <= 6 (3 points)
- [7, 10, 13]: 13 - 7 = 6 <= 6 (3 points)
Points with remainder 2 modulo 3: [2, 5, 8]: 8 - 2 = 6 <= 6 (3 points).
Maximum valid subset size is 3.
1. Partition points into buckets based on their normalized remainder modulo K: `rem = ((pts[i] % K) + K) % K`. 2. For each remainder bucket, sort its coordinates in ascending order. 3. Apply a two-pointer sliding window on each bucket: - Expand the right pointer `R`. - While `bucket[R] - bucket[L] > L`, advance `L++`. - Update `maxPoints = max(maxPoints, R - L + 1)`. 4. Time Complexity: O(N log N) for sorting, O(N) for sliding window.