Grind 75 Solutions

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Store all visited numbers and their indices in a hashmap.
        # For every number 'num', find if (target - num) is present in the above hashmap.
        # Return the pair of indices if we find such pair.
        numIdxMap = {}
        for i, num in enumerate(nums):
            remainingNum = target - num
            if(remainingNum in numIdxMap):
                return [numIdxMap[remainingNum], i]
            numIdxMap[num] = i

class Solution:
    def isValid(self, s: str) -> bool:
        bracketMap = {
            "(": ")",
            "{": "}",
            "[": "]"
        }
        stack = []
        for c in s:
            # Open brackets: Add to the stack
            # Closed brackets: Check the type of the last openining bracket
            if(c in bracketMap):
                stack.append(c)
            elif(not stack):
                return False
            else:
                lastOpenBracket = stack.pop()
                if(bracketMap[lastOpenBracket] != c):
                    return False
        # Check if all open brackets are closed successfully
        return len(stack) == 0

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Dummy head
        mergedList = ListNode(-1)
        mergedListHead = mergedList
        # Code similar to merging two arrays in merge sort
        # Since these are linked lists, we can optimize after finish iterating
        # over one of the lists
        while(list1 and list2):
            if(list1.val <= list2.val):
                mergedList.next = list1
                list1 = list1.next
            else:
                mergedList.next = list2
                list2 = list2.next
            mergedList = mergedList.next
        if(list1):
            mergedList.next = list1
        if(list2):
            mergedList.next = list2
        return mergedListHead.next

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # At every price in the prices array,
        # update the minimum price and maximum profit
        ans = 0
        minPrice = float("inf")
        for price in prices:
            minPrice = min(minPrice, price)
            ans = max(ans, price - minPrice)
        return ans

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Convert string to a list after converting
        # all uppercases letters into lowercase letters and removing all non-alphanumeric characters
        # Check if the list rades the same forward and backward
        sModified = [c.lower() for c in s if c.isalnum()]
        return sModified == sModified[::-1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if(root is None):
            return None
        # Replace L/R subtree with the inverted R/L subtree
        # Store one of the original subtrees in a temporary variable
        # to not loose them during inversion
        oldLeft = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(oldLeft)
        return root

class Solution:
    def getKey(self, s):
        # Generate a key from s that represents
        # number of occurences of all 26 characters separated by #
        counter = [0 for _ in range(26)]
        for c in s:
            counter[ord(c) - ord("a")] += 1
        return "#".join([str(val) for val in counter])

    def isAnagram(self, s: str, t: str) -> bool:
        # Is valid anagram if both s and t generates the same key
        return self.getKey(s) == self.getKey(t)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # # Iterative
        # start, end = 0, len(nums) - 1
        # while(start <= end):
        #     mid = (start + end) // 2
        #     if(target < nums[mid]):
        #         end = mid - 1
        #     elif(target > nums[mid]):
        #         start = mid + 1
        #     else:
        #         return mid
        # return -1

        # Recursive
        def dfs(nums, start, end):
            if(start > end):
                return -1
            mid = (start + end) // 2
            if(target < nums[mid]):
                return dfs(nums, start, mid - 1)
            elif(target > nums[mid]):
                return dfs(nums, mid + 1, end)
            else:
                return mid
        return dfs(nums, 0, len(nums) - 1)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        # Similar to number of islands / connected components
        def dfs(i, j, srcColor):
            if((i < 0) or (i >= numRows) or
               (j < 0) or (j >= numCols) or
               (image[i][j] != srcColor)):
               return
            image[i][j] = color
            dfs(i - 1, j, srcColor)
            dfs(i + 1, j, srcColor)
            dfs(i, j - 1, srcColor)
            dfs(i, j + 1, srcColor)

        numRows, numCols = len(image), len(image[0])
        if(image[sr][sc] != color):
            dfs(sr, sc, image[sr][sc])
        return image

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Since p and q exists in BST, there are three possibilities
        # of their placement with respect to the root:
        # Both on the left, Both on the right, One on the left and another on the right.
        # Recursively search for ancestor if both p and q are on the same side
        # Otherwise, root is the lowest common ancestor
        if((p.val < root.val) and (q.val < root.val)):
            return self.lowestCommonAncestor(root.left, p, q)
        elif((p.val > root.val) and (q.val > root.val)):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Binary tree is balanced if:
        # 1. Its left and right subtree is balanced
        # 2. Depth of two subtrees does not differ by more than 1
        def dfs(node):
            if(node is None):
                return True, 0
            isLeftBalanced, leftHeight = dfs(node.left)
            isRightBalanced, rightHeight = dfs(node.right)
            return (
                (isLeftBalanced and isRightBalanced and abs(leftHeight - rightHeight) <= 1),
                (max(leftHeight, rightHeight) + 1)
            )
        return dfs(root)[0]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Floyd's Tortoise and Hare Algorithm
        slow, fast = head, head
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next.next
            if(slow == fast):
                return True
        return False

class MyQueue:
    # Implemented with costly O(n) push operation and constant time O(1) pop operation
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        while(self.stack1):
            self.stack2.append(self.stack1.pop())
        self.stack1.append(x)
        while(self.stack2):
            self.stack1.append(self.stack2.pop())

    def pop(self) -> int:
        return self.stack1.pop()

    def peek(self) -> int:
        return self.stack1[-1]

    def empty(self) -> bool:
        return len(self.stack1) == 0


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # Simple binary search
        # Check if mid is a bad version.
        # If yes, then first bad version lies at mid / on the left of mid
        # Else, it lies on the right of mid
        start, end = 1, n
        while(start < end):
            mid = (start + end) // 2
            if(isBadVersion(mid)):
                end = mid
            else:
                start = mid + 1
        return start

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # Count all the characters in magazine
        charCounter = [0 for _ in range(26)]
        for c in magazine:
            charCounter[ord(c) - ord("a")] += 1
        # Check if there are enough characters to build ransomNote
        for c in ransomNote:
            if(charCounter[ord(c) - ord("a")] == 0):
                return False
            charCounter[ord(c) - ord("a")] -= 1
        return True

class Solution:
    def climbStairs(self, n: int) -> int:
        # Since we can either climb 1 or 2 steps,
        # this problem becomes similar to fibonacci number where,
        # F(n) = F(n - 1) + F(n - 2)
        def helper(n):
            if(n in dp):
                return dp[n]
            dp[n - 1] = helper(n - 1)
            dp[n - 2] = helper(n - 2)
            return dp[n - 1] + dp[n - 2]
        dp = {0: 1, 1: 1}
        return helper(n)

class Solution:
    def longestPalindrome(self, s: str) -> int:
        # Store characters count in a hashmap
        counter = {}
        for c in s:
            if(c not in counter):
                counter[c] = 0
            counter[c] += 1
        # The longest palindrome will consist of all the characters from s in even count
        # and one extra character (if remaining from s) in the middle
        ans, oddCharCount = 0, False
        for c in counter:
            quotient, remainder = divmod(counter[c], 2)
            ans += (quotient * 2)
            oddCharCount = oddCharCount or remainder
        ans += oddCharCount
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current = head
        while(current and current.next):
            oldNext = current.next
            current.next = oldNext.next
            oldNext.next = head
            head = oldNext
        return head

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # If the number appears more than (n / 2) times,
        # then the value at the middle index in sorted array will always be that number
        nums.sort()
        return nums[len(nums) // 2]

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # Code written similar to merge sort
        # Store the mapping where
        # keys represent the input values in the form of (a, b, existing extraBit)
        # and corresponding values represent the value and extraBit obtained after adding a + b + existing extra bit
        mapping = {
            ("0", "0", "0"): ("0", "0"),
            ("0", "0", "1"): ("0", "1"),
            ("0", "1", "0"): ("0", "1"),
            ("0", "1", "1"): ("1", "0"),
            ("1", "0", "0"): ("0", "1"),
            ("1", "0", "1"): ("1", "0"),
            ("1", "1", "0"): ("1", "0"),
            ("1", "1", "1"): ("1", "1")
        }
        output = []
        i = 0
        extraBit = "0"
        while((i < len(a)) and (i < len(b))):
            aChar = a[len(a) - i - 1]
            bChar = b[len(b) - i - 1]
            extraBit, val = mapping[(aChar, bChar, extraBit)]
            output.insert(0, val)
            i += 1
        while(i < len(a)):
            aChar = a[len(a) - i - 1]
            extraBit, val = mapping[(aChar, "0", extraBit)]
            output.insert(0, val)
            i += 1
        while(i < len(b)):
            bChar = b[len(b) - i - 1]
            extraBit, val = mapping[("0", bChar, extraBit)]
            output.insert(0, val)
            i += 1
        if(extraBit == "1"):
            output.insert(0, extraBit)
        return "".join(output)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def helper(node):
            if(node is None):
                return 0, 0
            lMaxEdge, lDiameter = helper(node.left)
            rMaxEdge, rDiameter = helper(node.right)
            return (
                max(lMaxEdge, rMaxEdge) + 1,
                max(lDiameter, rDiameter, lMaxEdge + rMaxEdge + 1)
            )
        # Subtract 1 from the final answer as we need nuimber of edges between the path
        # and not the number of nodes
        _, diameter = helper(root)
        return diameter - 1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next.next
        return slow

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        history = set()
        for num in nums:
            if(num in history):
                return True
            history.add(num)
        return False

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        currentSum = float("-inf")
        largestSum = currentSum
        for num in nums:
            # For every number, we can either add it to the existing subarray
            # or we can start the subarray from this number itself
            currentSum = max(currentSum + num, num)
            # Update the largest sum after making a choice about every number
            largestSum = max(largestSum, currentSum)
        return largestSum

class Solution:
    def _helper(self, intervals, interval):
        if((len(intervals) == 0) or (interval[0] > intervals[-1][1])):
            intervals.append(interval)
        else:
            intervals[-1][1] = max(intervals[-1][1], interval[1])

    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        insertedIntervals, insertedNewInterval = [], False
        i = 0
        while(i < len(intervals)):
            interval = intervals[i]
            if((not insertedNewInterval) and
               (newInterval[0] < interval[0])):
                # Insert the new interval
                self._helper(insertedIntervals, newInterval)
                insertedNewInterval = True
            else:
                # Insert from intervals
                self._helper(insertedIntervals, interval)
                i += 1
        # Insert the new interval if not inserted already
        if(not insertedNewInterval):
            self._helper(insertedIntervals, newInterval)
        return insertedIntervals

class Solution:
    def _place(self, nums, i, pos):
        num = nums[i]
        j = pos[num]
        # Move numbers until you reach where you started
        while(True):
            tmp = nums[j]
            nums[j] = num
            num = tmp
            j = pos[num]
            if(i == j):
                nums[j] = tmp
                break
        return

    def _update_pos(self, num, pos):
        if(num < 1):
            pos[0] += 1
        if(num < 2):
            pos[1] += 1
        if(num < 3):
            pos[2] += 1

    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        pos = {i: 0 for i in range(3)}
        for i, num in enumerate(nums):
            # Place number at its correct place
            self._place(nums, i, pos)
            # Update positions
            self._update_pos(num, pos)
        return