Python accepted solution, easy to understand


  • 0
    P

    maintain records of subsequences as [ curr_largest_number, #_of_consective_numbers ]
    go through all the number in the array

    • if it is equal to the last record's largest number + 1:
      num == stack[-1][0] + 1, then update this record
    • if it is larger than last record's largest number + 1: num > stack[-1][0] + 1, then add a new record
    • if it is less than last record's largest number +1: then go back to check the earlier records with the same methods in the stack

    samples:
    nums = [1,2,3,3,4,4,5,5] => stack = [[5, 5], [5, 3]]
    [[1, 1]]
    [[2, 2]]
    [[3, 3]]
    [[3, 3], [3, 1]]
    [[3, 3], [4, 2]]
    [[4, 4], [4, 2]]
    [[4, 4], [5, 3]]
    [[5, 5], [5, 3]]

    class Solution(object):
        def isPossible(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            stack = []
            for num in nums:
            	if not stack or num > stack[-1][0] + 1:
            		stack.append( [num, 1] )
            		continue
            	elif num == stack[-1][0] + 1:
            		stack[-1][0] += 1
            		stack[-1][1] += 1
            	else:
            		for i in range(1, len(stack)):
            			if num == stack[~i][0] + 1:
            				stack[~i][0] += 1
            				stack[~i][1] += 1
            				break
            			elif num > stack[~i][0] + 1:
            				if stack[~i][1] < 3:
            					return False
            				stack.append( [num, 1] )
            				break
            		else:
            			stack.append( [num, 1] )
            return min(map(lambda x:x[1], stack)) >= 3
    

Log in to reply
 

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