Split Array Into Consecutive Subsequences

Difficulty Level Medium
Frequently asked in Google
Greedy HeapViews 2585

Given a sorted array(in ascending order), check if the array can be split into 1 or more subsequences of length greater than equals to 3 such that every subsequence contains consecutive numbers.

Examples

Input:
arr[] = {1,2,3,3,4,5}
Output:
true
Explanation:
The array can be split into 2 subsequences as,
sub1[] = {1, 2, 3}
sub2[] = {3, 4, 5}

Input:
arr[] = {Z1, 2, 3, 3, 4, 4, 5, 5}
Output:
true
Explanation:
The consecutive subsequences are,
sub1[] = {1, 2, 3, 4, 5}
sub2[] = {3, 4, 5}

Split Array Into Consecutive Subsequences

Naive Approach for Split Array Into Consecutive Subsequences

For an element arr[i] of the given array, it can either form a new subsequence or can be added to a subsequence ending at (arr[i] – 1).

It is always better not to form a new subsequence as forming a new subsequence may result in some subsequences of length less than three. If there is no subsequence ending at (arr[i] – 1), there is no option but to form a new subsequence.

If there are more than one subsequences that can accommodate the current element, always add the current element to the subsequence with the least number of elements, this will ensure the minimization of subsequences of length less than 3.

Algorithm

  1. The first element of the array always forms a new subsequence.
  2. Traverse the array starting from index 1(0 based indexing).
  3. Check if there is some subsequence that can accommodate the current element, an element arr[i] can be added to a subsequence ending at (arr[i] – 1).
  4. If there is no subsequence that can accommodate the current element form a new subsequence.
  5. Else choose the subsequence with a minimum size that can accommodate the current element and add the current element to the chosen subsequence.
  6. After traversing the array, check if there is some subsequence of length less than 3, if yes, return false, else return true.

JAVA Code for Split Array Into Consecutive Subsequences

import java.util.ArrayList;

public class SplitTheArrayIntoConsecutievSubsequences {
    private static boolean isPossible(int[] arr) {
        // If the lenght of arr is less than 3, it is not possible to split the array
        if (arr == null || arr.length < 3) {
            return false;
        }
        int n = arr.length;

        // List of subsequences
        ArrayList<ArrayList<Integer>> al = new ArrayList<>();

        // First element always forms a new subsequence
        ArrayList<Integer> eles = new ArrayList<Integer>();
        eles.add(arr[0]);
        al.add(eles);

        // Traverse the array starting from index 1
        for (int i = 1; i < n; i++) {
            // Required position of subsequence that can accommodate the current element
            int pos = -1;
            // Size of required subsequence
            int size = -1;
            // Check if there is some subsequence that can accommodate the current element
            for (int j = 0; j < al.size(); j++) {
                // A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
                if (al.get(j).get(al.get(j).size() - 1) + 1 == arr[i]) {
                    if (pos == -1) {
                        pos = j;
                        size = al.get(j).size();
                    } else {
                        // Select the subsequence with minimum size
                        if (al.get(j).size() < size) {
                            pos = j;
                            size = al.get(j).size();
                        }
                    }
                }
            }

            // If there is no subsequence that can accommodate the current element
            // form a new subsequence
            if (pos == -1) {
                ArrayList<Integer> newAL = new ArrayList<>();
                newAL.add(arr[i]);
                al.add(newAL);
            } else {
                // else add it to the required subsequence
                al.get(pos).add(arr[i]);
            }
        }

        for (int i = 0; i < al.size(); i++) {
            // if there is some subsequence of length less than 3, return false
            if (al.get(i).size() < 3) {
                return false;
            }
        }
        // No subsequence of length less than 3, return true
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{1, 2, 3, 3, 4, 5};

        System.out.println(isPossible(arr1));

        // Example 2
        int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};

        System.out.println(isPossible(arr2));

        // Example 3
        int arr3[] = new int[]{1, 2, 3, 4, 4, 5};

        System.out.println(isPossible(arr3));
    }
}
true
true
false

C++ Code for Split Array Into Consecutive Subsequences

#include<bits/stdc++.h> 
using namespace std;

bool isPossible(int *arr, int n) {
    if (n < 3) {
        return false;
    }
    
    // List of subsequences
    vector<vector<int>> v;
    
    // First element always forms a new subsequence
    vector<int> eles;
    eles.push_back(arr[0]);
    v.push_back(eles);
    
    // Traverse the array starting from index 1
    for (int i = 1; i < n; i++) {
        // Required position of subsequence that can accommodate the current element
        int pos = -1;
        // Size of required subsequence
        int size = -1;
        // Check if there is some subsequence that can accommodate the current element
        for (int j = 0; j < v.size(); j++) {
            // A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
            if (v[j][v[j].size() - 1] + 1 == arr[i]) {
                if (pos == -1) {
                    pos = j;
                    size = v[j].size();
                } else {
                    // Select the subsequence with minimum size
                    if (v[j].size() < size) {
                        size = v[j].size();
                        pos = j;
                    }
                }            
            }
        }
        
        // If there is no subsequence that can accommodate the current element
        // form a new subsequence
        if (pos == -1) {
            vector<int> newV;
            newV.push_back(arr[i]);
            v.push_back(newV);
        } else {
            v[pos].push_back(arr[i]);
        }
    }
    
    for (int i = 0; i < v.size(); i++) {
        if (v[i].size() < 3) {
            return false;
        }
    }
    return true;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 3, 4, 5};
    if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
    if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 3
    int arr3[] = {1, 2, 3, 4, 4, 5};
    if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
        
    return 0;
}
true
true
false

Complexity Analysis

Time Complexity = O(n2)
Space Complexity = O(n)

Optimal Approach for Split Array Into Consecutive Subsequences

For an element arr[i], either it can form a new subsequence or can be added to another subsequence ending at (arr[i] – 1), if there are more than one subsequence that can accommodate arr[i], add it to the subsequence of minimum length.

Only three types of subsequence length are important, that is, subsequences of length 1, length 2 and length greater than equals to 3, denoted as p1, c1, p2, c2, p3 and c3, where p means previous and c means current.

For every number first count the number of occurrences of it in the array, check if it can spread across all the subsequences of length 1 and 2, if it cannot, return false immediately, because if the current number cannot extend subsequences of length 1 or 2, no number will do as the array is sorted. So there will remain some subsequences of length 1 or 2 at the end.

Else all the subsequences of length 1 converts to subsequences of length 2, length 2 converts to length 3, and remaining elements are added to subsequences of length 3 or more, if still some elements are not distributed they contributes to subsequences of length 1, else only the elements contributing to length 3 or more adds to the new length 3 subsequences.

At the end, if there are no length 1 and length 2 subsequences return true, else return false.

JAVA Code

public class SplitArrayIntoConsecutiveSubsequences {
    private static boolean isPossible(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return false;
        }

        int p1 = 0, p2 = 0, p3 = 0;
        int c1 = 0, c2 = 0, c3 = 0;
        int i = 0;
        // prev denotes previous element
        // curr denotes current element
        int prev = 0, curr = 0;

        // Traverse the array
        while (i < n) {
            // Current becomes previous
            p1 = c1;
            p2 = c2;
            p3 = c3;

            prev = curr;
            curr = arr[i];

            int count = 0;
            // Count the frequency of current element
            while (i < n && arr[i] == curr) {
                i++;
                count++;
            }

            if (prev + 1 == curr) {
                // if element cannot be spread across subsequences of length 1 and 2
                if (count < p1 + p2) {
                    // return false immediately
                    return false;
                }
                // Update c1, c2, c3 as described
                c1 = Math.max(0, count - (p1 + p2 + p3));
                c2 = p1;
                c3 = p2 + Math.min(p3, count - (p1 + p2));
            } else {
                // this element cannot be spread across any subsequence
                if (p1 != 0 || p2 != 0) {
                    // if there is any subsequence of length 1 or 2
                    // return false immediately
                    return false;
                }
                // Update c1, c2, c3 as described
                c1 = count;
                c2 = 0;
                c3 = 0;
            }
        }

        // if there are no length 1 and length 2 subsequences return true, else return false
        return (c1 == 0 && c2 == 0);
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{1, 2, 3, 3, 4, 5};

        System.out.println(isPossible(arr1));

        // Example 2
        int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};

        System.out.println(isPossible(arr2));

        // Example 3
        int arr3[] = new int[]{1, 2, 3, 4, 4, 5};

        System.out.println(isPossible(arr3));
    }
}
true
true
false

C++ Code

#include<bits/stdc++.h> 
using namespace std;

bool isPossible(int *arr, int n) {
    if (n < 3) {
        return false;
    }
    
    int p1 = 0, p2 = 0, p3 = 0;
    int c1 = 0, c2 = 0, c3 = 0;
    int i = 0;
    // prev denotes previous element
    // curr denotes current element
    int prev = 0, curr = 0;
    
    // Traverse the array
    while (i < n) {
        // Current becomes previous
        p1 = c1;
        p2 = c2;
        p3 = c3;
        
        prev = curr;
        curr = arr[i];
        
        int count = 0;
        // Count the frequency of current element
        while (i < n && arr[i] == curr) {
            i++;
            count++;
        }
        
        if (prev + 1 == curr) {
            // if element cannot be spread across subsequences of length 1 and 2
            if (count < p1 + p2) {
                // return false immediately
                return false;
            }
            // Update c1, c2, c3 as described
            c1 = std::max(0, count - (p1 + p2 + p3));
            c2 = p1;
            c3 = p2 + std::min(p3, count - (p1 + p2));
        } else {
            // this element cannot be spread across any subsequence
            if (p1 != 0 || p2 != 0) {
                // if there is any subsequence of length 1 or 2
                // return false immediately
                return false;
            }
            // Update c1, c2, c3 as described
            c1 = count;
            c2 = 0;
            c3 = 0;
        }
    }

    // if there are no length 1 and length 2 subsequences return true, else return false
    return (c1 == 0 && c2 == 0);
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 3, 4, 5};
    if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
    if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 3
    int arr3[] = {1, 2, 3, 4, 4, 5};
    if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
        
    return 0;
}
true
true
false

Complexity Analysis

Time Complexity = O(n)
Space Complexity = O(1)

References

Translate ยป