Split Array into Consecutive Subsequences Solution in Java

Problem Description

Ah, the classic “Split Array into Consecutive Subsequences” problem! It’s like trying to organize a party where everyone insists on arriving in a sequence. Imagine you have a bunch of friends (or numbers, in this case) who can only form a line if they are consecutive. If your friend Bob shows up with a 1, he can only stand next to Alice with a 2 and Charlie with a 3. But if Dave shows up with a 5, he’s just going to have to wait until someone brings a 4.

The challenge here is to determine if you can split an array of integers into one or more subsequences such that each subsequence consists of consecutive integers. If you can’t, well, it’s time to break out the ice cream and binge-watch your favorite show instead.

Code Solution


class Solution {
  public boolean isPossible(int[] nums) {
    Map count = new HashMap<>();
    List starts = new ArrayList<>(); // the start indices of each subsequence
    List ends = new ArrayList<>();   // the end indices of each subsequence

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    for (int i = 0; i < nums.length; ++i) {
      if (i > 0 && nums[i] == nums[i - 1])
        continue;
      final int num = nums[i];
      final int currCount = count.get(num);
      final int prevCount = count.getOrDefault(num - 1, 0);
      final int nextCount = count.getOrDefault(num + 1, 0);
      for (int j = 0; j < currCount - prevCount; ++j)
        starts.add(num);
      for (int j = 0; j < currCount - nextCount; ++j)
        ends.add(num);
    }

    for (int i = 0; i < starts.size(); ++i)
      if (ends.get(i) - starts.get(i) < 2)
        return false;

    return true;
  }
}

Approach Explanation

The code uses a HashMap to count the occurrences of each number in the array. It then iterates through the numbers to determine how many subsequences can start and end with each number. The key idea is to ensure that for every start of a subsequence, there is a corresponding end that allows for at least two consecutive numbers. If any subsequence fails this check, the function returns false.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

Real-World Example

Imagine you’re organizing a marathon, and you have runners who can only run in groups of three consecutive numbers (1, 2, 3). If you have runners numbered 1, 2, 3, 4, and 5, you can easily form two groups: (1, 2, 3) and (4, 5). But if you have runners numbered 1, 2, 4, and 5, you can’t form a valid group of three, and you’ll have to send them home with a participation ribbon instead.