LEETCODE SOLUTIONS

  Combination Sum Given an array of  distinct  integers  candidates  and a target integer  target , return  a list of all  unique combinations  of  candidates  where the chosen numbers sum to  target .  You may return the combinations in  any order . The  same  number may be chosen from  candidates  an  unlimited number of times . Two combinations are unique if the frequency of at least one of the chosen numbers is different. It is  guaranteed  that the number of unique combinations that sum up to  target  is less than  150  combinations for the given input.   Example 1: Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations. Example 2: Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] Example 3: Input: candidates = [2], target = 1 Output: []   Constraints: 1 <= candidates.length <=

  Search in Rotated Sorted Array There is an integer array  nums  sorted in ascending order (with  distinct  values). Prior to being passed to your function,  nums  is  possibly rotated  at an unknown pivot index  k  ( 1 <= k < nums.length ) such that the resulting array is  [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]  ( 0-indexed ). For example,  [0,1,2,4,5,6,7]  might be rotated at pivot index  3  and become  [4,5,6,7,0,1,2] . Given the array  nums   after  the possible rotation and an integer  target , return  the index of  target  if it is in  nums , or  -1  if it is not in  nums . You must write an algorithm with  O(log n)  runtime complexity.   Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Example 3: Input: nums = [1], target = 0 Output: -1   Constraints: 1 <= nums.length <= 5000 -10 4  <= nums[i] <= 10 4 All values of  nums  are  unique . nums  is a

Merge k Sorted Lists You are given an array of  k  linked-lists  lists , each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.   Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 Example 2: Input: lists = [] Output: [] Example 3: Input: lists = [[]] Output: [] class Solution : def mergeKLists ( self, lists: List[Optional[ListNode]] ) -> Optional[ListNode]: if not lists or len (lists) == 0 : return None while len (lists) > 1 : ml = [] for i in range ( 0 , len (lists), 2 ): l1 = lists[i] l2 = lists[i+ 1 ] if (i+ 1 ) < len (lists) else None ml.append(self.mergeTwoLists(l1,l2)) lists

  21 .  Merge Two Sorted Lists You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. class Solution:     def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:         d = ListNode()         p = d                  while l1 and l2 :             if l1.val < l2.val :                 p.next = l1                 l1 = l1.next             else :                 p.next = l2                 l2 = l2.next             p = p.next                          if l1:             p.next = l1         else :             p.next = l2                  return d.next Explaination :

  Valid Parentheses Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. class Solution:     def isValid(self, s: str) -> bool:         stack = []         hm = {             ")" : "(",             "]" : "[",             "}" : "{"         }                  for p in s:             if p in hm :                 if stack and stack[-1] == hm[p]:                     stack.pop()                 else :                     return False             else :                 stack.append(p)                              return True if not stack else False              Explaination :

Given the  head  of a linked list, remove the  n th  node from the end of the list and return its head.   Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1] class Solution:     def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:         d = ListNode (0, head)         l = d         r = head                  while n>0 and r :             r = r.next             n -= 1                      while r:             l = l.next             r = r.next                      #delete         l.next = l.next.next         return d.next Explaination :  

Given an integer array nums, return all the triplets  [nums[i], nums[j], nums[k]]  such that  i != j ,  i != k , and  j != k , and  nums[i] + nums[j] + nums[k] == 0 . Notice that the solution set must not contain duplicate triplets.   Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].  Notice that the order of the output and the order of the triplets does not matter. class Solution:     def threeSum(self, nums: List[int]) -> List[List[int]]:         ans = []         nums.sort()                  for i,a in enumerate(nums):             if i>0 and a == nums[i-1]:                 continue                              l, r = i+1, len(nums)-1             while l<r:                 tsum = a + nums[l] + nums[r]                 if tsum > 0:            

  You are given an integer array   height   of length   n . There are   n   vertical lines drawn such that the two endpoints of the   i th   line are   (i, 0)   and   (i, height[i]) . Find two lines that together with the x-axis form a container, such that the container contains the most water. Return  the maximum amount of water a container can store . Notice  that you may not slant the container.   Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. class Solution:     def maxArea(self, height: List[int]) -> int:         # ans = 0         # for l in range(len(height)):         #     for r in range(l+1, len(height)):         #         ar = (r-l) * min(height[l],height[r])         #         ans = max(ans, ar)         # return ans                  ans = 0         l, r = 0, len(height)-1                  while l<r:    

  Given a string   s , return   the longest palindromic substring   in   s .   Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. Example 2: Input: s = "cbbd" Output: "bb" class Solution:     def longestPalindrome(self, s: str) -> str:         p = ""         plen = 0                  for i in range(len(s)):             #odd check             l,r = i,i             while l>=0 and r<len(s) and s[l]==s[r]:                 if (r-l+1)>plen:                     p = s[l:r+1]                     plen=r-l+1                   l-=1                 r+=1                              #even check             l,r = i,i+1             while l>=0 and r<len(s) and s[l]==s[r]:                 if (r-l+1)>plen:                     p = s[l:r+1]                     plen=r-l+1                   l-=1                 r+=1         return p                               Explaination :

Given a string s, find the length of the longest substring without repeating characters. class Solution:     def lengthOfLongestSubstring(self, s: str) -> int:         charSet = set()         left = 0         ans = 0         for right in range(len(s)):             while s[right] in charSet:                 charSet.remove(s[left])                 left+=1             charSet.add(s[right])             ans = max(ans, right-left+1)         return ans                  Explained :

1. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order class Solution:     def twoSum(self, nums: List[int], target: int) -> List[int]:         hashmap = {} #  val : index                  for i,n in enumerate(nums):             diff = target - n             if diff in hashmap:                 return [hashmap[diff],i]             hashmap[n]=i         return Explained :