Divide Array Into Increasing Sequences - Leetcode Solution

Problem Statement:

Given a non-empty array of integers nums, you are asked to divide the array into some number of non-empty subsequences, where each subsequence is consecutive and increasing in order.

Return true if you can make such a division, or false otherwise.

Solution:

Approach:

The approach is simple. We maintain a priority queue which stores the number of subsequences formed till now and the end of the last subsequence. Now for each number, we check if it can be appended to an already existing subsequence or not. If yes, then we pop the highest priority element and add the current number to the subsequence and if it is the last element of the subsequence, we just decrement the number of subsequences. If it can't be appended to any subsequence, we create a new subsequence with this number as the last element.

Algorithm:

1. Create a priority queue of pairs (count of subsequences, end of the last subsequence), initially with (0,0).
2. Sort the input array.
3. For each number in the array, perform the following steps:

• If the priority queue is empty, create a new subsequence with this number as the last element in the subsequence.
• If the current number is equal to the end of the last subsequence in the priority queue, pop the highest priority element from the queue, decrement the count of subsequences and add the current number to the last subsequence.
• If the current number is greater than the end of the last subsequence in the priority queue, create a new subsequence with this number as the last element in the subsequence.
• If the current number is less than the end of the last subsequence in the priority queue, return false as we cannot create increasing subsequences.

4. Finally, return true.

Time Complexity:

This algorithm has two steps -- sorting the input array and iterating through the array. Sorting takes O(nlogn) time and iterating takes O(n) time, so the total time complexity is O(nlogn + n) which simplifies to O(nlogn).

Space Complexity:

We are using a priority queue to store the pairs, so the space complexity is O(n).

Code in Python:

import heapq

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        
        pq = [(0,0)]  # priority queue to store (count of subsequences formed, end of last subsequence)
        
        for num in sorted(nums):
            if pq[0][1] == num - 1:  # adding to an existing subsequence
                cnt, end = heapq.heappop(pq)
                cnt += 1
                end = num
                heapq.heappush(pq, (cnt, end))
            elif pq[0][1] < num - 1:  # creating a new subsequence
                heapq.heappush(pq, (1, num))
            else:  # cannot create increasing subsequences
                return False
        
        # if we reach here, it means we have formed all increasing subsequences
        return True

Example:

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

Output: True

Explanation: We can form two increasing subsequences -- (1,2,3,4,5) and (3,4,5).

1