Longest Strike (Codeforces 1676F)
Tags: Greedy, two pointers

Given an array $$$a$$$ of length $$$n$$$ and an integer $$$k$$$, you are tasked to find any two numbers $$$l$$$ and $$$r$$$ ($$$l \leq r$$$) such that:   For each $$$x$$$ $$$(l \leq x \leq r)$$$, $$$x$$$ appears in $$$a$$$ at least $$$k$$$ times (i.e. $$$k$$$ or more array elements are equal to $$$x$$$).  The value $$$r-l$$$ is maximized. If no numbers satisfy the conditions, output -1.For example, if $$$a=[11, 11, 12, 13, 13, 14, 14]$$$ and $$$k=2$$$, then:   for $$$l=12$$$, $$$r=14$$$ the first condition fails because $$$12$$$ does not appear at least $$$k=2$$$ times.  for $$$l=13$$$, $$$r=14$$$ the first condition holds, because $$$13$$$ occurs at least $$$k=2$$$ times in $$$a$$$ and $$$14$$$ occurs at least $$$k=2$$$ times in $$$a$$$.  for $$$l=11$$$, $$$r=11$$$ the first condition holds, because $$$11$$$ occurs at least $$$k=2$$$ times in $$$a$$$. A pair of $$$l$$$ and $$$r$$$ for which the first condition holds and $$$r-l$$$ is maximal is $$$l = 13$$$, $$$r = 14$$$.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains the integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — the length of the array $$$a$$$ and the minimum amount of times each number in the range $$$[l, r]$$$ should appear respectively.Then a single line follows, containing $$$n$$$ integers describing the array $$$a$$$ ($$$1 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case output $$$2$$$ numbers, $$$l$$$ and $$$r$$$ that satisfy the conditions, or "-1" if no numbers satisfy the conditions.If multiple answers exist, you can output any.


Sample Inputs:
4
7 2
11 11 12 13 13 14 14
5 1
6 3 5 2 1
6 4
4 3 4 3 3 4
14 2
1 1 2 2 2 3 3 3 3 4 4 4 4 4

Sample Outputs:
13 14
1 3
-1
1 4

Solution (Python):
from collections import Counter

def main():
    for test in range(int(input())):
        s = input().split()
        k = int(s[1])
        a = sorted(map(int, input().split()))
        counter = Counter(a)
        (l, r, target_l, my_max) = (-1, -1, -1, -1)
        for val in counter:
            if counter[val] < k:
                continue
            if val == r + 1:
                r = val
                if val - l > my_max:
                    (my_max, target_l) = (val - l, l)
            else:
                (l, r) = (val, val)
                if my_max == -1:
                    (my_max, target_l) = (0, l)
        if my_max != -1:
            print('{} {}'.format(target_l, target_l + my_max))
        else:
            print(-1)
main()

Solution (Python):
def di():
    return map(int, input().split())

def ii():
    return int(input())

def li():
    return list(map(int, input().split()))

def si():
    return list(map(int, input()))
import sys

def check(nums, k):
    numbers = nums.split()
    numbers.sort(key=int)
    numbersktimes = []
    counter = 1
    prev = 'a'
    for i in numbers:
        if prev == i:
            counter += 1
        else:
            counter = 1
        if counter == k:
            numbersktimes.append(int(i))
        prev = i
    if len(numbersktimes) == 0:
        print(-1)
    else:
        longestFirst = numbersktimes[0]
        longestLast = numbersktimes[0]
        prev = numbersktimes[0]
        start = numbersktimes[0]
        for index in range(1, len(numbersktimes)):
            elem = numbersktimes[index]
            if elem == prev + 1:
                if elem - start > longestLast - longestFirst:
                    longestLast = elem
                    longestFirst = start
            else:
                start = elem
            prev = elem
        print(longestFirst, longestLast)

def main():
    numTestcases = int(sys.stdin.readline())
    for line in range(numTestcases):
        lengthandtimes = sys.stdin.readline()
        lt = lengthandtimes.split()
        check(sys.stdin.readline(), int(lt[1]))
main()

Solution (Python):
def helper(ar):
    ar.sort()
    i = 0
    (l, r) = (-1, -1)
    finalans = [-1, -1]
    while i < len(ar):
        c = 1
        while i + 1 < len(ar) and ar[i + 1] == ar[i]:
            i += 1
            c += 1
        if c >= k and r != -1 and (r == ar[i] - 1):
            r += 1
        elif c >= k:
            (l, r) = (ar[i], ar[i])
        if finalans[1] - finalans[0] <= r - l:
            finalans = [l, r]
        i += 1
    return finalans
t = int(input())
for i in range(t):
    (n, k) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    (l, r) = helper(a)
    if l != -1:
        print(l, r)
    else:
        print(l)