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]