Hand of Straights

Medium🏃 GreedyArrayHash TableGreedySorting

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the i^th card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 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], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

Constraints:

1 <= hand.length <= 10⁴
0 <= hand[i] <= 10⁹
1 <= groupSize <= hand.length

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

Pattern Recognition & Intuition

Why this is a Greedy problem

🏃

Greedy

Always pick the locally optimal choice — and prove it works globally.

A greedy algorithm makes the best-looking choice at each step without reconsidering past decisions. It works when the "greedy choice property" holds: local optima lead to global optimum. The hard part isn't the code — it's proving (or recognizing) when greedy is valid.

MENTAL MODEL

Sort by the right criterion, then make the greedy choice. Prove correctness by exchange argument: "swapping the greedy choice for any other choice can only make things worse or equal."

INTUITION

For "Jump Game": at each position, greedily track the farthest index you can reach. You don't need to try all paths — if the max reachable index ever covers position i, you can be there. Greedy works because reaching farther is always at least as good as reaching less far.

SIGNALS — WHEN TO USE THIS PATTERN

"Jump game", "jump game II" — track max reachable index
"Gas station" — circular greedy: if total gas >= total cost, a solution exists
"Meeting rooms", "interval scheduling" — sort by end time, greedily pick non-overlapping
"Task scheduler" — frequency-based greedy
"Minimum number of arrows", "partition labels" — interval greedy

Approaches & Trade-offs

From brute force to optimal — understand every step of the journey

BRUTE FORCE

Brute Force

⏱ O(2ⁿ) without memo; O(n²) with DP💾 O(n) recursion

✦ OPTIMAL

Optimal

⏱ O(n) single pass💾 O(1)

Make the locally optimal choice at each step. For jump game: track max reachable, count jumps only when you cross a boundary.

ALGORITHM STEPS

Initialize max_reach = 0, jumps = 0, curr_boundary = 0
For each index i from 0 to n-2: update max_reach = max(max_reach, i + nums[i])
When i == curr_boundary: we must jump here, jumps++, curr_boundary = max_reach
If curr_boundary >= n-1 at any point: done

TIME

O(n) single pass

SPACE

O(1)

The greedy key: within the current "zone" [prev_boundary+1 .. curr_boundary], always extend as far as possible.

def jump(nums):
    jumps = max_reach = curr_end = 0
    for i in range(len(nums) - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == curr_end:          # must jump here
            jumps += 1
            curr_end = max_reach
    return jumps

Key Insight & Common Pitfalls

THE "AHA" MOMENT

Greedy algorithms are "obviously correct" once you see the right exchange argument. For interval scheduling: if you pick the interval that ends latest first, you can always swap it for the one ending soonest — and the count can only stay the same or improve. That's the exchange argument. If you can't construct this argument, greedy probably doesn't work and you need DP.

COMMON MISTAKES

✕Assuming greedy works without proof — test against counter-examples (coin change with non-standard denominations fails greedy)
✕Wrong sort criterion: for interval scheduling, sort by END time (not start, not length)
✕"Gas station": if total gas >= total cost, a solution definitely exists — start from where the running total hits a new minimum
✕Off-by-one: jump game loops to len(nums)-1 (not n), because you don't need a jump FROM the last position

PRO TIPS

›Exchange argument template: "Suppose we pick X instead of the greedy choice Y. Swapping X for Y gives result R' ≥ R."
›"Assign cookies": sort both, use two pointers — greedily match smallest sufficient cookie to each child
›"Lemonade change": greedily give largest bills first to preserve flexibility for larger change
›If stuck between greedy and DP: try greedy on small examples, check if it ever makes the wrong choice

Interactive Visualizer

Building 🏃 Greedy Visualization

Generating visualization…