An Interest In:
Web News this Week
- March 21, 2024
- March 20, 2024
- March 19, 2024
- March 18, 2024
- March 17, 2024
- March 16, 2024
- March 15, 2024
August 19, 2022 08:15 am GMT
Original Link: https://dev.to/salahelhossiny/split-array-into-consecutive-subsequences-1h1l
Split Array into Consecutive Subsequences
You are given an integer array nums that is sorted in non-decreasing order.
Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:
Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
All subsequences have a length of 3 or more.
Return true if you can split nums according to the above conditions, or false otherwise.
A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).
class Solution: def isPossible(self, nums: List[int]) -> bool: if len(nums) < 3: return False frequency = collections.Counter(nums) subsequence = collections.defaultdict(int) for i in nums: if frequency[i] == 0: continue frequency[i] -= 1 # option 1 - add to an existing subsequence if subsequence[i-1] > 0: subsequence[i-1] -= 1 subsequence[i] += 1 # option 2 - create a new subsequence elif frequency[i+1] and frequency[i+2]: frequency[i+1] -= 1 frequency[i+2] -= 1 subsequence[i+2] += 1 else: return False return True
Original Link: https://dev.to/salahelhossiny/split-array-into-consecutive-subsequences-1h1l
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To