Skip to main content

Split Array into Consecutive Subsequences

Problem Description​

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer). All subsequences have a length of 3 or more. Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Examples​

Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

Constraints​

  • 1 <= nums.length <= 10^4
  • -1000 <= nums[i] <= 1000
  • nums is sorted in non-decreasing order.

Solution for Split Array into Consecutive Subsequences​

Approach​

Data Structures​

  1. left Counter:

    • Keeps track of the frequency of each number in the array.
    • Helps to know how many of a particular number are left to be placed in a subsequence.

  2. end Counter:

    • Keeps track of the subsequences that end at a particular number.
    • Helps to know if a number can be appended to an existing subsequence.

Algorithm​

  1. Initialization:

    • Count the frequency of each number in the array A using the left counter.

  2. Iteration through the Array:

    • For each number i in A, do the following:

      • If i is no longer available in left (its count is zero), skip it.

      • Decrease the count of i in left.

      • Check if i can extend a previous subsequence:

        • If there is a subsequence ending at i-1 (i.e., end[i - 1] > 0):
          • Decrease the count of subsequences ending at i-1.
          • Increase the count of subsequences ending at i.

      • Else, Check if i can start a new subsequence:

        • If there are available i+1 and i+2 in left:
          • Decrease the count of i+1 and i+2 in left.
          • Increase the count of subsequences ending at i+2.

      • If neither of the above conditions hold:

        • Return False because i cannot be part of a valid subsequence.

  3. Return True:

    • If all numbers have been processed without any issues, return True.

Intuition​

  • The main idea is to use a greedy approach to build valid subsequences.
  • By maintaining counters (left and end), we can efficiently manage the formation and extension of subsequences.
  • We prioritize extending existing subsequences to ensure that subsequences of length at least 3 are formed whenever possible.
  • If extending is not possible, we check if a new subsequence can be started.
  • The algorithm ensures that every number is either used to extend a subsequence or to start a new valid subsequence, making it both efficient and correct.

Implementation​

Live Editor
function Solution(arr) {
  function isPossible(A) {
    const left = new Map();
    const end = new Map();

    for (let num of A) {
        left.set(num, (left.get(num) || 0) + 1);
    }

    for (let num of A) {
        if (left.get(num) === 0) continue;
        left.set(num, left.get(num) - 1);

        if ((end.get(num - 1) || 0) > 0) {
            end.set(num - 1, end.get(num - 1) - 1);
            end.set(num, (end.get(num) || 0) + 1);
        } else if ((left.get(num + 1) || 0) > 0 && (left.get(num + 2) || 0) > 0) {
            left.set(num + 1, left.get(num + 1) - 1);
            left.set(num + 2, left.get(num + 2) - 1);
            end.set(num + 2, (end.get(num + 2) || 0) + 1);
        } else {
            return false;
        }
    }

    return true;
}

  const input =[1,2,3,3,4,5]
  const output = isPossible(input)
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(N)O(N)
  • Space Complexity: O(N) O(N)

Code in Different Languages​

Written by @hiteshgahanolia
  function isPossible(A) {
 const left = new Map();
 const end = new Map();

 for (let num of A) {
     left.set(num, (left.get(num) || 0) + 1);
 }

 for (let num of A) {
     if (left.get(num) === 0) continue;
     left.set(num, left.get(num) - 1);

     if ((end.get(num - 1) || 0) > 0) {
         end.set(num - 1, end.get(num - 1) - 1);
         end.set(num, (end.get(num) || 0) + 1);
     } else if ((left.get(num + 1) || 0) > 0 && (left.get(num + 2) || 0) > 0) {
         left.set(num + 1, left.get(num + 1) - 1);
         left.set(num + 2, left.get(num + 2) - 1);
         end.set(num + 2, (end.get(num + 2) || 0) + 1);
     } else {
         return false;
     }
 }

 return true;
}

References​