Today I solved..

Daily challenge 220819

• 659 Split Array into Consecutive Subsequences

Algorithm

1. convert non-decreasing order into 1-increasing sequences reduced into count.
   • if 1-increasing sequence has ended, store current sequence and start new sequence.
   • ex: [1, 2, 3, 3, 4, 5] -> [[1, 1, 2, 1, 1]]
   • ex: [0, 1, 2, 10, 11, 12] -> [[1, 1, 1],[1, 1, 1]]
2. solve each sequence.
   1. while there is non-zero value in sequence:
   2. start decreasing value from first non-zero value until it's increasing
   3. initial sequence example: [1, 1, 3, 2, 2, 1, 1]
   4. round 1: [0, 0, 2, 2, 2, 1, 1]
   5. round 2: [0, 0, 1, 1, 1, 1, 1]
   6. round 3: [0, 0, 0, 0, 0, 0, 0]

Python Code

class Solution:
    def isPossible(self, nums: List[int]) -> bool:

        n = len(nums)

        # convert into sequences        
        sequences = list()        
        seq = list()
        count = 1        
        for i in range(n - 1):            

            # same number
            if nums[i] == nums[i + 1]:                
                count += 1

            # increasing
            elif nums[i + 1] - nums[i] == 1:                
                seq.append(count)
                count = 1

            # new sequence
            else:                
                seq.append(count)                
                if len(seq) < 3:
                    return False                
                sequences.append(seq)

                count = 1
                seq = list()

        seq.append(count)
        if len(seq) < 3:
            return False
        sequences.append(seq)


        # check each sequence
        for seq in sequences:

            while True:
                # lo : first non-zero value index
                lo = -1
                for i in range(len(seq)):
                    if seq[i] != 0:
                        lo = i
                        break
                if lo == -1:
                    break

                # hi : max increasing value index
                hi = lo + 1
                while hi < len(seq):
                    if seq[hi - 1] > seq[hi]:
                        break
                    hi += 1

                if hi - lo < 3:
                    return False

                # decrement until value is increasing
                for i in range(lo, hi):
                    seq[i] -= 1

        return True