Split Array into Consecutive Subsequences

In Doudizhu, cards with consecutive ranks can form straights. Sometimes splitting pairs to combine with single cards allows forming more straights, potentially increasing winning chances.

How can we optimally split cards to form straights? Let's explore an interesting algorithm problem: consecutive subsequence partition.

This is LeetCode problem 659 "Split Array into Consecutive Subsequences":

Given a sorted array nums in ascending order (possibly containing duplicates), determine whether it can be partitioned into subsequences where each subsequence:

• Has length ≥ 3
• Consists of consecutive integers

Function signature:

boolean isPossible(int[] nums);

bool isPossible(vector<int>& nums);

def isPossible(nums: List[int]) -> bool:

func isPossible(nums []int) bool

var isPossible = function(nums) {}

For example, consider the given input nums = [1,2,3,3,4,4,5,5]. The algorithm returns true.

This is because nums can be split into two subsequences of consecutive integers: [1,2,3,4,5] and [3,4,5].

However, if the input is nums = [1,2,3,4,4,5], the algorithm returns false, as it cannot be split into two subsequences of at least length 3 with consecutive integers.

For problems involving consecutive integers, sorting should be your first instinct. But in this case, the problem states that the input nums is already sorted.

So, how do we determine if nums can be divided into several subsequences that meet the criteria?

Similar to the previous article on Backtracking for Set Partitioning, we want to partition the elements of nums into several subsequences. The logic can be represented by the following code:

for (int v : nums) {
    if (...) {
        // assign v to a subsequence
    } else {
        // really cannot assign v
        return false;
    }
    return true;
}

The key question is, how do we determine how to allocate the current element v?

We need to discuss different scenarios. Once we clarify these scenarios, the problem can be solved.

There are two main scenarios:

1. The current element v forms its own group, starting a sequence with a length of at least 3.

For example, given nums = [1,2,3,6,7,8], when we reach the element 6, it can only start its own valid subsequence [6,7,8].

2. The current element v is appended to an existing subsequence.

For example, given nums = [1,2,3,4,5], when we reach the element 4, it can only be appended to the existing subsequence [1,2,3]. It cannot start a new subsequence because there is no 6.

But what if both scenarios are possible? How do we choose?

For instance, given nums = [1,2,3,4,5,5,6,7], for the element 4, should it start a new subsequence [4,5,6] or be appended to the subsequence [1,2,3]?

Clearly, the correct way to split the nums array is into [1,2,3,4,5] and [5,6,7], so the element 4 should first check if it can be appended to another sequence. If not, then check if it can start a new subsequence.

This is the overall approach. To implement these choices in the algorithm, we need two hash tables for assistance:

• The freq hash table helps an element determine if it can start a new sequence.
• The need hash table helps an element determine if it can be appended to an existing sequence.

freq records the frequency of each element, for example, freq[3] == 2 means the element 3 appears twice in nums.

If we find that freq[3], freq[4], freq[5] are all greater than 0, it means element 3 can start a sequence of length 3.

need records which elements can be appended to existing subsequences.

For example, if we already have two subsequences [1,2,3,4] and [2,3,4], then need[5] should be 2, indicating that there is a demand for two 5s.

Understanding the roles of these two hash tables allows us to comprehend the solution:

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();

        // count the frequency of elements in nums
        for (int v : nums) {
            freq.put(v, freq.getOrDefault(v, 0) + 1);
        }

        for (int v : nums) {
            if (freq.get(v) == 0) {
                // already used in other subsequences
                continue;
            }

            // first determine if v can be appended to the end of other subsequences
            if (need.containsKey(v) && need.get(v) > 0) {
                // v can be appended to the end of a previous subsequence
                freq.put(v, freq.get(v) - 1);
                // decrease the need for v by one
                need.put(v, need.get(v) - 1);
                // increase the need for v + 1 by one
                need.put(v + 1, need.getOrDefault(v + 1, 0) + 1);
            } else if (freq.getOrDefault(v, 0) > 0 && 
                       freq.getOrDefault(v + 1, 0) > 0 && 
                       freq.getOrDefault(v + 2, 0) > 0) {
                // create a new subsequence of length 3 starting with v: [v, v+1, v+2]
                freq.put(v, freq.get(v) - 1);
                freq.put(v + 1, freq.get(v + 1) - 1);
                freq.put(v + 2, freq.get(v + 2) - 1);
                // increase the need for v + 3 by one
                need.put(v + 3, need.getOrDefault(v + 3, 0) + 1);
            } else {
                // if neither of the two conditions is met, it cannot be allocated
                return false;
            }
        }

        return true;
    }
}

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> freq;
        unordered_map<int, int> need;

        // count the frequency of elements in nums
        for (int v : nums) {
            ++freq[v];
        }

        for (int v : nums) {
            if (freq[v] == 0) {
                // already used in other subsequences
                continue;
            }

            // first determine if v can be appended to other subsequences
            if (need.count(v) && need[v] > 0) {
                // v can be appended to a previous subsequence
                freq[v] = freq[v] - 1;
                // decrease the need for v by one
                need[v] = need[v] - 1;
                // increase the need for v + 1 by one
                need[v + 1] = need[v + 1] + 1;
            } else if (freq[v] > 0 && 
                       freq[v + 1] > 0 && 
                       freq[v + 2] > 0) {
                // create a new subsequence of length 3 starting with v: [v, v+1, v+2]
                freq[v] = freq[v] - 1;
                freq[v + 1] = freq[v + 1] - 1;
                freq[v + 2] = freq[v + 2] - 1;
                // increase the need for v + 3 by one
                need[v + 3] = need[v + 3] + 1;
            } else {
                // if neither condition is met, it cannot be allocated
                return false;
            }
        }

        return true;
    }
};

class Solution:
    def isPossible(self, nums):
        freq = {}
        need = {}

        # count the frequency of elements in nums
        for v in nums:
            freq[v] = freq.get(v, 0) + 1

        for v in nums:
            if freq.get(v) == 0:
                # already used in other subsequences
                continue

            # first determine if v can be appended to other subsequences
            if v in need and need[v] > 0:
                # v can be appended to a previous subsequence
                freq[v] = freq.get(v) - 1
                # decrease the need for v by one
                need[v] = need.get(v) - 1
                # increase the need for v + 1 by one
                need[v + 1] = need.get(v + 1, 0) + 1
            elif freq.get(v, 0) > 0 and \
                 freq.get(v + 1, 0) > 0 and \
                 freq.get(v + 2, 0) > 0:
                # create a new subsequence of length 3 starting with v: [v, v+1, v+2]
                freq[v] = freq[v] - 1
                freq[v + 1] = freq[v + 1] - 1
                freq[v + 2] = freq[v + 2] - 1
                # increase the need for v + 3 by one
                need[v + 3] = need.get(v + 3, 0) + 1
            else:
                # if neither condition is met, it cannot be allocated
                return False
        return True

func isPossible(nums []int) bool {
    freq := make(map[int]int)
    need := make(map[int]int)

    // count the frequency of elements in nums
    for _, v := range nums {
        freq[v]++
    }

    for _, v := range nums {
        if freq[v] == 0 {
            // already used in other subsequences
            continue
        }

        // first determine if v can be appended to other subsequences
        if need[v] > 0 {
            // v can be appended to a previous subsequence
            freq[v]--
            // decrease the need for v by one
            need[v]--
            // increase the need for v + 1 by one
            need[v+1]++
        } else if freq[v] > 0 && 
                  freq[v+1] > 0 && 
                  freq[v+2] > 0 {
            // create a new subsequence of length 3 starting with v: [v, v+1, v+2]
            freq[v]--
            freq[v+1]--
            freq[v+2]--
            // increase the need for v + 3 by one
            need[v+3]++
        } else {
            // if neither condition is met, it cannot be allocated
            return false
        }
    }

    return true
}

var isPossible = function(nums) {
   
    var freq = new Map();
    var need = new Map();

    // count the frequency of elements in nums
    for (let v of nums) {
        freq.set(v, (freq.get(v) || 0) + 1);
    }

    for (let v of nums) {
        if (freq.get(v) == 0) {
            // already used in other subsequences
            continue;
        }

        // first determine if v can be appended to other subsequences
        if (need.has(v) && need.get(v) > 0) {
            // v can be appended to a previous subsequence
            freq.set(v, freq.get(v) - 1);
            // decrease the need for v by one
            need.set(v, need.get(v) - 1);
            // increase the need for v + 1 by one
            need.set(v + 1, (need.get(v + 1) || 0) + 1);
        } else if ((freq.get(v) || 0) > 0 && 
                   (freq.get(v + 1) || 0) > 0 && 
                   (freq.get(v + 2) || 0) > 0) {
            // create a new subsequence of length 3 starting with v: [v, v+1, v+2]
            freq.set(v, freq.get(v) - 1);
            freq.set(v + 1, freq.get(v + 1) - 1);
            freq.set(v + 2, freq.get(v + 2) - 1);
            // increase the need for v + 3 by one
            need.set(v + 3, (need.get(v + 3) || 0) + 1);
        } else {
            // if neither condition is met, it cannot be allocated
            return false;
        }
    }

    return true;
};

So far, we have solved this problem.

You might be wondering, in the card game Dou Di Zhu, a straight requires at least 5 consecutive cards, but in our problem, we only calculate subsequences with a minimum length of 3. How do we handle this?

It's simple. Just modify our else if branch to check for 5 consecutive elements after v.

Now, let's challenge ourselves further. What if I don't just want a boolean value? What if I want you to print out all the subsequences? How do we do that?

Actually, this is also easy to implement. Just modify need to not only record the required count for an element but also record which specific subsequences generate these requirements:

// need[6] = 2 means there are two subsequences that need 6
Map<Integer, Integer> need = new HashMap<>();

// need[6] = {
//     {3,4,5},
//     {2,3,4,5},
// }
// record which two subsequences need 6
Map<Integer, List<List<Integer>>> need = new HashMap<>();

// need[6] = 2 means there are two subsequences that need 6
unordered_map<int, int> need;

// need[6] = {
//     {3,4,5},
//     {2,3,4,5},
// }
// record which two subsequences need 6
unordered_map<int, vector<vector<int>>> need;

# need[6] = 2 means there are two subsequences that need 6
need = {}

# record which two subsequences need 6
need_sequences = {}

// need[6] = 2 means there are two subsequences that require 6
need := make(map[int]int)

// need[6] = {
//     {3,4,5},
//     {2,3,4,5},
// }
// record which two subsequences require 6
need := make(map[int][][]int)

// need[6] = 2 means there are two subsequences that need 6
var need = {};

// need[6] = {
//     {3,4,5},
//     {2,3,4,5},
// }
// record which two subsequences need 6
var needTwoSubsequences = {};

This way, we just need to slightly modify the previous code:

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, List<List<Integer>>> need = new HashMap<>();

        // count the frequency of elements in nums
        for (int v : nums) {
            freq.put(v, freq.getOrDefault(v, 0) + 1);
        }

        for (int v : nums) {
            if (freq.get(v) == 0) {
                continue;
            }

            if (need.containsKey(v) && need.get(v).size() > 0) {
                // v can be appended to a previous sequence
                freq.put(v, freq.get(v) - 1);
                // take any subsequence that needs v
                List<Integer> seq = need.get(v).remove(need.get(v).size() - 1);
                // append v to this subsequence
                seq.add(v);
                // the requirement of this subsequence becomes v + 1
                need.computeIfAbsent(v + 1, k -> new ArrayList<>()).add(seq);
            } else if (freq.getOrDefault(v, 0) > 0 && 
                       freq.getOrDefault(v + 1, 0) > 0 && 
                       freq.getOrDefault(v + 2, 0) > 0) {
                // v can be used as the start
                freq.put(v, freq.get(v) - 1);
                freq.put(v + 1, freq.get(v + 1) - 1);
                freq.put(v + 2, freq.get(v + 2) - 1);
                // create a subsequence of length 3 [v, v + 1, v + 2]
                List<Integer> seq = new ArrayList<>(Arrays.asList(v, v + 1, v + 2));
                // increment the need for v + 3 by one
                need.computeIfAbsent(v + 3, k -> new ArrayList<>()).add(seq);
            } else {
                return false;
            }
        }

        // print all the subsequences that have been split out
        for (Map.Entry<Integer, List<List<Integer>>> entry : need.entrySet()) {
            for (List<Integer> seq : entry.getValue()) {
                for (int val : seq) {
                    System.out.print(val + " ");
                }
                System.out.println();
            }
        }

        return true;
    }
}

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> freq;
        unordered_map<int, vector<vector<int>>> need;

        // count the frequency of elements in nums
        for (int v : nums) {
            freq[v] = freq[v] + 1;
        }

        for (int v : nums) {
            if (freq[v] == 0) {
                continue;
            }

            if (need.count(v) && need[v].size() > 0) {
                // v can be appended to a previous sequence
                freq[v] = freq[v] - 1;
                // take any subsequence that needs v
                vector<int> seq = need[v].back();
                need[v].pop_back();
                // append v to this subsequence
                seq.push_back(v);
                // the requirement of this subsequence becomes v + 1
                need[v + 1].push_back(seq);
            } else if (freq.count(v) > 0 && 
                       freq.count(v + 1) > 0 && 
                       freq.count(v + 2) > 0) {
                // v can be used as the start
                freq[v] = freq[v] - 1;
                freq[v + 1] = freq[v + 1] - 1;
                freq[v + 2] = freq[v + 2] - 1;
                // create a subsequence of length 3 [v, v + 1, v + 2]
                vector<int> seq = {v, v + 1, v + 2};
                // increase the need for v + 3 by one
                need[v + 3].push_back(seq);
            } else {
                return false;
            }
        }

        // print all the subsequences that have been split out
        for (auto& entry : need) {
            for (vector<int>& seq : entry.second) {
                for (int val : seq) {
                    cout << val << " ";
                }
                cout << endl;
            }
        }

        return true;
    }
};

class Solution:
    def isPossible(self, nums):
        freq = collections.Counter(nums)
        need = collections.defaultdict(list)

        # count the frequency of elements in nums
        for v in nums:
            if freq[v] == 0:
                continue

            if need[v]:
                # v can be appended to a previous sequence
                freq[v] -= 1
                # take any subsequence that needs v
                seq = need[v].pop()
                # append v to this subsequence
                seq.append(v)
                # the requirement of this subsequence becomes v + 1
                need[v + 1].append(seq)
            elif freq[v] > 0 and freq[v + 1] > 0 and freq[v + 2] > 0:
                # can use v as the start
                freq[v] -= 1
                freq[v + 1] -= 1
                freq[v + 2] -= 1
                # create a subsequence of length 3 [v, v + 1, v + 2]
                seq = [v, v+1, v+2]
                # increase the need for v + 3 by one
                need[v + 3].append(seq)
            else:
                return False

        # print all the subsequences that have been split out
        for v, seqs in need.items():
            for seq in seqs:
                print(' '.join(map(str, seq)))

        return True

func isPossible(nums []int) bool {
    freq := map[int]int{}
    need := map[int][][]int{}

    // count the frequency of elements in nums
    for _, v := range nums {
        freq[v] = freq[v] + 1
    }

    for _, v := range nums {
        if freq[v] == 0 {
            continue
        }
        seqs, ok := need[v]
        if ok && len(seqs) > 0 {
            // v can be appended to a previous sequence
            freq[v] = freq[v] - 1
            // pick any subsequence that needs v
            seq := need[v][len(need[v])-1]
            need[v] = need[v][:len(need[v])-1]
            // append v to this subsequence
            seq = append(seq, v)
            // the requirement of this subsequence becomes v + 1
            need[v+1] = append(need[v+1], seq)
        } else if freq[v] > 0 && freq[v+1] > 0 && freq[v+2] > 0 {
            // v can be used as the beginning
            freq[v] = freq[v] - 1
            freq[v+1] = freq[v+1] - 1
            freq[v+2] = freq[v+2] - 1
            // create a subsequence of length 3 [v, v + 1, v + 2]
            seq := []int{v, v + 1, v + 2}
            // increment the need for v + 3
            need[v+3] = append(need[v+3], seq)
        } else {
            return false
        }
    }

    // print all subsequences that have been split out
    for _, seqs := range need {
        for _, seq := range seqs {
            for _, val := range seq {
                fmt.Print(val, " ")
            }
            fmt.Println()
        }
    }

    return true
}

var isPossible = function(nums) {
    let freq = new Map();
    let need = new Map();
  
    // count the frequency of elements in nums
    for (let v of nums) {
        freq.set(v, (freq.get(v) || 0) + 1);
    }

    for (let v of nums) {
        if (freq.get(v) === 0) {
            continue;
        }

        if (need.has(v) && need.get(v).length > 0) {
            // v can be appended to a previous sequence
            freq.set(v, freq.get(v) - 1);
            
            // take any subsequence that needs v
            let seq = need.get(v).pop();
            // append v to this subsequence
            seq.push(v);
            
            // the requirement of this subsequence becomes v + 1
            need.has(v + 1) || need.set(v + 1, []);
            need.get(v + 1).push(seq);
        } else if ((freq.get(v) || 0) > 0 && 
            (freq.get(v + 1) || 0) > 0 && 
            (freq.get(v + 2) || 0) > 0) {
            // v can be used as the start
            freq.set(v, freq.get(v) - 1);
            freq.set(v + 1, freq.get(v + 1) - 1);
            freq.set(v + 2, freq.get(v + 2) - 1);
            
            // create a new subsequence of length 3 [v, v + 1, v + 2]
            let seq = [v, v + 1, v + 2];
            
            // increase the need for v + 3 by one
            need.has(v + 3) || need.set(v + 3, []);
            need.get(v + 3).push(seq);
        } else {
            return false;
        }
    }

    // print all the subsequences that have been split out
    for (let [key, value] of need.entries()) {
        for (let seq of value) {
            for (let val of seq) {
                console.log(val + " ");
            }
            console.log('\n');
        }
    }

    return true;
};

This way, we have also achieved the need to record specific subsequences.

If this article was helpful to you, give it a thumbs up, and WeChat will recommend more similar articles to you.