Skip to main content

Split Array into Consecutive Subsequences

labuladongOriginalAbout 3129 words

659. 分割数组为连续子序列 https://leetcode.cn/problems/split-array-into-consecutive-subsequences

659. Split Array into Consecutive Subsequences https://leetcode.com/problems/split-array-into-consecutive-subsequences

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCodeDifficulty
659. Split Array into Consecutive Subsequences🟠

In the card game Dou Di Zhu, consecutive cards can be used as a straight. Sometimes, by breaking pairs and combining them with single cards, we can form more straights, which might increase our chances of winning.

So, how can we reasonably break up the cards in our hand to form straights? Today, we'll look at a very interesting algorithm problem: the partitioning of consecutive subsequences.

This is LeetCode problem #659, "Split Array into Consecutive Subsequences." The problem is straightforward:

You are given an ascendingly sorted array nums (which may contain duplicate numbers). Your task is to determine if nums can be split into several subsequences, each of which has a length of at least 3 and consists of consecutive integers.

The function signature is as follows:

java 🟢
boolean isPossible(int[] 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:

java 🟢
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;
    }
}

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:

java 🟢
// 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<>();

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

java 🟢
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;
    }
}

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.

Last update: 11/6/2024, 3:43:27 PM
© 2019 - 2024 labuladong