amarjitdhillon

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:        
        if len(s2) < len(s1): # edge case
            return False
        
        freq_s1, freq_s2 = [0]*26, [0]*26
            
        # populate freq_s1 list
        for x in s1:
            freq_s1[ord(x)-ord('a')] += 1

amarjitdhillon

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        '''
        1. len(P) >= len(S). if not return [] as there is no anagram
        2. Take sliding  window of len(P) and slide over the S array. Update the frequecy list for each window
            if both lists are same then add the index to result list.append
        3. At then end return res list
        '''
        
        res, charP, charS = [], [0]*26, [0]*26

amarjitdhillon

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:    
        l, r = 0, len(nums)-1
        while(l < r):
            m = (l+r)//2
            if nums[m] > nums[m+1]: # peak is at left for sure, so update the r pointer
                r = m
            else : # peak is at right for sure, so update l pointer
                l = m+1
        return l

amarjitdhillon

    def maxSubArray(self, nums: List[int]) -> int:
        current_sum, max_sum = 0, nums[0] # add first element to max array as len(nums) > 1 (given constaint)
        for x in nums:
            current_sum += x
              
            if current_sum > max_sum: # update the max sum
                max_sum = current_sum
                
            # reset if sum is negative
            if current_sum < 0: 

amarjitdhillon

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea, currArea, l, r = 0,0, 0, len(height)-1
        
        while(l < r and l >= 0 and r <= len(height)-1):
            currArea = min(height[l],height[r]) * (r-l)
            if currArea > maxArea:
                maxArea = currArea # udpate the max area
            
            if height[l] < height[r]: # left pointer needs to be incremented

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

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 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

# 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 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