Practice › Heap & Priority Queue
Hand of Straights
Medium · Heap & Priority Queue · Asked at Google, Amazon, Microsoft
Can the cards be split into groups of exactly k cards where each group is k consecutive values (like 3,4,5)? Print YES or NO.
Input
First line: n k. Second line: the n card values.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^4
- 1 ≤ k ≤ n
- 0 ≤ value ≤ 10^9
The smallest remaining card must start a group. Count the cards, then repeatedly take the smallest value v and use one of v, v+1, …, v+k−1 (a min-heap or sorted map).
Example 1
Input
9 3 1 2 3 6 2 3 4 7 8
Output
YES
Example 2
Input
5 4 1 2 3 4 5
Output
NO
Hints
- If n is not divisible by k, the answer is NO immediately.
- The smallest remaining card can only be the start of a group. Use counts in a sorted map (or a min-heap) and always build the group starting at the smallest card.
Approach
Count each value in an ordered map. Walk the values in increasing order; for value v with remaining count t > 0, exactly t groups must start at v, so each of v, v+1, …, v+k−1 must have at least t cards — subtract t from each, or answer NO if one is short. If the walk finishes, the answer is YES.
Complexity: O(n log n + n·k) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
map<long long, int> cnt;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
cnt[x]++;
}
if (n % k) {
cout << "NO\n";
return 0;
}
for (auto &e : cnt) {
int t = e.second;
if (t == 0) continue;
for (int i = 0; i < k; i++) {
auto it = cnt.find(e.first + i);
if (it == cnt.end() || it->second < t) {
cout << "NO\n";
return 0;
}
it->second -= t;
}
}
cout << "YES\n";
return 0;
}Python solution
import sys
from collections import Counter
data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
cnt = Counter(data[2 : 2 + n])
ok = n % k == 0
if ok:
for v in sorted(cnt):
t = cnt[v]
if t == 0:
continue
for i in range(k):
if cnt[v + i] < t:
ok = False
break
cnt[v + i] -= t
if not ok:
break
print("YES" if ok else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
TreeMap<Long, Integer> cnt = new TreeMap<>();
for (int i = 0; i < n; i++) cnt.merge(sc.nextLong(), 1, Integer::sum);
if (n % k != 0) {
System.out.println("NO");
return;
}
for (long v : new ArrayList<>(cnt.keySet())) {
int t = cnt.get(v);
if (t == 0) continue;
for (int i = 0; i < k; i++) {
Integer c = cnt.get(v + i);
if (c == null || c < t) {
System.out.println("NO");
return;
}
cnt.put(v + i, c - t);
}
}
System.out.println("YES");
}
}