Leetcode BLIND-75

Question 1

217. Contains Duplicate ( Easy )

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct

Example 1:

Input: nums = [1,2,3,1]
Output: true

Answer 1

• Convert given array into set ( it will remove duplicates)
• Again convert that set into arrayset_nums = list(set(nums))
• if both original array and set array has same length means there were no duplicates present
• so return false` if len(nums) == len(set_nums): return False`
• else means they differ in length so there were duplicates present` return True`

Question 2

242. Valid Anagram ( Easy )

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Answer 2

• Base Case:if len(s) != len(t): return False
• Create two Hashmaps
• Iterate and store char in string as key and count as value
• return True if both dict are same else false.return countS == countT

Code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t): return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)

        return countS == countT

Question 3

1. Two Sum ( Easy )

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Explanation:
nums[0] + nums[1] == 9, we return [0, 1]

Answer 3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i in range(len(nums)):
            if (target- nums[i]) in d: return [i, d[target-nums[i]]]
            d[nums[i]] = i
        

Question 4

49. Group Anagrams ( Medium )

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: 
strs = ["eat","tea","tan","ate","nat","bat"]

Output: 
[["bat"],["nat","tan"],["ate","eat","tea"]]

Answer 4

• have a defaultdict of type list

   ` d = defaultdict(list)`

• iterate through array of strings and map tuple of sorted string as key with value as list of all the strings

    for s in strs:
               d[tuple(sorted(s))].append(s)

• lastly return all values in a string

   ` return d.values()`

Code

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)

        for s in strs:
            d[tuple(sorted(s))].append(s)
        
        return d.values()

Question 5

347. Top K Frequent Elements ( Medium)

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Answer 5

Code

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for n in nums:
            count[n] = 1 + count.get(n, 0)
        for n, c in count.items():
            freq[c].append(n)

        res = []
        for i in range(len(freq) - 1, 0, -1):
            for n in freq[i]:
                res.append(n)
                if len(res) == k:
                    return res

        # O(n)

Question 6

238. Product of Array Except Self ( Medium)

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Answer 6

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * (len(nums))

        for i in range(1, len(nums)):
            res[i] = res[i-1] * nums[i-1]
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        return res        

Question 7

125. Valid Palindrome ( Easy )

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Answer 7

Code

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join(c for c in s if c.isalnum()).lower()
        return s == s[::-1]
        

Another Simple Example of Code

class Solution:
    def isPalindrome(self, s: str) -> bool:

        new_string = ''

        for c in s:
            if c.isalnum():
                new_string += c
        
        new_string = new_string.lower()
        
        return new_string == new_string[::-1]

        

Question 8

15. 3Sum (Medium)

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.

Answer 8

• Sort the array
• Intialise res array to return later
• Iterate using enumerate function, as we will need number as well as index here
• If its not the first number and is equal to previous number then continue as its will give us the same/duplicate pairs again

if i > 0 and nums[i] == nums[i-1]: continue

• Rest of the problem is similar to Two Sum ll
• Initialise two pointersl, r = i+1, len(nums)-1
• In the else part of code while l and r are not crossing each other and while number is equal to previous number, we will keep incresing the left pointer as we will keep getting the duplicates
• Lastly we will return the res array

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        
        for i, ele in enumerate(nums):
            if i > 0 and nums[i] == nums[i-1]: continue
             
            l, r = i+1, len(nums)-1
            while l < r:
                threesum = ele + nums[l] + nums[r]
                if threesum > 0: r -= 1
                elif threesum < 0: l += 1
                else:
                    res.append([ele, nums[l], nums[r]])
                    l += 1 
                    while l < r and nums[l] == nums[l-1]: l += 1
        
        return res 

Question 9

11. Container With Most Water (Medium)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith 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.

Example 1:

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.

Example 2:

Input: height = [1,1]
Output: 1

Answer 9

• Two pointer method
• At each point, curr_arera is min of height and distance between r and lcurrArea = min(height[l], height[r])*(r-l)maxArea = max(maxArea, currArea)

Code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea = 0
        l = 0 
        r = len(height)-1
        
        while l <= r:
            currArea = min(height[l], height[r])*(r-l)
            maxArea = max(maxArea, currArea)

            if height[l] < height[r]: l += 1
            else: r -= 1
        
        return maxArea

Question 10

121. Best Time to Buy and Sell Stock (Easy)

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Answer 10

• cheap = prices[0]
• max profit maxP is 0
• iterate, if curr prices[i] is less than cheap then cheap = prices[i]
• current profit currP is prices[i] - cheap and
• maxP is max(maxP, currP)
• lastly return max profit maxP

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cheap = prices[0]
        maxP = 0

        for i in range(1, len(prices)):
            if prices[i] < cheap:
                cheap = prices[i]
            
            currP = prices[i] - cheap 
            maxP = max(maxP, currP)
        
        return maxP
        

Question 11

20. Valid Parentheses (Easy)

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Answer 11

• for every char in string if char is in "([{" then will add to stack
• elif char in string is ")]}" and if stack’s last element is not "([{" resp or if stack is empty then return False and pop the element from stack
• lastly if stack is empty then return True else return False

Code

class Solution:
    def isValid(self, s: str) -> bool:
        st = []

        for c in s:
            if c in '([{':
                st.append(c)

            elif c is ')':
                if (not st or st[-1] != '('): return False
                st.pop()
            
            elif c is']':
                if (not st or st[-1] != '['): return False
                st.pop()
            
            elif c is'}':
                if (not st or st[-1] != '{'): return False
                st.pop()
        
        if not st: return True
        return False
            
        

Question 12

153. Find Minimum in Rotated Sorted Array (Medium)

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Answer 12

• mid = l + (r-l) // 2 ( so that left + right doesn’t go above 32 bit Integer )
• Do Binary Search and return nums[l]

Code

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        while l < r:
            mid = l + (r-l) // 2
            if nums[mid] < nums[r]: r = mid
            else: l = mid+1
        return nums[l]
        

Question 13

33. Search in Rotated Sorted Array (Medium)

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

Answer 13

• Binary Search two pointers l and r
• ` if nums[mid] == target: return mid `
• If nums[mid] is greater than or equal to nums[l] then left part is sorted so now search in left part
• If target is greater than nums[mid] or if less than nums[l] and nums[mid
  then search in right part. l = mid+1
• In the else section right part is sorted
• If target is less than nums[mid] or target is greater than nums[mid] and target is gretaer than nums[r] then search in left part. i.e r = mid-1
• Lastly return -1 as element is not found.

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1

        while l <= r:
            m = (l+r) // 2 
            #middle element

            if nums[m] == target: return m 
            #target found

            elif nums[m] >= nums[l]:

                #left part is sorted 
                if target > nums[m] or (target < nums[l] and target < nums[m]):
                    l = m+1
                else: r = m-1
                
            else:

                #right part is sorted
                if target < nums[m] or ( target > nums[m] and target > nums[r]):
                    r = m-1
                else: l = m+1
            
        return -1

        

Question 14

206. Reverse Linked List ( Easy )

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Answer 14

Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head

        prev = None
        curr = head

        while curr:
            next = curr.next

            curr.next = prev
            prev = curr
            curr = next
        
        return prev
        

Question 15

21. Merge Two Sorted Lists ( Easy )

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into 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.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Answer 15

• Create curent and dummy Node as ListNode(0)
• while both l1 and l2 is not empty, we will iterate and current.next will be smaller value
• Lastly to add reamining values from list1 and list2 we will do
• current.next = l1 or l2
• return dummy.next

Code

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        current = dummy = ListNode(0)

        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1 
                l1 = l1.next 

            else:
                current.next = l2 
                l2 = l2.next 

            current = current.next 

        current.next = l1 or l2 
        
        return dummy.next 

Question 16

141. Linked List Cycle ( Easy)

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to.
Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Answer 16

Code

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        while fast and fast.next:

            slow = slow.next
            fast = fast.next.next

            if slow == fast: return True
        
        return False

Question 17

23. Merge k Sorted Lists ( Hard )

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

Answer 17

• Base Case is that if len of lists is 0 or 1 then we will return None or lists[0] resp.
• mid = len(lists) // 2
• We will Recursively call the given function on left and right part
• Then we will return the MergeTwoLists function on left and right part.
• In the code below the return, we have defined mergeTwoLists which is excat code of Merge Two Linked Lists Problem

Code

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        #base case
        if len(lists) == 0: return None
        if len(lists) == 1: return lists[0]

        mid = len(lists) // 2

        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])

        #call defined function on left and right two merge them
        return self.MergeTwoLists(left, right)

    #define function to merge two linked lists into one
    def MergeTwoLists(self, l1, l2):
        new = curr = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next   
            curr = curr.next
        
        curr.next = l1 or l2

        return new.next
    

Question 18

226. Invert Binary Tree ( Easy )

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Answer 18

• Base Case: if root is empty or root.left and root.right is empty then we will return the root.
• We will assign root.left to root.right and vice-versa
• We will Recursively call the function on left and right subtree
• return the root

Code

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root or (not root.left and not root.right): return root

        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Question 19

104. Maximum Depth of Binary Tree ( Easy )

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Answer 19

• ` if not root: return 0`
• 1 + max of Two Recursive Functions ( left and right )

Code

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0 
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Question 20

100. Same Tree ( Easy )

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Answer 20

• If both root are null then true
• if one of the root is null then false
• if values of root is not same then false
• return AND of given function for p.left, q.left and p.right, q.right

Code

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q: return True
        if not p or not q: return False
        if p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Question 21

572. Subtree of Another Tree ( Easy )

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Answer 21

Code

class Solution:
    def isSubtree(self, s: Optional[TreeNode], t: Optional[TreeNode]) -> bool:
        if not t: return True
        if not s: return False

        if self.SameTree(s, t): return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    def SameTree(self, s, t):
        if not s and not t: return True
        if not s or not t: return False
        if s.val != t.val: return False
        return self.SameTree(s.left, t.left) and self.SameTree(s.right, t.right)

Question 22

235. Lowest Common Ancestor of a Binary Search Tree ( Medium )

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.

Answer 22

• LCA of two Node is basically lowest common Node between them.
• We will take curr as root Node and if p and q both are greater than curr then we will go to right
  curr = curr.right ( As this is the Binary Search Tree )
• else if both p and q are smaller than curr then we will go the left.
• In the else part, means one value is less than curr and one value is greter than curr in such case LCA is always root or here curr Node so we will return curr

Code

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        curr = root
        while curr:
            # both are greater
            if p.val > curr.val and q.val > curr.val:
                curr = curr.right # to go the right 
            elif p.val < curr.val and q.val < curr.val:
                # both are less so go left 
                curr = curr.left 
            else:
                # one on the left and one on the right so LCA is root 
                return curr

        

Question 23

102. Binary Tree Level Order Traversal ( Medium )

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Answer 23

Algorithm:

• Initialize an empty queue.
• If the root is not null, add it to the queue.
• While the queue is not empty, repeat steps 4-6.
• Get the size of the queue and initialize an empty list to store the nodes of the current level.
• Loop through the elements of the current level and add them to the list.
• For each element of the current level, add its children to the queue.
• Add the current level list to the result list.
• Return the result list.

Code

class Solution:
   def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

    queue = []
    result = []

    if root:
        queue.append(root)

    while queue:

        size = len(queue)
        level = []

        for i in range(size):
            node = queue.pop(0)
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)
    
    return result

Question 24

98. Validate Binary Search Tree ( Medium )

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true

Answer 24

• We will define helper function with parameter as root, left and right where left is set to -ve infinity and right is set to +ve infinity
• Base case of helper function is if root is empty then return True
• if root.val is less than l or is greater than r then its not valid BST so return False
• In the helper function we will recursively call the function or root.left and root.right
• Lastly we will call the helper function on root Node

Code

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def helper(root, l = float('-inf'), r = float('inf')):
            if not root: return True
            val = root.val
            if val <= l or val >= r: return False
            return helper(root.left, l, val) and helper(root.right, val, r)
        return helper(root)
        

Question 25

**230. Kth Smallest Element in a BST ( Medium )** Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. Example 1: ``` Input: root = [3,1,4,null,2], k = 1 Output: 1 ```

Answer 25

- We will have `stack` and `curr` set as root - `while true` and `while curr`, we will add `curr` to the `stack` and ` curr = curr.left ` - ` node = stack.pop` and `k -= 1` - If at any point `k == 0` ( as we are dec the k ) then, return `node.val` as it will be `kth` smallest element in BST - `curr = node.right ` **Code** ``` class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: if not root: return stack = [] curr = root while True: while curr: stack.append(curr) curr = curr.left node = stack.pop() k -= 1 if k == 0: return node.val curr = node.right ```

Question 26

**105. Construct Binary Tree from Preorder and Inorder Traversal ( Medium )** Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. Example 1: ``` Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] ``` Example 2: ``` Input: preorder = [-1], inorder = [-1] Output: [-1] ```

Answer 26

# Definition for a binary tree node. **Code** ``` class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: inmap = {} for i, ele in enumerate(inorder): inmap[ele] = i def buildhelper(prestart, preend, instart, inend): if prestart > preend: return rootval = preorder[prestart] root = TreeNode(rootval) rootindex = inmap[rootval] linstart = instart linend = rootindex -1 rinstart = rootindex + 1 rinend = inend lprestart = prestart + 1 lpreend = linend - linstart + lprestart rprestart = lpreend+1 rpreend = preend root.left = buildhelper(lprestart, lpreend, linstart, linend) root.right = buildhelper(rprestart, rpreend, rinstart, rinend) return root return buildhelper(0, len(preorder)-1, 0, len(inorder)-1) ```

Question 27

**39. Combination Sum ( Medium )** 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. The test cases are generated such 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]] ```

Answer 27

**Code** ``` class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: # define a backtracking fucntion def backtrack(start, target, path, res): if target < 0: return if target == 0: res.append(path) return for i in range(start, len(candidates)): backtrack(i, target-candidates[i], path+[candidates[i]], res) res = [] candidates.sort() backtrack(0, target, [], res) return res ```

Question 28

**79. Word Search ( Medium )** Given an `m x n` grid of characters `board` and a string `word`, return `true` if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: ``` Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true ``` Example 2: ``` Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true ```

Answer 28

**Code** ``` class Solution: def exist(self, board: List[List[str]], word: str) -> bool: rows, cols = len(board), len(board[0]) res = [] path = set() def dfs(r,c,i): if i == len(word): return True if r < 0 or c < 0 or r >= rows or c >= cols or word[i] != board[r][c] or (r,c) in path: return False path.add((r,c)) res = ( dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or dfs(r, c+1, i+1) or dfs(r, c-1, i+1) ) path.remove((r,c)) return res for r in range(rows): for c in range(cols): if dfs(r, c, 0): return True ```

Question 29

**200. Number of Islands ( Medium )** Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: ``` Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 ``` Example 2: ``` Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 ```

Answer 29

- base case `if not grid: return 0` - function to perform dfs - calculate len or row and column - varibale count to return later - visited matrix to keep track of visited elements - traverse through grid if any element is 1 and not visited then incerement the count and perform dfs on it. - lastly return the count. **Code** ``` class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == "0" or visited[i][j]: return visited[i][j] = True dfs(i+1, j) dfs(i-1, j) dfs(i, j+1) dfs(i, j-1) m, n = len(grid), len(grid[0]) count = 0 visited = [[False for _ in range(n)] for _ in range(m)] for i in range(m): for j in range(n): if grid[i][j] == '1' and not visited[i][j]: count += 1 dfs(i,j) return count ```

Question 30

**70. Climbing Stairs ( Easy )** You are climbing a staircase. It takes ` n ` steps to reach the top. Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top? Example 1: ``` Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps ``` Example 2: ``` Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step ```

Answer 30

- Fibonacci way using `temp` **Code** ``` class Solution: def climbStairs(self, n: int) -> int: one, two = 1, 1 for i in range(n-1): temp = one one = one + two two = temp return one ```

Question 31

**198. House Robber ( Medium )** You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night.** Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight **without alerting the police**. Example 1: ``` Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. ``` Example 2: ``` Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12 ```

Answer 31

**Code** ``` class Solution: def rob(self, nums: List[int]) -> int: one, two = 0, 0 # [one, two, n, n+1, ....] # array actually will look like this ( for understanding ) for n in nums: temp = max(one+n, two) # to rob n th house , we can rob n + one but if we rob two then we cant rob n # as they are adjecent to each other. one = two two = temp # by the time we reach end, two is the max value we can rob return two ```

Question 32

**213. House Robber II ( Medium )** You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and **it will automatically contact the police if two adjacent houses were broken into on the same night.** Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight **without alerting the police**. Example 1: ``` Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses. ``` Example 2: ``` Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. ``` Example 3: ``` Input: nums = [1,2,3] Output: 3 ```

Answer 32

- Now we will just return max of both helper functions. - One excluding first value and other excluding last value - We will take max of three values as in case of array having only one element - helper function is bascially code for House Robber I - We will pass this helper function on entire array expect first and - Entire array except last as first and last house is adjecent. **Code** ``` class Solution: def rob(self, nums: List[int]) -> int: return max(nums[0], self.helper(nums[1:]), self.helper(nums[:-1])) def helper(self, nums): one, two = 0, 0 # [ one, two, n, n+1, ...] for n in nums: temp = max(one+n, two) one = two two = temp return two ```

Question 33

**5. Longest Palindromic Substring ( Medium )** 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" ```

Answer 33

**Code** ``` class Solution: def longestPalindrome(self, s: str) -> str: res = '' res_len = 0 for i in range(len(s)): # for palindrome of even length l, r = i, i while l >= 0 and r < len(s) and s[l] == s[r]: if (r-l+1) > res_len: res = s[l:r+1] res_len = r-l+1 l -= 1 r += 1 # for palindrome of odd length l, r = i, i+1 while l >= 0 and r < len(s) and s[l] == s[r]: if (r-l+1) > res_len: res = s[l:r+1] res_len = r-l+1 l -= 1 r += 1 return res ```

Question 34

**647. Palindromic Substrings ( Medium )** Given a string `s`, return the number of palindromic substrings in it. A string is a **palindrome** when it reads the same backward as forward. A **substring** is a contiguous sequence of characters within the string. Example 1: ``` Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". ``` Example 2: ``` Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". ```

Answer 34

**Code** ``` class Solution: def countSubstrings(self, s: str) -> int: res = 0 for i in range(len(s)): res += self.countp(s,i,i) res += self.countp(s,i,i+1) return res def countp(self, s, l, r): res = 0 while l >= 0 and r < len(s) and s[l] == s[r]: res += 1 l -= 1 r += 1 return res ```

Question 35

**62. Unique Paths ( Medium )** There is a robot on an `m x n` grid. The robot is initially located at the top-left corner (i.e., `grid[0][0]`). The robot tries to move to the bottom-right corner (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time. Given the two integers `m` and `n`, return the number of possible unique paths that the robot can take to reach the bottom-right corner. The test cases are generated so that the answer will be less than or equal to `2 * 10**9` Example 1: ``` Input: m = 3, n = 7 Output: 28 ``` Example 2: ``` Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down ```

Answer 35

**Code** ``` class Solution: def uniquePaths(self, m: int, n: int) -> int: #bottom additional row of all the ones oldrow = [1]*n for i in range(m-1): #for each row we are calculating newrow newrow = [1]*n #traverse through columns in reverse order excluding last column for j in range(n-2, -1, -1): #at each postion 'i' answer is answer at 'i+1' block of same row + answer #at ith position of bottom row newrow[j] = newrow[j+1] + oldrow[j] oldrow = newrow return oldrow[0] ```

Question 36

**55. Jump Game ( Medium )** You are given an integer array `nums`. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return `true` if you can reach the last index, or `false` otherwise. Example 1: ``` Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. ``` Example 2: ``` Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index. ```

Answer 36

**Code** ``` class Solution: def canJump(self, nums: List[int]) -> bool: #to keep track of max position that can be reached from current position max_reach = 0 #iterate through entire array for i, jump in enumerate(nums): #if curr position if greater than max reach then return false #as last index cant be reached if i > max_reach: return False #update max reach every time max_reach = max(max_reach, i+jump) #return true as last index can be reached as we are here. return True ```

Question 37

**48. Rotate Image ( Medium )** You are given an `n x n` 2D `matrix `representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation. Example 1: ``` Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] ```

Answer 37

We want to rotate [1,2,3], [4,5,6], [7,8,9] -> [7,4,1], [8,5,2], [9,6,3]] We can do this in two steps. Reversing the matrix does this: [1,2,3], [4,5,6], [7,8,9]] -> [7, 8, 9], [4, 5, 6], [1, 2, 3] Transposing means: rows become columns, columns become rows. [7, 8, 9], [4, 5, 6], [1, 2, 3] -> [7,4,1], [8,5,2], [9,6,3] **Code** ``` class Solution: def rotate(self, matrix: List[List[int]]) -> None: # algo # reverse # transpose and return matrix[:] = matrix[::-1] # reversed it # take transpose of the matrix and return it. for i in range(len(matrix)): for j in range(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] return matrix ```

Question 38

**54. Spiral Matrix ( Medium )** Given an `m x n` `matrix`, return all elements of the matrix in spiral order. Example 1: ``` Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5] ``` Example 2: ``` Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7] ```

Answer 38

**Visualization** Here's how the matrix changes by always extracting the first row and rotating the remaining matrix counter-clockwise: |1 2 3| |6 9| |8 7| |4| => |5| => || |4 5 6| => |5 8| => |5 4| => |5| |7 8 9| |4 7| Now look at the first rows we extracted: |1 2 3| |6 9| |8 7| |4| |5| Those concatenated are the desired result. **Another visualization** ``` spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) = [1, 2, 3] + spiral_order([[6, 9], [5, 8], [4, 7]]) = [1, 2, 3] + [6, 9] + spiral_order([[8, 7], [5, 4]]) = [1, 2, 3] + [6, 9] + [8, 7] + spiral_order([[4], [5]]) = [1, 2, 3] + [6, 9] + [8, 7] + [4] + spiral_order([[5]]) = [1, 2, 3] + [6, 9] + [8, 7] + [4] + [5] + spiral_order([]) = [1, 2, 3] + [6, 9] + [8, 7] + [4] + [5] + [] = [1, 2, 3, 6, 9, 8, 7, 4, 5] ``` **Code** ``` def spiralOrder(self, matrix): return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1]) ``` **Easy Code** ``` class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: res = [] # result array to return later row_start = 0 row_end = len(matrix)-1 col_start = 0 col_end = len(matrix[0])-1 while (row_start <= row_end) and (col_start <= col_end): # left to right for i in range(col_start, col_end+1): res.append(matrix[row_start][i]) # increment the row start row_start += 1 # top to bottom for i in range(row_start, row_end+1): res.append(matrix[i][col_end]) # decrement the col end col_end -= 1 # right to left if row_start <= row_end: for i in range(col_end, col_start-1, -1): res.append(matrix[row_end][i]) # decrement the row end row_end -= 1 # bottom to top if col_start <= col_end: for i in range(row_end, row_start-1, -1): res.append(matrix[i][col_start]) # increment the col_start col_start += 1 # return res array return res ```

Question 39

**73. Set Matrix Zeroes ( Medium )** Given an `m x n` integer matrix `matrix`, if an element is `0`, set its entire row and column to `0`'s. You must do it in place. Example 1: ``` Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]] ``` Example 2: ``` Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]] ```

Answer 39

**Code** ``` class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) # to keep track of column zero col0 = 1 for i in range(m): if matrix[i][0] == 0: col0 = 0 for j in range(1,n): if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0 for i in range(m-1, -1, -1): for j in range(n-1, 0, -1): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 if col0 == 0: matrix[i][0] = 0 return matrix ```

Question 40

**191. Number of 1 Bits ( Easy )** Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). **Note:** - Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. - In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. `-3`. Example 1: ``` Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. ``` Example 2: ``` Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit. ``` Example 3: ``` Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty ```

Answer 40

**Code** ``` class Solution: def hammingWeight(self, n: int) -> int: # algo # mod by 2 and if its 1 then increment the count # right shift all bits of n by one for next iteration # repeat the process while n > 0 res = 0 while n: # n % 2 will be zero if last bit is zero or # it will be one if last bit is one # whatever it is just add it to the result res += n % 2 # right shift all bits by one n = n >> 1 return res ```

Question 41

**338. Counting Bits ( Easy )** Given an integer `n`, return an array `ans` of length `n + 1` such that for each `i` (`0 <= i <= n`), `ans[i]` is the number of `1`'s in the binary representation of `i`. Example 1: ``` Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 ``` Example 2: ``` Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101 ```

Answer 41

**Code** ``` class Solution: def countBits(self, n: int) -> List[int]: res = [] for i in range(n+1): res.append(bin(i)[2:].count('1')) return res ```

Question 42

**190. Reverse Bits ( Easy )** Reverse bits of a given 32 bits unsigned integer. **Note:** - Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. - In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer `-3` and the output represents the signed integer `-1073741825`. Example 1: ``` Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000) Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000. ``` Example 2: ``` Input: n = 11111111111111111111111111111101 Output: 3221225471 (10111111111111111111111111111111) Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111. ```

Answer 42

**Code** ``` class Solution: def reverseBits(self, n: int) -> int: # algo # initialise rev num to zero # iterate in range of 32 - for each iteration # left shift rev number by 1, or it with - (n and 1) # then right shift n by one # lastly return the result rev = 0 for i in range(32): rev = (rev << 1) | (n & 1) n >>= 1 return rev ```

Question 43

**268. Missing Number ( Easy )** Given an array `nums` containing `n` distinct numbers in the range` [0, n]`, return the only number in the range that is missing from the array. Example 1: ``` Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums. ``` Example 2: ``` Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums. ``` Example 3: ``` Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums. ```

Answer 43

**Code** ``` class Solution: def missingNumber(self, nums: List[int]) -> int: # res is initialised to len(nums) bacause our loop will add all numbers # in range (0, len(nums)-1) but not len(nums) # so we already initialising it to len(nums) then adding rest of the numbers res = len(nums) for i in range(len(nums)): # here i is number from array [0,1,2,3] for given array [3,0,1] # res is the diff between two arrays given above # which will be missing number and that will be our answer res += (i-nums[i]) return res ```

Question 44

**371. Sum of Two Integers ( Medium )** Given two integers `a` and `b`, return the sum of the two integers without using the operators `+` and `-`. Example 1: ``` Input: a = 1, b = 2 Output: 3 ``` Example 2: ``` Input: a = 2, b = 3 Output: 5 ```

Answer 44

**Code** ``` class Solution: def getSum(self, a: int, b: int) -> int: mask = 0b11111111111111111111111111111111 MAX = 0b01111111111111111111111111111111 if b == 0: return a if a <= MAX else ~(a ^ mask) return self.getSum( (a ^ b) & mask, ((a & b) << 1) & mask ) ```

Question 45

**659 · Encode and Decode Strings ( Medium )** Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement `encode` and `decode` Example1 ``` Input: ["lint","code","love","you"] Output: ["lint","code","love","you"] ``` ``` Explanation: One possible encode method is: "lint:;code:;love:;you" ``` Example2 ``` Input: ["we", "say", ":", "yes"] Output: ["we", "say", ":", "yes"] ``` ``` Explanation: One possible encode method is: "we:;say:;:::;yes" ```

Answer 45

**Code** ``` class Solution: def encode(self, strs): res = "" for s in strs: res += str(len(s)) + '#' + s return res def decode(self, str): res = [] i = 0 while i < len(str): j = i while s[j] != '#': j += 1 # now j is at '#' for encoded string '4#bubu' # everything from i to j without including j is length # as we can see, so we will store it in length length = int(str[i:j]) # in res array we will append string # string begins from j+1 and takes length chars res.append(str[j+1:j+1+length]) # i will be set to start of new string i = j+1+length return res ```

Question 46

**128. Longest Consecutive Sequence ( Medium )** Given an unsorted array of integers `nums`, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in `O(n)` time. Example 1: ``` Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. ``` Example 2: ``` Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9 ```

Answer 46

- Convert array into set - If num does not have neighbour, then its start of seq so `curr_num` is num and `curr_seq` is 1 - so while `curr_num+1` is in set we will increment `curr_seq` too and `long_seq` is max of curr and long seq - Lastly we will return `long_seq` **Code** ``` class Solution: def longestConsecutive(self, nums: List[int]) -> int: long_seq = 0 numSet = set(nums) for n in numSet: if (n-1) not in numSet: # start of seq curr_num, curr_seq = n, 1 while (curr_num + 1) in numSet: curr_num += 1 curr_seq += 1 long_seq = max(curr_seq, long_seq) return long_seq ```

Question 47

**3. Longest Substring Without Repeating Characters ( Medium )** Given a string `s`, find the length of the longest substring without repeating characters. Example 1: ``` Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. ``` Example 2: ``` Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. ```

Answer 47

- `l` , `r` Sliding Window - Create set `charSet` - when we encounter duplicate element, we will keep removing leftmost element from set and we will keep incrementing left pointer - We will add rightmost char `s[r]` to the set. - `res` is max of `res` and `(r-l+1)` - Lastly we will return the `res` array **Code** ``` class Solution: def lengthOfLongestSubstring(self, s: str) -> int: res = 0 charSet = set() l = 0 # sliding window for r in range(len(s)): # when we encounter duplicate element while s[r] in charSet: # keep removing left char # keep incrementing left pointer charSet.remove(s[l]) l += 1 charSet.add(s[r]) res = max(res, (r-l+1)) return res ```

Question 48

**424. Longest Repeating Character Replacement** You are given a string `s` and an integer `k`. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most `k` times. Return the length of the longest substring containing the same letter you can get after performing the above operations. Example 1: ``` Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. ``` Example 2: ``` Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too. ```

Answer 48

``` class Solution: def characterReplacement(self, s: str, k: int) -> int: # initialize dict to count freq of char in given string count = {} # length of maximum window in order to return later as output res = 0 # left pointer l = 0 # count of most frequently occuring character maxf = 0 for r in range(len(s)): # add each char of string to dict count[s[r]] = 1 + count.get(s[r], 0) # update the max count as we go along maxf = max(maxf, count[s[r]]) # while number of characters to be replaced from window are greater than # number of characters we are allowed to replace # shrink our sliding window while (r-l+1)-maxf > k: count[s[l]] -= 1 l += 1 # update the length of maximum repeating char window res = max(res, (r-l+1)) # return res return res ```

Question 49

**143. Reorder List** You are given the head of a singly linked-list. The list can be represented as: `L0 → L1 → … → Ln - 1 → Ln` Reorder the list to be on the following form: `L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …` You may not modify the values in the list's nodes. Only nodes themselves may be changed. Example 1: ``` Input: head = [1,2,3,4] Output: [1,4,2,3] ``` Example 2: ``` Input: head = [1,2,3,4,5] Output: [1,5,2,4,3] ```

Answer 49

``` # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reorderList(self, head: Optional[ListNode]) -> None: # reach mid # seprate two linked lists # reverse second half # add one node from first ll and first from second ll slow, fast = head, head while fast.next and fast.next.next: slow, fast = slow.next, fast.next.next # slow.next = head head2 = slow.next # sep two linked list slow.next = None # reverse second half prev = None curr = head2 while curr: next = curr.next curr.next = prev prev = curr curr = next head2 = prev dummy = ListNode(0) # add nodes from head and head2 c1, c2 = head, head2 while c1 and c2: dummy.next = c1 c1 = c1.next dummy = dummy.next dummy.next = c2 c2 = c2.next dummy = dummy.next dummy.next = c1 or c2 return dummy.next ```