Reference: LeetCode
Difficulty: Medium

My Post: All-In-One Java Solution (Map + PQ & Two Maps) with Explanation, Examples, and Comments

Problem

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Note: The length of the input is in range of [1, 10000].

Example: 

1
2
3
4
5
6
Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences:
1, 2, 3
3, 4, 5
1
2
3
4
5
6
Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences:
1, 2, 3, 4, 5
3, 4, 5

Analysis

Map + PriorityQueue

Reference:

We use a HashMap<Integer, PriorityQueue<Integer>> to store the information we need to process the list. For current number val, we compare its value to its predecessor to see if their difference is $1$.

By map.get(val), we have a priority queue, which stores all available lengths of sequence ending with value val. The reason why we use a priority queue is that when we encounter a new value val, we want to append it to the shortest sequence that needs most “help”. We want all sequences we have to satisfy the requirement >= k. For example, [1, 2, 3] and [2, 3]: The next value is 4, we will add it to [2, 3] and it becomes [2, 3, 4] rather than adding it to [1, 2, 3]. This is the idea of greedy algorithm, since we always go for the shortest length of sequence at each step.

Algorithm:

  • For each current value val:
    • If val - 1 exists in the map, we get the priority queue by map.get(val - 1) and poll the shortest sequence’s length and offer it into the priority queue in map.get(val).
    • If val - 1 does not exists in the map, or its priority queue is empty, we start over from this element and offer 1 into the val‘s priority queue.
  • Finally, we iterate the map’s values, and poll each sequence’s length by pq.poll() and check if all of then satisfy the requirement.

For example, we have a sequence [1, 2, 3, 3, 4, 4, 5, 5]:

1
2
3
4
5
6
7
8
9
val   map                                             case
1     <1, [1]>                                        not exist
2     <2, [2]>, <1, []>                               exist
3     <3, [3]>, <2, []>, <1, []>                      exist
3     <3, [3, 1]>, <2, []>, <1, []>                   exist but no more length
4     <4, [2]>, <3, [3]>, <2, []>, <1, []>            exist
4     <4, [2, 4]>, <3, []>, <2, []>, <1, []>          exist
5     <5, [3]>, <4, [4]>, <3, []>, <2, []>, <1, []>   exist (remember! shortest length)
5     <5, [3, 5]>, <4, []>, <3, []>, <2, []>, <1, []> exist

Code with comments:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public boolean isPossible(int[] nums) {
  // Build map <num, minPQ of length>
  Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
  
  for (int val : nums) {
    if (map.containsKey(val - 1) && map.get(val - 1).size() > 0) { // minPQ size > 0
      // (num - 1) sequence exists
      PriorityQueue<Integer> pq = map.get(val - 1);
      int len = pq.poll();
      if (map.get(val) == null) {
        map.put(val, new PriorityQueue<>());
      }
      map.get(val).add(len + 1);
    } else {
      // (num - 1) sequence does not exist
      if (map.get(val) == null) {
        map.put(val, new PriorityQueue<>());
      }
      map.get(val).add(1);
    }
  }
  
  // Check each non-empty priority queue
  for (PriorityQueue<Integer> pq : map.values()) {
    while (pq.size() > 0) {
      if (pq.poll() < 3) {
        return false;
      }
    }
  }
  
  return true;
}

Time: $O(N\log{N})$
Space: $O(N)$

Two Maps

Reference: Java O(n) Time O(n) Space

Thanks marcohwlam for the example that many post writers don’t even add to their posts. Not mention the code without comments. Drives me crazy!

Note: I still don’t know why it works though, but at least I now know how it works.

This time, we have two hash maps: freqMap and subMap.

  • freqMap: Count the frequency of all numbers.
  • subMap: Store qualified (>= 3) subsequences. It is not obvious though.
    • For example, <4, 1> means we have already one qualified subsequence (e.g. [1, 2, 3]) and it will continue from 4. Then later when we encounter a value 4, we can append 4 to the current subsequence and update the map to <4, 0>, <5, 1>.

Algorithm:

  • Iterate through the array to get the frequency of all the elements.
  • Iterate through the array once more to see:
    • Case 1: If val‘s frequency is used up? Yes => continue; to the next val.
    • Case 2: If each element can be appended to a previously constructed consecutive subsequence.
    • Case 3: If it can be the start of a new consecutive sequence.
    • Case 4: Returns false.
    • Remember to decrement the frequency of val in freqMap at each time.

For example, we have a sequence [1, 2, 3, 3, 4, 4, 5, 5]:

1
2
3
4
5
6
7
8
9
10
11
Init: freqMap = <1, 1>, <2, 1>, <3, 2>, <4, 2>, <5, 2>
val   case     subMap                   freqMap
1     3        <4, 1>                   <1, 0>, <2, 0>, <3, 1>, <4, 2>, <5, 2>
2     1        continue;
3     3        <4, 1>, <6, 1>           <1, 0>, <2, 0>, <3, 0>, <4, 1>, <5, 1>
3     1        continue;
4     2        <4, 0>, <5, 1>, <6, 1>   <1, 0>, <2, 0>, <3, 0>, <4, 0>, <5, 1>
4     1        continue;
5     3        <4, 0>, <5, 0>, <6, 2>   <1, 0>, <2, 0>, <3, 0>, <4, 0>, <5, 0>
5     1        continue;
return true;

Code with comments:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public boolean isPossible(int[] nums) {
  Map<Integer, Integer> freqMap = new HashMap<>();
  Map<Integer, Integer> subMap = new HashMap<>();

  // Count the frequency
  for (int val : nums) {
    freqMap.put(val, freqMap.getOrDefault(val, 0) + 1);
  }

  // Scan the nums
  for (int val : nums) {
    // Case 1 - "No available frequency"
    if (freqMap.get(val) == 0) { // No more frequencies. It has been used up.
      continue;
    }
    // Case 2 - "If val is where a subsequence in subMap could continue from"
    else if (subMap.getOrDefault(val, 0) > 0) {
      subMap.put(val, subMap.get(val) - 1); // use this subsequence from this val
      subMap.put(val + 1, subMap.getOrDefault(val + 1, 0) + 1); // append val + 1, update the subsequence continuing from val + 1.
    }
    // Case 3 - "Start of a new subsequence, 3 consecutive numbers"
    else if (freqMap.getOrDefault(val + 1, 0) > 0 && freqMap.getOrDefault(val + 2, 0) > 0) { // Check if we still have frequencies
      freqMap.put(val + 1, freqMap.get(val + 1) - 1); // use: val + 1
      freqMap.put(val + 2, freqMap.get(val + 2) - 1); // use: val + 2
      subMap.put(val + 3, subMap.getOrDefault(val + 3, 0) + 1); // We have one more subsequence continuing from val + 3
    }
    // Case 4
    else {
      return false;
    }
    freqMap.put(val, freqMap.get(val) - 1); // frequency of val--
  }
  return true;
}

Time: $O(N)$
Space: $O(N)$

Extra

$O(1)$ space:

Java O(n) time & O(1) space solution – greedily extending shorter subsequence

The original code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isPossible(int[] nums) {
  int pre = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;
  int cur = 0, cnt = 0, c1 = 0, c2 = 0, c3 = 0;
      
  for (int i = 0; i < nums.length; pre = cur, p1 = c1, p2 = c2, p3 = c3) {
      for (cur = nums[i], cnt = 0; i < nums.length && cur == nums[i]; cnt++, i++);
          
      if (cur != pre + 1) {
          if (p1 != 0 || p2 != 0) return false;
          c1 = cnt; c2 = 0; c3 = 0;
          
      } else {
          if (cnt < p1 + p2) return false;
          c1 = Math.max(0, cnt - (p1 + p2 + p3));
          c2 = p1;
          c3 = p2 + Math.min(p3, cnt - (p1 + p2));
      }
  }
  
  return (p1 == 0 && p2 == 0);
}