Day 23 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/split-array-subsequences/1

Split Array Subsequences

Difficulty: Medium Accuracy: 51.83%

Given a sorted integer array arr[] and an integer k, determine if it is possible to split the array into one or more consecutive subsequences such that:

1. Each subsequence consists of consecutive integers (each number is exactly one greater than the previous).
2. Every subsequence has a length of at least k. Return true if such a split is possible, otherwise return false.

Examples :
Input: arr[] = [2, 2, 3, 3, 4, 5], k = 2
Output: true
Explanation: arr can be split into three subsequence of length k - [2, 3], [2, 3], [4, 5].
Input: arr[] = [1, 1, 1, 1, 1], k = 4
Output: false
Explanation: It is impossible to split arr into consecutive increasing subsequences of length 4 or more.

Constraints:
1 ≤ arr.size() ≤ 105
1 ≤ arr[i] ≤ 105
1 ≤ k ≤ arr.size()

Solution:
class Solution:
def isPossible(self, arr, k):
from collections import Counter, defaultdict
freq = Counter(arr)
end = defaultdict(int)
for num in arr:
if freq[num] == 0:
continue
freq[num] -= 1
if end[num - 1] > 0:
end[num - 1] -= 1
end[num] += 1
else:
valid = True
for nxt in range(num + 1, num + k):
if freq[nxt] == 0:
valid = False
break
freq[nxt] -= 1
if not valid:
return False
end[num + k - 1] += 1
return True