Split Array Subsequences

JavaView on GFG

Intuition

Split array into minimum number of consecutive increasing sequences each of length >= 3.

Algorithm

1Greedy: use frequency map and end-count map. For each x: prefer appending to existing sequence ending at x-1.

Common Pitfalls

•Same as LC 659. Two maps: count remaining, ends. Greedy append then start new. O(n).

Split Array Subsequences.java

Java

// Approach: Greedy with HashMap. Append to existing subsequences or start new ones; track ends.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {

    public boolean isPossible(int[] arr, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> end = new HashMap<>();

        for (int num : arr)
            count.put(num, count.getOrDefault(num, 0) + 1);

        for (int num : arr) {
            if (count.get(num) == 0)
                continue;

            count.put(num, count.get(num) - 1);

            if (end.getOrDefault(num - 1, 0) > 0) {
                end.put(num - 1, end.get(num - 1) - 1);
                end.put(num, end.getOrDefault(num, 0) + 1);
            }

            else {
                boolean canForm = true;
                for (int j = 1; j < k; j++) {
                    if (count.getOrDefault(num + j, 0) <= 0) {
                        canForm = false;
                        break;
                    }
                }

                if (!canForm)
                    return false;

                for (int j = 1; j < k; j++)
                    count.put(num + j, count.get(num + j) - 1);

                end.put(num + k - 1, end.getOrDefault(num + k - 1, 0) + 1);
            }
        }

        return true;
    }
}

Was this solution helpful?