Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. If n is not divisible by k, the answer is NO immediately.
  2. 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");
    }
}

Solve Hand of Straights online · All practice problems