Hand of Straights medium

Problem Statement

You are given an integer array hand containing cards, where hand[i] is the value of the i-th card. You are also given an integer groupSize. You want to arrange the cards into groups, such that each group contains groupSize consecutive cards.

Return true if and only if you can arrange the cards in groups, or false otherwise.

Example 1

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: One possible arrangement is: [1,2,3] [2,3,4] [6,7,8]

Example 2

Input: hand = [1,2,3,4,5], groupSize = 4 Output: false Explanation: You cannot arrange the cards into groups of 4.

Steps

1. Count Card Frequencies: Create a frequency map (HashMap) to count the occurrences of each card value in the hand.

2. Iterate and Check: Iterate through the card values in ascending order. For each card value:

   • Check if it's present in the frequency map (with a count > 0).
   • If it is, form a group. This means decrementing the count of the current card and the next groupSize - 1 consecutive cards. If any of the consecutive cards are missing (count is 0), we cannot form a group, so return false.
   • Continue this process until all cards are processed or a group cannot be formed.

3. Return Result: If all cards are processed successfully (all counts in the frequency map become 0), return true. Otherwise, return false.

Explanation

The solution utilizes a frequency map to efficiently track the number of times each card appears. The iterative approach ensures that we attempt to create groups sequentially. The key is to check for the availability of consecutive cards needed for a group; if any are missing, the arrangement is impossible.

Code

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false; // Impossible to form groups

        Map<Integer, Integer> count = new HashMap<>();
        for (int card : hand) {
            count.put(card, count.getOrDefault(card, 0) + 1);
        }

        for (int i = Integer.MIN_VALUE; ; ++i) { //Iterate through all possible card values
          if (count.getOrDefault(i, 0) > 0){
            for(int j = i; j < i + groupSize; ++j){
                if(count.getOrDefault(j,0) == 0) return false;
                count.put(j, count.get(j) - 1);
                if(count.get(j) == 0) count.remove(j); //Remove from map if count is 0 for better efficiency
            }
          }
          if(count.isEmpty()) return true; //All cards processed successfully
        }
    }
}

Complexity

• Time Complexity: O(N log N), where N is the length of the hand array. The dominant operation is iterating through the HashMap (which is at most the size of the hand). While HashMap provides O(1) average-case get and put operations, in the worst case (e.g., all cards are unique), the implicit sorting implied by the for (int i = Integer.MIN_VALUE; ++i) loop necessitates the O(N log N) time if we consider the sorting. If we assume cards are already roughly sorted, then the complexity would be O(N).

• Space Complexity: O(N) in the worst case, to store the frequency map (HashMap). In the best case where many card values repeat, this could be less than O(N).