Posts

160. Intersection of Two Linked Lists

Image
Given the heads of two singly linked-lists  headA  and  headB , return  the node at which the two lists intersect . If the two linked lists have no intersection at all, return  null . Note: Has an easy solution, but O(N) good solution is Medium. a + c + b = b + c + a def getIntersectionNode ( headA : ListNode , headB : ListNode ):             pA = headA     pB = headB     while pA != pB :         pA = headB if pA is None else pA .next         pB = headA if pB is None else pB .next     return pA     # Note: In the case lists do not intersect, the pointers for A and B     # will still line up in the 2nd iteration, just that here won't be     # a common node down the list and both will reach their respective ends     # at the same time. So pA will be NULL in that case
Post a Comment
Read more

208. Implement Trie (Prefix Tree)

class Trie :        class Node :         def __init__ ( self ):             self . children = {}             self . isEnd = False     def __init__ ( self ):         self . root = Trie . Node ()             def insert ( self , word : str ):         p = self . root                 for ch in word :             if ch not in p . children :                 p . children [ ch ] = Trie . Node ()             p = p . children [ ch ]         p . isEnd = True     def search ( self , word : str ):         p = self . root                 for ch in word :       ...
Post a Comment
Read more

347. Top K Frequent Elements

Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] def topKFrequent ( self , nums : List [ int ], k : int ):             freq = Counter ( nums )         return heapq . nlargest ( k , freq . keys (), key = freq . get )    
Post a Comment
Read more

674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers  nums , return  the length of the longest  continuous increasing subsequence  (i.e. subarray) . The subsequence must be  strictly  increasing. A  continuous increasing subsequence  is defined by two indices  l  and  r  ( l < r ) such that it is  [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]  and for each  l <= i < r ,  nums[i] < nums[i + 1] . def findLengthOfLCIS ( nums : List [ int ]):         ans = start = 0         for i in range ( len ( nums )):         if i and nums [ i ] <= nums [ i - 1 ]:             start = i         ans = max ( ans , i - start + 1 )             return ans      
Post a Comment
Read more

139. Word Break

Given a string  s  and a dictionary of strings  wordDict , return  true  if  s  can be segmented into a space-separated sequence of one or more dictionary words. Note  that the same word in the dictionary may be reused multiple times in the segmentation.   Example: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".   def wordBreak ( s : str , wordDict : List [ str ]):             word_set = set ( wordDict )     dp = [ False ] * ( len ( s ) + 1 )     dp [ 0 ] = True     for i in range ( 1 , len ( s ) + 1 ):         for j in range ( i ):             if dp [ j ] and s [ j : i ] in word_set :                 dp [ i ] = True                 break   ...
Post a Comment
Read more

907. Sum of Subarray Minimums

Given an array of integers arr, find the sum of  min(b) , where  b  ranges over every (contiguous) subarray of  arr . Since the answer may be large, return the answer  modulo   10 9  + 7 .   Example: Input: arr = [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17. def sumSubarrayMins ( self , arr : List [ int ]):             L = len ( arr ), total = 0 , M = ( 10 ** 9 + 7 )         left =  [ i + 1 for i in range ( L )]     right = [ L - i for i in range ( L )]         p = [], n = []         for i in range ( L ):                 while p :                             if p [- 1 ][ 0 ] <= arr [...
Post a Comment
Read more

215. Kth Largest Element in an Array

Given an integer array  nums  and an integer  k , return  the   k th   largest element in the array . Note that it is the  k th  largest element in the sorted order, not the  k th  distinct element. You must solve it in  O(n)  time complexity.   Example: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 def findKthLargest ( nums : List [ int ], k : int ):             heap = nums [: k ]     heapq . heapify ( heap )             N = len ( nums )     for i in range ( k , N ):                     heapq . heappush ( heap , nums [ i ])                               heapq . heappop ( heap )             return heap [ 0 ]
Post a Comment
Read more