Vivek, I have followed your approach for finding unique mode in middle and I got TLE eventhough it seems like O(n ^ 2), am I missing anything? from math import comb class Solution: def subsequencesWithMiddleMode(self, nums: List[int]) -> int: uniqueMiddleModes = 0 uniqueNums = list(set(nums)) MOD = 10 ** 9 + 7 for i in range(2, len(nums) - 2): leftMap = Counter(nums[:i]) rightMap = Counter(nums[i + 1: ]) totalElementsAtLeft = i totalElementsAtRight = len(nums) - (i + 1) # any 2, i as mid, any 2 total = (comb(totalElementsAtLeft, 2) * 1 * comb(totalElementsAtRight, 2)) % MOD invalidCases = 0 a = nums[i] # any 2 apart from "a", "a" as mid, any 2 apart from "a" num # exact 1 nums[i] at mid case invalidCase1 = (comb(totalElementsAtLeft - leftMap[a], 2) * 1 * comb(totalElementsAtRight - rightMap[a], 2)) % MOD # now comes difficult case, exact 2 nums[i] and nums[i] at mid invalidCase2 = 0 for b in uniqueNums: if b == nums[i]: continue rightCCount = totalElementsAtRight - rightMap[a] - rightMap[b] leftCCount = totalElementsAtLeft - leftMap[a] - leftMap[b] # (b b) a (a c) invalidCase2 += (comb(leftMap[b], 2) * 1 * rightMap[a] * rightCCount) % MOD # (a c) a (b b) invalidCase2 += (leftMap[a] * leftCCount * 1 * comb(rightMap[b], 2)) % MOD # (a b) a (b c) invalidCase2 += (leftMap[a] * leftMap[b] * 1 * rightMap[b] * rightCCount) % MOD # (b c) a (a b) invalidCase2 += (leftMap[b] * leftCCount * 1 * rightMap[a] * rightMap[b]) % MOD # (b b) a (a b) invalidCase2 += (comb(leftMap[b], 2) * 1 * rightMap[a] * rightMap[b]) % MOD # (a b) a (b b) invalidCase2 += (leftMap[a] * leftMap[b] * 1 * comb(rightMap[b], 2)) % MOD uniqueMiddleModes += total - invalidCase1 - invalidCase2 return uniqueMiddleModes % MOD
Amazing session!!, Sweep line problem was awesome!!.
Please don't stop these sessions format ever
These sessions are so helpful ❤
30:16 Meet in the middle (MITM)
Vivek, I have followed your approach for finding unique mode in middle and I got TLE eventhough it seems like O(n ^ 2), am I missing anything?
from math import comb
class Solution:
def subsequencesWithMiddleMode(self, nums: List[int]) -> int:
uniqueMiddleModes = 0
uniqueNums = list(set(nums))
MOD = 10 ** 9 + 7
for i in range(2, len(nums) - 2):
leftMap = Counter(nums[:i])
rightMap = Counter(nums[i + 1: ])
totalElementsAtLeft = i
totalElementsAtRight = len(nums) - (i + 1)
# any 2, i as mid, any 2
total = (comb(totalElementsAtLeft, 2) * 1 * comb(totalElementsAtRight, 2)) % MOD
invalidCases = 0
a = nums[i]
# any 2 apart from "a", "a" as mid, any 2 apart from "a" num
# exact 1 nums[i] at mid case
invalidCase1 = (comb(totalElementsAtLeft - leftMap[a], 2) * 1 * comb(totalElementsAtRight - rightMap[a], 2)) % MOD
# now comes difficult case, exact 2 nums[i] and nums[i] at mid
invalidCase2 = 0
for b in uniqueNums:
if b == nums[i]:
continue
rightCCount = totalElementsAtRight - rightMap[a] - rightMap[b]
leftCCount = totalElementsAtLeft - leftMap[a] - leftMap[b]
# (b b) a (a c)
invalidCase2 += (comb(leftMap[b], 2) * 1 * rightMap[a] * rightCCount) % MOD
# (a c) a (b b)
invalidCase2 += (leftMap[a] * leftCCount * 1 * comb(rightMap[b], 2)) % MOD
# (a b) a (b c)
invalidCase2 += (leftMap[a] * leftMap[b] * 1 * rightMap[b] * rightCCount) % MOD
# (b c) a (a b)
invalidCase2 += (leftMap[b] * leftCCount * 1 * rightMap[a] * rightMap[b]) % MOD
# (b b) a (a b)
invalidCase2 += (comb(leftMap[b], 2) * 1 * rightMap[a] * rightMap[b]) % MOD
# (a b) a (b b)
invalidCase2 += (leftMap[a] * leftMap[b] * 1 * comb(rightMap[b], 2)) % MOD
uniqueMiddleModes += total - invalidCase1 - invalidCase2
return uniqueMiddleModes % MOD
solved sweep line algo problems using sorted map, why sorted map is not working in this problem 3....
what was lofi at start?