Greedy solution


  • 0
    T

    Each time considering the starting element s = nums[0].

    We know if there is a solution, s must be a beginning of a sequence, or we can pad s to some existing sequence that has 3+ elements that expects next element to be s+1.

    We should favor padding s to an existing sequence before we look beyond to form a new sequence weith 3+ elements, because each solution with more subsequences than the solution with minimum subsequences and longest subsequences can be converted into the latter.

    (1,2,3), (4,5,6) => (1,2,3,4,5,6).

    To remember if we have any subsequence with 3+ elements that accept s, we can use Dictionary<int,int>, where it counts the number of 3+ element subsequence that expects Key.

    Thus each time we see a new element, we query s to see if we can append it to an existing subsequence. If not, we need to see if it can form a new 3+ element subsequence. If not, the splitting cannot be done.

    This procedure is summarized below.

    As an optimization we can group integers instead of checking the continuous same element every time, and if that's done, the complexity is O(n). Otherwise, complexity is O(kn), where k is the count of the element that has the most appearance.

      public class Solution {
            public bool IsPossible(int[] nums)
            {
                var list = nums.ToList();
                Dictionary<int, int> done = new Dictionary<int, int>();
                while (list.Count > 0)
                {
                    int idx = 0;
                    int current = list[idx];
                    int orig = current;
                    list.RemoveAt(idx);
                    int len = 1;
                    //scan right.
                    if (done.ContainsKey(orig))
                    {
                        if (done[orig] > 0)
                        {
                            done[orig]--;
                            if (done.ContainsKey(orig + 1) == false)
                            {
                                done[orig + 1] = 0;
                            }
                            done[orig + 1]++;
                            continue;
                        }
                    }
                    while (len < 3 && list.Count > 0 && idx < list.Count)
                    {
                        int newVal = list[idx];
                        if (newVal == current)
                        {
                            idx++;
                            continue;
                        }
                        else if (newVal == current + 1)
                        {
                            //pick newVal.
                            list.RemoveAt(idx);
                            len++;
                            current = newVal;
                        }
                        else
                        {
                            break;
                        }
                    }
                    //if len >= 3.
                    if (len >= 3)
                    {
                        //Debug.Assert(current  == orig + len - 1);
                        if (done.ContainsKey(current + 1) == false)
                        {
                            done[current + 1] = 0;
                        }
                        done[current + 1]++;
                    }
                    else
                    {
                        if (done.ContainsKey(orig) == false)
                        {
                            return false;
                        }
                        else
                        {
                            done[orig]--;
                            if (done[orig] < 0) return false;
                            int newHead = orig + len;
                            if (done.ContainsKey(newHead) == false)
                            {
                                done[newHead] = 0;
                            }
                            done[newHead]++;
                        }
                    }
                }
                return true;
            }
      }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.