# Solving Leetcode Interviews in Seconds with AI: Split Array into Consecutive Subsequences


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "659" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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).   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  Example 3:  Input: nums = [1,2,3,4,4,5] Output: false Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.    Constraints:  1 <= nums.length <= 104 -1000 <= nums[i] <= 1000 nums is sorted in non-decreasing order.  

	# Explanation
	Here's the breakdown of the approach and the Python code:

*   **High-Level Approach:**
    *   Iterate through the input array `nums`. Maintain two dictionaries: `freq` to store the frequency of each number and `tails` to store the number of subsequences ending with a particular number.
    *   For each number `num`, check if it can be appended to an existing subsequence (i.e., if `tails[num - 1] > 0`). If so, decrement `tails[num - 1]` and increment `tails[num]`.
    *   If `num` cannot be appended to an existing subsequence, check if a new subsequence of length 3 or more can be started. This requires `freq[num + 1] > 0` and `freq[num + 2] > 0`. If so, decrement `freq[num + 1]` and `freq[num + 2]` and increment `tails[num + 2]`.
    *   If neither of the above conditions is met, it means that `num` cannot be part of any valid subsequence, so return `False`.

*   **Complexity:**
    *   Runtime Complexity: O(n), where n is the length of the input array.
    *   Storage Complexity: O(n), where n is the range of numbers in the input array which effectively translates to the number of unique elements.

	
	# Code
	```python
	from collections import defaultdict

def is_possible(nums):
    freq = defaultdict(int)
    tails = defaultdict(int)

    for num in nums:
        freq[num] += 1

    for num in nums:
        if freq[num] == 0:
            continue

        freq[num] -= 1

        if tails[num - 1] > 0:
            tails[num - 1] -= 1
            tails[num] += 1
        elif freq[num + 1] > 0 and freq[num + 2] > 0:
            freq[num + 1] -= 1
            freq[num + 2] -= 1
            tails[num + 2] += 1
        else:
            return False

    return True
	```