amarjitdhillon

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        '''
        Intuition: We can convert the string s into array groups that represent the length of same-character contiguous blocks within the string. For example, if s = "110001111000000", then groups lengths will be [2, 3, 4, 6]. Then, we can make min(groups[i], groups[i+1]) valid binary strings within this string. Because the binary digits to the left or right of this string must change at the boundary, our answer can never be larger.
        
        Let's understand this with an example
                For 00011 we have 2 groups of lengths 3 and 2, yet here we can make 2 valid substrings which are min(4,2). 
                    These strings are 0011 and 01. So clearly min group is the limiting factor
                 For 000011, we have 2 groups of lengths 4 and 2, yet here we can make 2 valid substrings which are min(4,2). 
                    These strings are 0011 and 01. I hope the logic is clear

amarjitdhillon

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        R = len(board)       # num of rows 
        C = len(board[0])    # num of cols
        
        # use a set to hold all the values which are visited before in the path
        visited = set()     
        
        '''
        Desc for findIfExists function

amarjitdhillon

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        oneCount, flipCount = 0,0                 # intially both are 0
        for c in s:
            if c == "1":
                oneCount += 1
            else:                                   # if not 1 then it's a zero
                if oneCount >= 1:       
                    flipCount += 1                  # in case we have already seen a zero, we will increase the flipCount 
            flipCount = min(flipCount, oneCount)    # we will do fip if it's count is less then # of 1's seen so far

amarjitdhillon

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        result, plogs = [], []
        
        for i, log in enumerate(logs):
            lg = log.split(" ")  # split the string over the space and convert to a list. 
            
            if lg[1].isalpha(): # Identify the type of log as letter log or digit log : this can be checked if 2nd element is string or a digit?
                # tuple with 4 keys (k1,k2,k3,k4)
                # k1 for which type of logs, k2 for contents of logs, k3 for log identifier and k4 for original index in logs list

amarjitdhillon

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []     
        keypad = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
        
        # edge case
        if len(digits) == 0:
            return []
        
        def dfsKeypad(index,path):

amarjitdhillon

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        
        open_count,close_count, result, r = 0, 0, [], []
        
        def dfsParantheses(open_count,close_count,r):
            
            if open_count == close_count == n:  # base case, bottom of the tree

amarjitdhillon

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # create a min heap and add the first element of each linked list with the id. here `id` is the list number
        minheap = []

amarjitdhillon

class Solution:
    def rotate(self, mat: List[List[int]]) -> None:
        """
        Time complexity: O(N) as we are iterating the matrix twice where N is the number of cells in the grid.
        Space complexity: O(1) as  we are doing the in place transaction
        """
        C = len(mat[0])
        R = len(mat)
        
        # first transformation is for all the rows and half of the element lying to right hand side of diagonal

amarjitdhillon

class Solution:
    def spiralOrder(self, mat: List[List[int]]) -> List[int]:
        t, b ,l, r = 0, len(mat), 0, len(mat[0])    # define top, bottom, left and right
        res = []                                    # final result array
        
        while((l < r) and (t < b)):             # print till the bounds don't collide 
            
            for i in range(l, r):               # print the top row, left to right from l to r
                res.append(mat[t][i])
            t += 1

amarjitdhillon

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # In base case, the `not root` is the null case, other cases means we have found the node we are looking for
        if not root or root == p or root == q: 
            return root
        
        x = self.lowestCommonAncestor(root.left, p, q)
        y = self.lowestCommonAncestor(root.right, p, q)
        
        if (x and y) or root in [p,q]: # root in [p,q] as node can be ancestor of itself