classSolution:defmaxArea(self,height:List[int])->int:"""
sorted_indices = sorted(range(len(height)),
key=lambda index: height[index], reverse=True)
maxArea = 0
print(sorted_indices)
for i, s in enumerate(sorted_indices):
for j, t in enumerate(sorted_indices):
if j >= i:
container_height = min(height[s],height[t])
area = abs(s-t) * container_height
if area > maxArea:
maxArea = area
return maxArea
# Time Limit Exceeded | 54/65 testcases passed
"""# two pointer approachmaxArea=0leftPointer=0rightPointer=len(height)-1whileleftPointer!=rightPointer:area=min(height[leftPointer],height[rightPointer])*abs(leftPointer-rightPointer)ifarea>maxArea:maxArea=areaifheight[leftPointer]<height[rightPointer]:leftPointer+=1else:rightPointer-=1returnmaxArea
#from itertools import combinations"""
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
def twoSum(numbers: List[int], target: int) -> List[List[int]]:
res = []
if not numbers:
return []
leftPointer, rightPointer = 0, len(numbers) - 1
while leftPointer < rightPointer:
status = numbers[leftPointer] + numbers[rightPointer]
if status < target:
leftPointer += 1
elif status > target:
rightPointer -= 1
else:
res.append([leftPointer + 1, rightPointer + 1])
# skip duplicates on BOTH sides
lv, rv = numbers[leftPointer], numbers[rightPointer]
while leftPointer < rightPointer and numbers[leftPointer] == lv:
leftPointer += 1
while leftPointer < rightPointer and numbers[rightPointer] == rv:
rightPointer -= 1
return res
#combinations_of_3 = list(combinations(nums,3))
#print(len(combinations_of_3))
#out = []
#for c in combinations_of_3:
# if sum(c) == 0:
# if sorted(c) not in out:
# out.append(sorted(c))
#
#return out
nums.sort()
out = []
for i,n in enumerate(nums):
if n>0:
break # sorted, so a positive number means we can never get to 0
if i>0 and n == nums[i-1]: # skip if same as previous
continue
print(nums[i+1:])
idxs = twoSum(nums[i+1:], 0-n)
if idxs:
for idx in idxs:
out.append([n, nums[i+idx[0]], nums[i+idx[1]]])
return out
"""classSolution:defthreeSum(self,nums:List[int])->List[List[int]]:deftwoSum(numbers:List[int],target:int)->List[List[int]]:res:List[List[int]]=[]ifnotnumbers:returnresleftPointer,rightPointer=0,len(numbers)-1whileleftPointer<rightPointer:status=numbers[leftPointer]+numbers[rightPointer]ifstatus<target:leftPointer+=1elifstatus>target:rightPointer-=1else:# record (keeping your 1-based indexing)res.append([leftPointer+1,rightPointer+1])# skip duplicates on BOTH sideslv,rv=numbers[leftPointer],numbers[rightPointer]whileleftPointer<rightPointerandnumbers[leftPointer]==lv:leftPointer+=1whileleftPointer<rightPointerandnumbers[rightPointer]==rv:rightPointer-=1returnresnums.sort()out:List[List[int]]=[]fori,ninenumerate(nums):ifn>0:break# remaining numbers are positive → no more tripletsifi>0andn==nums[i-1]:continue# skip duplicate anchorsidxs=twoSum(nums[i+1:],-n)# search suffixforl1,r1inidxs:# l1/r1 are 1-based within the suffixout.append([n,nums[i+l1],nums[i+r1]])returnout
classSolution:deffirstMissingPositive(self,nums:List[int])->int:"""shockingly this code is accepted despite the O(nlogn) tc and O(n) sc
# will remove this assumption later:
nums = sorted(list(set(nums)))
one = False
location = 0
for i, num in enumerate(nums):
if num == 1:
one = True
location = i
if one == False:
return 1
# check subsequent:
j = location
spi = 1
while j < len(nums):
if nums[j] == spi:
spi += 1
j += 1
continue
return spi
return spi
"""# cyclic sort:n=len(nums)# place each positive integer at the respective index within numsforiinrange(n):while1<=nums[i]<=nandnums[nums[i]-1]!=nums[i]:nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]# swap# linear search for first discrepancyforiinrange(n):ifnums[i]!=i+1:returni+1# returns discrep# or returns n + 1returnn+1
classSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:"""
#O(mnlogn) sorting bruteforce
print(strs)
base = []
for string in strs:
base.append("".join((sorted(string))))
print(base)
# find indices that are all the same
idxs = []
marked = []
for i, word1 in enumerate(base):
i_likes = []
for j, word2 in enumerate(base):
if word1 == word2 and i <= j and j not in marked:
marked.append(j)
i_likes.append(j)
if i_likes:
idxs.append(i_likes)
print(idxs)
# replace indices with words:
ans = []
for tup in idxs:
sublist = []
for idx in tup:
sublist.append(strs[idx])
ans.append(sublist)
return ans
"""# hashmap: O(m*n)hash={}forsinstrs:count=[0]*26forcins:count[ord(c)-ord("a")]+=1key=tuple(count)ifkeyinhash:hash[key].append(s)else:hash[key]=[s]returnlist(hash.values())
// function to insert value m at position n in array a by shifting the array
voidinsert(int*a,intm,intn,intl){printf("debug %d %d %d\n",m,n,l);inttemp=a[l-1];for(inti=l-1;i>n;i--){a[i]=a[i-1];}a[0]=temp;a[n]=m;}voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){intp1=m-1;intp2=n-1;for(intp=m+n-1;p>=0;p--){if(p2<0){break;}else{nums1[p]=(p1>=0&&nums1[p1]>nums2[p2])?nums1[p1--]:nums2[p2--];}}}/*
int offset = 0;
for (int i = 0; i < m; i++) {
for (int j = 0 + offset; j < n; j++) {
// if less than first element
if (i == 0 && nums1[i] >= nums2[j]) {
printf("insert start\n");
insert(nums1, nums2[j], i, m + n);
offset++;
break;
}
// if greater than last element
else if (i == m - 1 && nums1[i] <= nums2[j]) {
printf("insert end\n");
insert(nums1, nums2[j], i, m + n);
offset++;
break;
}
else if (nums1[i] <= nums2[j] && (i + 1 < m && nums1[i+1] >= nums2[j])){ // belongs in middle
printf("insert middle\n");
insert(nums1, nums2[j], i+1, m + n);
offset++;
break;
}
}
}
}
*/
classSolution:deflongestConsecutive(self,nums:List[int])->int:numSet=set(nums)# O(n) average time, O(n) spacelongest=0forninnumSet:# ← iterate uniques to avoid duplicate re-walks# check if it is the start of the sequenceif(n-1)notinnumSet:length=0while(n+length)innumSet:length+=1longest=max(length,longest)returnlongest
classSolution:defmajorityElement(self,nums:List[int])->int:"""my naive soln
d = {x:nums.count(x) for x in nums}
a, b = d.keys(), d.values()
max_value = max(b)
max_index = list(b).index(max_value)
return (list(a)[max_index])
# o(n^2) because we run o(n) count on each x
""""""
candidate = 0
count = 0
# phase 1: find candidate
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
"""count={}# dictionary.res,maxCount=0,0forninnums:count[n]=1+count.get(n,0)res=nifcount[n]>maxCountelseresmaxCount=max(count[n],maxCount)returnres
classSolution:defisHappy(self,n:int)->bool:"""
# N is input size, n is number of digits of N
visited = set() # O(log n)
while n != 1:
m = 0
if n in visited: # O(1)
return False
digits = [int(digit) for digit in str(n)] # O(log n)
for digit in digits: # O(log n)
m += digit*digit
visited.add(n)
n = m
return True
"""# Time Complexity: O(log n) - number of digits in n# Space Complexity: O(log n) - size of visited setvisited:set[int]=set()# Track numbers we've seen to detect cycleswhilennotinvisited:visited.add(n)ifn==1:returnTrue# Calculate sum of squared digitscurrent_sum:int=0whilen>0:digit:int=n%10current_sum+=digit*digitn//=10n=current_sumreturnFalse# We found a cycle, number is not happy
classSolution:defproductExceptSelf(self,nums:List[int])->List[int]:"""o(n^2)
res = [1] * len(nums)
for i,num in enumerate(nums):
for j in range(len(nums)):
res[j] *= (num if i !=j else 1)
return res
""""""better code, but still not fast enough
# calculate prefix
prefix = [0] * (len(nums) + 2)
prefix[0], prefix[len(nums)+1] = 1,1
for i in range(len(nums)):
prefix[i+1] = (nums[i] * prefix[i])
print(prefix)
# calculate postfix
postfix = [0] * (len(nums) + 2)
postfix[0], postfix[len(nums)+1] = 1,1
print(postfix)
for i in reversed(range(len(nums))):
postfix[i+1] = (nums[i] * postfix[i+2])
print(postfix)
# multiply prefix with postfix for each n
res = [0] * len(nums)
for i in range(len((nums))):
print(res)
res[i] = prefix[i] * postfix[i+2]
return res
"""# the issue above was space complexity.# we are going to update the result array for both prefix and postfixres=[1]*len(nums)# prefix loop:foriinrange(1,len(nums)):res[i]=nums[i-1]*res[i-1]postfix=1forjinreversed(range(len(nums)-1)):postfix*=nums[j+1]res[j]*=postfixreturnres
fromcollectionsimportdeque#from typing import ListclassSolution:defmaxSlidingWindow(self,nums:List[int],k:int)->List[int]:"""anki
q = deque()
left = right = 0
def slide_right():
nonlocal right
while q and nums[q[-1]] < nums[right]:
q.pop()
q.append(right)
right += 1
def slide_left():
nonlocal left
left += 1
if q and left > q[0]:
q.popleft()
result = []
while right < k:
slide_right()
result.append(nums[q[0]])
while right < len(nums):
slide_right()
slide_left()
result.append(nums[q[0]])
return result
"""output=[]l=r=0q=deque()whiler<len(nums):whileqandnums[q[-1]]<nums[r]:q.pop()q.append(r)# remove left val from windowifl>q[0]:q.popleft()if(r+1)>=k:output.append(nums[q[0]])l+=1r+=1returnoutput"""naive
left = 0
right = k
result = []
N = len(nums)
while right <= N:
result.append(max(nums[left:right]))
left += 1
right += 1
return result
"""
deftopKFrequent(nums:List[int],k:int)->List[int]:"""
d = DefaultDict(int)
for item in nums:
d[item] += 1
l = list(sorted(d.items(), key = lambda x: x[1],reverse=True))
return [x[0] for x in l[:k]]
"""# O(nlogn), dominated by the sorting# O(n)################################### #################################### O(n) solution via bucket sort:# 1. count frequencies O(n)frequencies=DefaultDict(int)# lookup failures will be populated with a default int of 0foriteminnums:frequencies[item]+=1n=len(nums)# 2. create buckets (index = frequency) O(n)buckets=[[]for_inrange(n+1)]fornum,frequencyinfrequencies.items():buckets[frequency].append(num)# 3. collect k most frequent items O(n)result=[]whilen>-1andk>0:ifbuckets[n]:result.append(buckets[n].pop())k-=1else:n-=1returnresult
importitertoolsclassSolution:deffindAnagrams(self,s:str,p:str)->List[int]:"""
positions = set()
perms = [''.join(q) for q in itertools.permutations(p)]
for perm in perms:
for i in range(len(s)):
index = s.find(perm, i)
if index == -1:
continue
if index not in positions:
positions.add(index)
i = index + 1
return list(positions)
"""iflen(p)>len(s):return[]pCount,sCount={},{}foriinrange(len(p)):pCount[p[i]]=1+pCount.get(p[i],0)sCount[s[i]]=1+sCount.get(s[i],0)res=[0]ifsCount==pCountelse[]l=0forrinrange(len(p),len(s)):sCount[s[r]]=1+sCount.get(s[r],0)sCount[s[l]]-=1ifsCount[s[l]]==0:sCount.pop(s[l])l+=1ifsCount==pCount:res.append(l)returnres
classSolution:deffindDisappearedNumbers(self,nums:List[int])->List[int]:missing=[]"""
hashmap = {} for num in nums:
hashmap[num] = 1
for i in range(1, len(nums)+1):
if i not in hashmap:
missing.append(i)
return missing
"""uniques=set(nums)foriinrange(1,len(nums)+1):ifinotinuniques:missing.append(i)returnmissing
importitertoolsclassSolution:defcheckInclusion(self,s1:str,s2:str)->bool:"""
if len(s1) == len(s2) and set(s1) != set(s2): return False
perms = [''.join(q) for q in itertools.permutations(s1)]
res = False
for perm in perms:
print(perm)
index = s2.find(perm, 0)
if index != -1:
res = True
return res
"""n1=len(s1)n2=len(s2)ifn1>n2:returnFalses1_counts=[0]*26s2_counts=[0]*26foriinrange(n1):s1_counts[ord(s1[i])-ord('a')]+=1s2_counts[ord(s2[i])-ord('a')]+=1ifs1_counts==s2_counts:returnTrueforiinrange(n1,n2):s2_counts[ord(s2[i])-ord('a')]+=1s2_counts[ord(s2[i-n1])-ord('a')]-=1ifs1_counts==s2_counts:returnTruereturnFalse
1365. How Many Numbers Are Smaller Than the Current Number#
classSolution:defsmallerNumbersThanCurrent(self,nums:List[int])->List[int]:"""
counts = []
for a in nums:
count = 0
for b in nums:
if a != b and b < a:
count += 1
counts.append(count)
return counts
"""mynums=sorted(nums)iteration=-1hashMap={}foriteminmynums:iteration+=1ifiteminhashMap:continuehashMap[item]=iterationreturn[hashMap[item]foriteminnums]
This front matter follows the pattern of other files in the blog directory, includes math support for the calculations, and reflects the content about birthday prize money analysis with mathematical calculations.
Years
Prize
Recipient
21
50,20
Aarav, Jisu
22
50,100
Erick, Sarro
23
100,150
Unclaimed, Aarav
24
300
Unclaimed
rule: take the most expensive offering and then double it:
21: 50,20 | 50
22: 50, 100 | 100
23: 100, 150 |