C++, DP easy to understand, O(n) time O(1) space


  • 7
    Z

    I feel this problem hard. The idea here is DP.

    1. If numbers are not continuous, I check each segment. For example, 1,2,3,3,4,5, 9,10,11;
    2. Count frequency of each continuous number. Note the value of numbers doesn't matter.
    3. DP part. I use parameter "ones" for subsequences with length 1 ending with index i, "twos" for subsequences with length 2 ending with index i, and "tot" for all subsequences ending with index i.
      When processing next number, if the frequency of new number mp[i+1] < ones+twos, there is no way to split, return false.
      In a greedy way, we need append the new number to short sequences first. So
      twos[i+1] = ones[i];
      ones[i+1] = mp[i+1]-tot, i.e. the extra new number
      If it is possible to split, ones and twos would be 0 by the end of the loop.

    The run time is clearly O(n).

    class Solution {
    public:
        bool isPossible(vector<int>& nums) {
            int n = nums.size(), k = 0;
            //if nums are not continuous, check each section
            //for example, 1,2,3, 6,7,8;
            for (int i = 1; i < n; i++) {
                if (nums[i]-nums[i-1] > 1) {
                    if (!check(nums, k, i-1)) 
                        return false;
                    k = i;
                }
            }
            return check(nums, k, n-1);
        }
    private:
        bool check(vector<int>& nums, int s, int e) {
            int n = nums[e]-nums[s]+1;
            // count frequency of each number
            vector<int> mp(n, 0);
            for (int i = s, tmp = nums[s]; i <= e; i++)
                mp[nums[i]-tmp]++;
            // ones is subsequences with length 1 ending with index i-1
            // twos is subsequences with length 2 ending with index i-1
            // tot  is all subsequences ending with index i-1
            // initially ones[0] ending with index -1, i.e. nonexistent 
            vector<int> ones(n+1, 0), twos(n+1, 0), tot(n+1, 0);
            for (int i = 0; i < n; i++) {
                // we need at least ones+twos new number to make consecutive sequence
                // for examle, two 2, five 1,2, we need at least seven 3
                if (mp[i] < ones[i] + twos[i]) return false;
                // Greedy, appending to short sequences first
                // so twos = ones, and new ones is the extra new number
                twos[i+1] = ones[i];
                ones[i+1] = max(0, mp[i]-tot[i]);
                tot[i+1] = mp[i];
            }
            // if no subsequence length <= 2, return true
            return ones[n] == 0 && twos[n] == 0;
        }
    };
    

    Same code but O(1) space

    class Solution {
    public:
        bool isPossible(vector<int>& nums) {
            int n = nums.size(), k = 0;
            for (int i = 1; i < n; i++) {
                if (nums[i]-nums[i-1] > 1) {
                    if (!check(nums, k, i)) 
                        return false;
                    k = i;
                }
            }
            return check(nums, k, n);
        }
    private:
        bool check(vector<int>& nums, int s, int e) {
            int ones = 0, twos = 0, tot = 0;
            for (int i = s+1, cnt = 1; i <= e; i++) {
                if (i < e && nums[i] == nums[i-1])
                    cnt++;
                else {
                    if (cnt < ones + twos) return false;
                    twos = ones;
                    ones = max(0, cnt-tot);
                    tot = cnt;
                    cnt = 1;
                }
            }
            return ones == 0 && twos == 0;
        }
    };
    

  • 3
    A

    No need to use dp, we can just check every three numbers to ensure that there is sequence

    public class Solution {
        public boolean isPossible(int[] nums) {
            int base = nums[0];
            for (int i = 0; i < nums.length; i++){
                nums[i] = nums[i] - base;
            }
            int[] fre = new int[nums[nums.length - 1] + 3];
            for (int n : nums) fre[n]++;
            for (int i = 2; i <= nums[nums.length - 1] + 2; i++){
                int one = Math.max(fre[i - 1] - fre[i - 2], 0);
                int two = Math.max(0, fre[i - 2] - (i >= 3 ? fre[i - 3] : 0));
                if (fre[i] < one + two || fre[i - 1] < two){
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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