Split Array into Consecutive Subsequences – C++ Solution

Problem Description

Ah, the classic dilemma of trying to split an array into consecutive subsequences! It’s like trying to organize a party where everyone insists on arriving in a specific order. You know, the kind of party where you have to make sure that your guests (the numbers in the array) can form a line of consecutive numbers without anyone feeling left out.

Imagine you have a group of friends who all want to play a game of “Consecutive Numbers.” But wait! They can only play if they can line up in a sequence. If one of them shows up late or decides to skip a number, the whole game is ruined! Your task is to determine if you can split the array into one or more such sequences.

So, if you have an array like [1, 2, 3, 3, 4, 5], you can form the sequences [1, 2, 3] and [3, 4, 5]. But if you have [1, 2, 3, 4, 5, 6, 8], you’re out of luck because there’s no way to include 7 in any sequence.

Code Solution


class Solution {
 public:
  bool isPossible(vector& nums) {
    unordered_map count;
    vector starts;  // the start indices of each subsequence
    vector ends;    // the end indices of each subsequence

    for (const int num : nums)
      ++count[num];

    for (int i = 0; i < nums.size(); ++i) {
      if (i > 0 && nums[i] == nums[i - 1])
        continue;
      const int num = nums[i];
      const int currCount = count[num];
      const int prevCount = count.contains(num - 1) ? count[num - 1] : 0;
      const int nextCount = count.contains(num + 1) ? count[num + 1] : 0;
      for (int j = 0; j < currCount - prevCount; ++j)
        starts.push_back(num);
      for (int j = 0; j < currCount - nextCount; ++j)
        ends.push_back(num);
    }

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

    return true;
  }
};

Approach

The approach taken in this solution is quite clever. It uses a hash map to count the occurrences of each number in the array. Then, it iterates through the array to determine how many subsequences can be formed. The key idea is to track the start and end of potential subsequences and ensure that each subsequence has at least three consecutive numbers. If any subsequence fails this condition, the function returns false.

Time and Space Complexity

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

Real-World Example

Think of it like organizing a marathon. You have runners (the numbers) who need to line up in consecutive order to start the race. If one runner decides to skip a number (like not showing up for the race), you can’t have a proper start. You need to ensure that there are enough consecutive runners to form a valid starting line. If you can’t, the race is off!