algoadvance

Leetcode 659. Split Array into Consecutive Subsequences

Problem Statement

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

You need to determine if it is possible to split nums into one or more subsequences such that:

  1. Each subsequence consists of consecutive integers.
  2. Each subsequence has a length of at least 3.

Return true if it is possible to split nums according to the above conditions, otherwise return false.

Clarifying Questions

  1. Are there any specific constraints on the length of the array?
    • Typically, the problem doesn’t specify constraints, but it is safe to consider that the array size could be large (up to 10^4 or higher).
  2. Can the same element be part of multiple subsequences?
    • No, each element can be part of only one subsequence.
  3. What happens if the input array has less than 3 elements?
    • If the array has less than 3 elements, it is not possible to form a subsequence of at least 3 consecutive integers, so the answer should be false for such inputs.

Strategy

To solve this problem, we can use a greedy algorithm with the help of two hash maps:

  1. Frequency Map (freq): This map keeps track of the remaining frequency of each integer in nums.
  2. Hypothetical End Map (end_map): This map keeps track of subsequences that end at a particular integer value.

Steps to solve the problem:

  1. Populate the freq map with the frequency of each number in nums.
  2. Iterate through each number in nums to check if it can be placed in an existing subsequence or if a new subsequence can be started.
  3. For each number:
    • If its frequency is 0, continue to the next number.
    • If an existing subsequence ending at num-1 can be extended, do so.
    • If a subsequence cannot be extended, check if we can start a new subsequence with num, num+1, and num+2.
    • If neither of the above conditions is satisfied, return false.
  4. After processing all numbers, if all operations are valid, return true.

Code

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> freq, end_map;
        
        // Fill the frequency map
        for (int num : nums) {
            freq[num]++;
        }
        
        for (int num : nums) {
            if (freq[num] == 0) {
                continue; // If current number is already used, skip it
            }
            
            // Try to add this number to an existing subsequence ending with num - 1
            if (end_map[num - 1] > 0) {
                end_map[num - 1]--;
                end_map[num]++;
            } 
            // If can't extend a previous subsequence, try to start a new one with num, num + 1, num + 2
            else if (freq[num + 1] > 0 && freq[num + 2] > 0) {
                freq[num + 1]--;
                freq[num + 2]--;
                end_map[num + 2]++;
            } 
            // If neither, return false
            else {
                return false;
            }
            
            // Decrease the frequency of the current number
            freq[num]--;
        }
        
        return true;
    }
};

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the input array nums. This is because we iterate through the array a constant number of times, performing constant-time operations at each step through the use of hash maps.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI