initial
So I set it like this where for each iteration of number, I set that number as the comparision number +- k for other numbers to be included in the current subsequence. Then, I increment count
But its wrong logic cuz im assuming that the current iter number is either the max or min number in the current subsequence. It does not ensure that max(subsequence) - min(subsequence) <= k for all elements in that subsequence.
class Solution:
def partitionArray(self, nums: List[int], k: int) -> int:
count = 0
visited = [False for _ in range(len(nums))]
for i in range(len(nums)):
if not visited[i]:
visited[i]=True
if i+1!=len(nums):
for j in range(i+1,len(nums)):
if abs(nums[i]-nums[j])<=k:
visited[j]=True
count+=1
return count sol
so instead, we should sort the given nums list first! That way we know the first current number can be the absolute minimum and we can search up to k range. Then set the next number that exceeds this k range to be the minimum value and so on.
But I didnt think of sort cuz it disregards the order, something subsequence needs to know and have. But we can disregard order this case cuz we only care about the values in the subsequence, not the arrangement of numbers within the subsequence.
The constraint (max - min <= k) only depends on the numerical values within each subsequence, not their original positions
class Solution:
def partitionArray(self, nums: List[int], k: int) -> int:
count = 0
nums.sort()
minVal=int(10e7)
# 1,2,3,5,6
for i in range(len(nums)):
if abs(nums[i]-minVal)>k:
minVal=nums[i]
count+=1
else:
continue
return count complexity
n log n time
1 space
