SKYFALL - EDITORIAL

editorial
, , ,
1

Sky Watching - EDITORIAL

Practice

Contest

Author: kishen1912000
Editorialist: kishen1912000

DIFFICULTY:

Easy

PREREQUISITES:

Implementation, Two Pointers, Binary Search

PROBLEM:

Given N points on a line, find the maximum number of points which you can contain within a container of length L.

EXPLANATION:

Sort the x-coordinates of the stars. Now, use a two pointer approach, where the first pointer is the left end and the second pointer is the right end. Keep moving the right pointer till the difference between coordinates at the right pointer and the left pointer is \leq L. If it becomes greater than L, move the left pointer. Repeat this till the right pointer reaches the end. While doing this, update the max number of points which is right pointer - left pointer +1, and make sure you update this even when it is equal to the max, by this way the final answer you have will have will be the highest x-coordinate with the max value.

Alternate Solution:

Instead of two pointer, for each point you can use binary search to find the max number of points possible with that as the left endpoint.

Time Complexity:

O(T(NlogN + N))

SOLUTIONS:

Setter's Solution 
for _ in range(int(input())):
    n,l = [int(s) for s in input().split()]
    x = sorted([int(s) for s in input().split()])
    i = 0
    j = 1
    maxl = 1
    ansx = x[0]
    count = 1
    while j<n:
        if x[j]-x[i] > l:
            count-=1
            i+=1
        else:
            count +=1
            j+=1
        if count >= maxl:
            maxl = count
            ansx = x[i]
    print(maxl, ansx)