Hand of Straights

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

 


Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].
Example 2:

Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.
 

Constraints:

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/


Solution1:

class Solution {
    public boolean isNStraightHand(int[] hand, int W) {
        if (hand.length % W != 0) return false;
        if (W == 1) return true;
        List<Integer> hands = new ArrayList();
        for (int val : hand) hands.add(val);
        Collections.sort(hands);
        return helper(hands, W);
    }
    
    private boolean helper(List<Integer> hands, int W) {
        // System.out.println(hands);
        int n = hands.size();
        if (n == 0) return true;
        if (n % W != 0) return false;
        if (W == 1) return true;
        int k = 1;
        Iterator<Integer> iter = hands.iterator();
        int smallest = iter.next();
        iter.remove();
        while (iter.hasNext() && k < W) {
            if (iter.next() == smallest + k) {
                k ++;
                iter.remove();
            }
        }
        if (k == W) {
            return helper(hands, W);
        }
        return false;
    }
}

Solution2:

class Solution {
    public boolean isNStraightHand(int[] hand, int W) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i : hand){
            minHeap.add(i);
        }
        while(minHeap.size() != 0) {
            int start = minHeap.poll();
            for(int j = 1; j < W; j++){
                if(minHeap.remove(start + j)) {
                    continue;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }
}