LeetCode 846 - Hand of Straights

https://leetcode.com/problems/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.

Note:

1. 1 <= hand.length <= 10000
2. 0 <= hand[i] <= 10^9
3. 1 <= W <= hand.length

X. Remainder
public boolean isNStraightHand(int[] hand, int W) { int remainder = hand.length % W; if(remainder != 0){ return false; }else{ int[] map = new int[W]; for(int card: hand){ map[card%W]++; } for(int i = 0; i<map.length -1; i++){ if(map[i] != map[i+1]){ return false; } } } return true; }

X. https://leetcode.com/problems/hand-of-straights/discuss/153519/copy-from-the-quickest-java-solutions-with-explanation(10-ms-Beats-100)

This idea is just so brilliant...
The key process is bucket the input array.
Assume the input is :

int[] hand = {1, 2, 3, 6, 2, 3, 4, 7, 8};
int W =3;

Step 1: bucket input array

//every column is a bucket,when current bucket full ,save hands value to next bucket

[3, 6, 3]
[1, 4, 7]
[2, 2, 8]

Step 2: sort each row

[3, 3, 6]
[1, 4, 7]
[2, 2, 8]

Step 3: test consecutive of each columns...

Note:
the first value may be min or max  of current bucket
also the last value may be min or max of current bucket

time complexity: O(N + W * HlogH + HW) = O(N + WHlogH) = O(N + NlogH) = O(NlogH)
N: number of cards in hand
W: group size
H: N / W

  public boolean isNStraightHand(int[] hands, int W) {

    if (W == 1)

      return true;

    if (hands.length % W != 0)

      return false;

    int H = hands.length / W;

    int[][] buckets = new int[W][H];

    int[] bucketSize = new int[W];

    for (int h : hands) {

      int indexInBucket = h % W, bucketId = bucketSize[indexInBucket]++;

      if (bucketId >= H)

        return false;

      buckets[indexInBucket][bucketId] = h;

    }

    for (int i = 0; i < W; i++)

      Arrays.sort(buckets[i]);

    for (int i = 0; i < H; i++)

      for (int j = 1; j < W; j++)

        // consider case 3,1,2 and 3,4,2

        if (buckets[j][i] != buckets[j - 1][i] + 1 && buckets[j - 1][i] - buckets[j][i] != W - 1)

          return false;

    return true;

  }

We will repeatedly try to form a group (of size W) starting with the lowest card. This works because the lowest card still in our hand must be the bottom end of a size W straight.

Algorithm

Let's keep a count {card: number of copies of card} as a TreeMap (or dict).

Then, repeatedly we will do the following steps: find the lowest value card that has 1 or more copies (say with value x), and try to remove x, x+1, x+2, ..., x+W-1 from our count. If we can't, then the task is impossible.

Time Complexity: $O(N * (N/W))$, where $N$ is the length of hand. The $(N / W)$ factor comes from min(count). In Java, the $(N / W)$ factor becomes $\log N$ due to the complexity of TreeMap.

  public boolean isNStraightHand(int[] hand, int W) {

    TreeMap<Integer, Integer> count = new TreeMap();

    for (int card : hand) {

      if (!count.containsKey(card))

        count.put(card, 1);

      else

        count.replace(card, count.get(card) + 1);

    }

    while (count.size() > 0) {

      int first = count.firstKey();

      for (int card = first; card < first + W; ++card) {

        if (!count.containsKey(card))

          return false;

        int c = count.get(card);

        if (c == 1)

          count.remove(card);

        else

          count.replace(card, c - 1);

      }

    }

    return true;

  }

https://leetcode.com/problems/hand-of-straights/discuss/135598/C%2B%2BJavaPython-O(MlogM)-Complexity

1. Count number of different cards to a map c
2. Loop from the smallest card number.
3. Everytime we meet a new card i, we cut off i - i + W - 1 from the counter.

Time Complexity:
O(MlogM + MW), where M is the number of different cards.

    public boolean isNStraightHand(int[] hand, int W) {
        Map<Integer, Integer> c = new TreeMap<>();
        for (int i : hand) c.put(i, c.getOrDefault(i, 0)+1);
        for (int it : c.keySet())
            if (c.get(it) > 0)
                for (int i = W - 1; i >= 0; --i) {
                    if (c.getOrDefault(it + i, 0) < c.get(it)) return false;
                    c.put(it + i, c.get(it + i) - c.get(it));
                }
        return true;
    }

X. Follow Up
We just got lucky AC solution. Because W <= 10000.
What if W is huge, should we cut off card on by one?

Explanation:

1. Count number of different cards to a map c
2. Cur represent current opened straight groups.
3. In a deque start, we record the number of opened a straight group.
4. Loop from the smallest card number.

For example, hand = [1,2,3,2,3,4], W = 3
We meet one 1:
opened = 0, we open a new straight groups starting at 1, push (1,1) to start.
We meet two 2:
opened = 1, we need open another straight groups starting at 1, push (2,1) to start.
We meet two 3:
opened = 2, it match openedrent open groups.
We open one group at 1, now we close it. opened = opened - 1 = 1
We meet one 4:
opened = 1, it match openedrent open groups.
We open one group at 2, now we close it. opened = opened - 1 = 0

5. return if no more open groups.

Time Complexity:
O(MlogM), where M is the number of different cards.

    public boolean isNStraightHand(int[] hand, int W) {
        Map<Integer, Integer> c = new TreeMap<>();
        for (int i : hand) c.put(i, c.getOrDefault(i, 0)+1);
        Queue<Integer> start = new LinkedList<>();
        int last_checked = -1, opened = 0;
        for (int i : c.keySet()) {
            if (opened > 0 && i > last_checked + 1 || opened > c.get(i)) return false;
            start.add(c.get(i) - opened);
            last_checked = i; opened = c.get(i);
            if (start.size() == W) opened -= start.remove();
        }
        return opened == 0;
    }

X. https://www.cnblogs.com/okokabcd/p/9444195.html

public boolean isNStraightHand(int[] hand, int W) {
    List<Integer> nums = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>(); // num, count
    for (int tmp : hand) {
        Integer count = map.get(tmp);
        if (count == null) {
            count = 0;
            nums.add(tmp);
        }
        map.put(tmp, count+1);
    }

    Collections.sort(nums); // sort

    int i=0;
    while (i < nums.size()) {
        int tmp = nums.get(i);
        int offset = 0;
        while (offset < W) {
            Integer count = map.get(tmp + offset);
            if (count == null || count < 1) return false;
            map.put(tmp + offset, count-1);
            offset++;
        }
        while (i < nums.size() && map.get(nums.get(i)) == 0) i++;
    }

    return true;
}

// no need to use i

  public boolean isNStraightHand(int[] hand, int W) {

    if (hand.length % W != 0)

      return false;

    Map<Integer, Long> counts = new TreeMap<>(

        Arrays.stream(hand).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting())));

    for (int i = hand.length / W; i > 0; i--) { // not i>=0

      if (!straight(counts, W)) {

        return false;

      }

    }

    return true;

  }

  private boolean straight(Map<Integer, Long> counts, int W) {

    Iterator<Entry<Integer, Long>> it = counts.entrySet().iterator();

    int prev = -1;

    while (it.hasNext() && W > 0) {

      --W; // state change

      Entry<Integer, Long> entry = it.next();

      if (prev != -1) {

        if (entry.getKey() != prev + 1) {

          return false;

        }

      }

      prev = entry.getKey();

      if (entry.getValue() == 1) {

        it.remove();

      } else {

        entry.setValue(entry.getValue() - 1);

      }

    }

    return W == 0;

  }

https://leetcode.com/problems/hand-of-straights/discuss/136200/Simple-Java-solution-using-priority-queue
- PriorityQueue.remove O(n)