# Weekly Contest 269
# 2089. Find Target Indices After Sorting Array
# Solution
class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums.sort()
res = []
for i in range(len(nums)):
if nums[i] > target:
break
if nums[i] == target:
res.append(i)
return res
# 2090. K Radius Subarray Averages
2090. K Radius Subarray Averages
class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
curSum = 0
length = 2*k + 1
if len(nums) < length:
return [-1 for i in range(len(nums))]
res = [0 for i in range(len(nums))]
for i in range(length -1):
curSum += nums[i]
if i < k:
res[i] = -1
for i in range(k, len(nums) - k):
curSum += nums[i+k]
res[i] = curSum // length
if i == len(nums) - k:
break
curSum -= nums[i-k]
for i in range(len(nums) - k, len(nums)):
res[i] = -1
return res
# Leetcode 2091. Removing Minimum and Maximum From Array
2091. Removing Minimum and Maximum From Array
class Solution:
def minimumDeletions(self, nums: List[int]) -> int:
if len(nums) == 1:
return 1
minIndex, minValue = 0, 10**6
maxIndex, maxValue = 0, -10**6
length = len(nums)
for i in range(len(nums)):
if nums[i] < minValue:
minValue = nums[i]
minIndex = i
if nums[i] > maxValue:
maxValue = nums[i]
maxIndex = i
if minIndex > maxIndex:
maxIndex, minIndex = minIndex, maxIndex
print(minIndex, maxIndex, len(nums), maxIndex + 1, len(nums) - minIndex, minIndex + 1 + len(nums) - maxIndex)
res = min(maxIndex + 1, len(nums) - minIndex, minIndex + 1 + len(nums) - maxIndex)
return res
# Leetcode 2092 Find All People With Secret
2092. Find All People With Secret
Contruct and use union find to find the solution.
class Solution:
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
group = [i for i in range(n)]
meetings.append([0, firstPerson, 0])
meetings.sort(key=lambda x: x[2])
def union(p1, p2):
g1 = find(p1)
g2 = find(p2)
group[g2] = g1
def find(p):
if group[p] == p: return group[p]
else:
g = find(group[p])
group[p] = g
return g
i = 0
while i < len(meetings):
known = []
in_queue = [meetings[i]]
i += 1
while i < len(meetings):
if meetings[i][-1] == in_queue[-1][-1]:
in_queue.append(meetings[i])
i += 1
else: break
for m in in_queue:
p1 = m[0]
p2 = m[1]
if find(p1) == 0:
union(p1, p2)
elif find(p2) == 0:
union(p2, p1)
else:
union(p1, p2)
known.append(p1)
known.append(p2)
for p in known:
if find(p) != 0:
group[p] = p
return [i for i in range(n) if find(i) == 0]