Split Array into Consecutive Subsequences

Split Array into Consecutive Subsequences

What is this problem about?

The Split Array into Consecutive Subsequences interview question asks you to determine if a sorted array can be partitioned into one or more subsequences such that each subsequence consists of consecutive integers and has a minimum length of three. This problem combines array partitioning with strict length and value constraints, making it a complex logic puzzle.

Why is this asked in interviews?

Companies like Amazon and Google use this Split Array into Consecutive Subsequences coding problem to test a candidate's ability to think several steps ahead. It requires balancing the need to satisfy the "minimum length 3" rule while still using up all the numbers in the array. It evaluates your skills in Greedy logic and your ability to use Hash Tables or Heaps to track the state of multiple sequences simultaneously.

Algorithmic pattern used

The most efficient approach is a Greedy strategy using two Hash Maps:

1. A frequency map to count how many of each number remain.
2. A hypothetical (or needs) map to track which numbers are needed to extend existing subsequences. For each number, you first try to add it to an existing subsequence that needs it. If that's not possible, you try to start a new subsequence of length 3 (checking if the next two consecutive numbers are available). If neither is possible, you return false.

Example explanation

Array: [1, 2, 3, 3, 4, 5]

1. Number 1: Can't extend. Can start 1-2-3? Yes. (1, 2, 3 used). Subsequences: [1,2,3].
2. Number 3: Remaining 3. Can it extend? No. Can start 3-4-5? Yes. (3, 4, 5 used). Subsequences: [1,2,3], [3,4,5]. All numbers used. Result: True.

If the array was [1, 2, 3, 3, 4]:

1. 1-2-3 are used.
2. Number 3: Can't extend. Try to start 3-4-5? No 5 available.
3. Number 4: Not used. Result: False (because the second 3 and 4 couldn't form a sequence of length 3).

Common mistakes candidates make

• Min Length 3 Ignore: Forgetting the rule that every sequence must have at least 3 elements.
• Sorting Requirement: Not checking if the array is sorted, or failing to realize how sorting simplifies the problem.
• Greedy Priority: Not prioritizing extending an existing sequence over starting a new one. Extending is always safer because it doesn't "cost" you the next two numbers.
• Map Management: Not properly decrementing counts in the frequency map, leading to using the same number twice.

Interview preparation tip

For greedy problems, always consider the "priority of choices." In this problem, the priority is: 1. Extend an existing sequence. 2. Start a new sequence of length 3. This hierarchy ensures that you don't leave "dangling" sequences that are too short to be valid.