Master DSA Patterns,
Land Any Tech Job.

# O(1) — constant
def get_first(arr): return arr[0]

# O(n) — single loop
def find(arr, t):
    for x in arr:
        if x == t: return True
    return False

# O(n²) — nested loops
def pairs(arr):
    for i in arr:
        for j in arr: print(i, j)

# O(log n) — halves each step
def bsearch(arr, t):
    l, r = 0, len(arr)-1
    while l <= r:
        m = (l+r)//2
        if arr[m]==t: return m
        elif arr[m]<t: l = m+1
        else: r = m-1
    return -1

def containsDuplicate(nums):
    seen = set()
    for n in nums:
        if n in seen: return True
        seen.add(n)
    return False
# Alt: return len(nums) != len(set(nums))

def missingNumber(nums):
    n = len(nums)
    return n*(n+1)//2 - sum(nums)

def findDisappearedNumbers(nums):
    seen = set(nums)
    return [i for i in range(1, len(nums)+1)
            if i not in seen]

def twoSum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        comp = target - n
        if comp in seen: return [seen[comp], i]
        seen[n] = i

def smallerNumbersThanCurrent(nums):
    s = sorted(nums); rank = {}
    for i, v in enumerate(s):
        if v not in rank: rank[v] = i
    return [rank[n] for n in nums]

def minTimeToVisitAllPoints(points):
    total = 0
    for i in range(len(points)-1):
        dx = abs(points[i+1][0]-points[i][0])
        dy = abs(points[i+1][1]-points[i][1])
        total += max(dx, dy)
    return total

def sortedSquares(nums):
    n = len(nums)
    res, l, r, pos = [0]*n, 0, n-1, n-1
    while l <= r:
        ls, rs = nums[l]**2, nums[r]**2
        if ls > rs: res[pos]=ls; l+=1
        else:       res[pos]=rs; r-=1
        pos -= 1
    return res

def threeSum(nums):
    nums.sort(); res = []
    for i in range(len(nums)-2):
        if i>0 and nums[i]==nums[i-1]: continue
        l, r = i+1, len(nums)-1
        while l < r:
            s = nums[i]+nums[l]+nums[r]
            if s==0:
                res.append([nums[i],nums[l],nums[r]])
                while l<r and nums[l]==nums[l+1]: l+=1
                while l<r and nums[r]==nums[r-1]: r-=1
                l+=1; r-=1
            elif s<0: l+=1
            else: r-=1
    return res

def minimumAbsDifference(arr):
    arr.sort()
    min_d = min(arr[i+1]-arr[i] for i in range(len(arr)-1))
    return [[arr[i],arr[i+1]] for i in range(len(arr)-1)
            if arr[i+1]-arr[i]==min_d]

def longestMountain(arr):
    n, res = len(arr), 0
    for i in range(1, n-1):
        if arr[i-1]<arr[i]>arr[i+1]:
            l, r = i-1, i+1
            while l>0 and arr[l-1]<arr[l]: l-=1
            while r<n-1 and arr[r]>arr[r+1]: r+=1
            res = max(res, r-l+1)
    return res

def containsNearbyDuplicate(nums, k):
    window = set()
    for i, n in enumerate(nums):
        if n in window: return True
        window.add(n)
        if len(window) > k: window.remove(nums[i-k])
    return False

def minSubArrayLen(target, nums):
    l = total = 0; min_len = float('inf')
    for r in range(len(nums)):
        total += nums[r]
        while total >= target:
            min_len = min(min_len, r-l+1)
            total -= nums[l]; l += 1
    return min_len if min_len != float('inf') else 0

def maxProfit(prices):
    min_p = float('inf'); max_p = 0
    for p in prices:
        min_p  = min(min_p, p)
        max_p  = max(max_p, p - min_p)
    return max_p

class NumArray:
    def __init__(self, nums):
        self.p = [0]
        for n in nums: self.p.append(self.p[-1]+n)
    def sumRange(self, l, r): return self.p[r+1]-self.p[l]

def spiralOrder(matrix):
    res = []
    T,B = 0,len(matrix)-1
    L,R = 0,len(matrix[0])-1
    while T<=B and L<=R:
        for c in range(L,R+1): res.append(matrix[T][c]); T+=1
        for r in range(T,B+1): res.append(matrix[r][R]); R-=1
        if T<=B:
            for c in range(R,L-1,-1): res.append(matrix[B][c]); B-=1
        if L<=R:
            for r in range(B,T-1,-1): res.append(matrix[r][L]); L+=1
    return res

def numIslands(grid):
    def dfs(r, c):
        if (r<0 or c<0 or r>=len(grid) or
            c>=len(grid[0]) or grid[r][c]=='0'): return
        grid[r][c]='0'
        dfs(r+1,c);dfs(r-1,c);dfs(r,c+1);dfs(r,c-1)
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c]=='1': count+=1; dfs(r,c)
    return count

def singleNumber(nums):
    result = 0
    for n in nums: result ^= n
    return result
# [4,1,2,1,2]: 0^4=4,^1=5,^2=7,^1=6,^2=4 ✓

def climbStairs(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n+1): a, b = b, a+b
    return b

def coinChange(coins, amount):
    dp = [float('inf')]*(amount+1); dp[0] = 0
    for i in range(1, amount+1):
        for coin in coins:
            if coin<=i: dp[i]=min(dp[i],dp[i-coin]+1)
    return dp[amount] if dp[amount]!=float('inf') else -1

def countBits(n):
    dp = [0]*(n+1)
    for i in range(1, n+1): dp[i] = dp[i>>1]+(i&1)
    return dp

def rob(nums):
    if not nums: return 0
    if len(nums)==1: return nums[0]
    prev2, prev1 = 0, 0
    for n in nums:
        curr = max(prev1, prev2+n)
        prev2, prev1 = prev1, curr
    return prev1
# dp[i] = max(skip house i, rob house i + best 2 ago)
# Rolling vars → O(1) space

def maxSubArray(nums):
    curr = res = nums[0]
    for n in nums[1:]:
        curr = max(n, curr+n)
        res  = max(res, curr)
    return res
# answer=6, subarray=[4,-1,2,1]

def letterCasePermutation(s):
    res = []
    def bt(i, curr):
        if i==len(s): res.append(curr); return
        if s[i].isdigit(): bt(i+1, curr+s[i])
        else:
            bt(i+1, curr+s[i].lower())
            bt(i+1, curr+s[i].upper())
    bt(0, ''); return res

def subsets(nums):
    res = []
    def bt(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i]); bt(i+1,path); path.pop()
    bt(0, []); return res

def combine(n, k):
    res = []
    def bt(start, path):
        if len(path)==k: res.append(path[:]); return
        need = k-len(path)
        for i in range(start, n+1):
            if n-i+1<need: break
            path.append(i); bt(i+1,path); path.pop()
    bt(1,[]); return res

def permute(nums):
    res = []
    def bt(path, used):
        if len(path)==len(nums): res.append(path[:]); return
        for n in nums:
            if n in used: continue
            path.append(n); used.add(n); bt(path,used)
            path.pop(); used.remove(n)
    bt([],set()); return res

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
    return slow

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
        if slow == fast: return True
    return False

def isPalindrome(head):
    slow=fast=head
    while fast and fast.next: slow=slow.next; fast=fast.next.next
    prev,curr=None,slow
    while curr:
        nxt=curr.next; curr.next=prev; prev=curr; curr=nxt
    l,r=head,prev
    while r:
        if l.val!=r.val: return False
        l=l.next; r=r.next
    return True

def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next   # SAVE!
        curr.next = prev  # flip
        prev = curr; curr = nxt
    return prev

def reverseBetween(head, left, right):
    dummy=ListNode(0,head); prev=dummy
    for _ in range(left-1): prev=prev.next
    curr=prev.next
    for _ in range(right-left):
        nxt=curr.next; curr.next=nxt.next
        nxt.next=prev.next; prev.next=nxt
    return dummy.next

def removeElements(head, val):
    dummy=ListNode(0); dummy.next=head; curr=dummy
    while curr.next:
        if curr.next.val==val: curr.next=curr.next.next
        else: curr=curr.next
    return dummy.next

def mergeTwoLists(l1, l2):
    dummy=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 dummy.next

class MinStack:
    def __init__(self): self.s=[]
    def push(self,v):
        m=min(v,self.s[-1][1] if self.s else v)
        self.s.append((v,m))
    def pop(self): self.s.pop()
    def top(self): return self.s[-1][0]
    def getMin(self): return self.s[-1][1]

def isValid(s):
    stack=[]; match={')':'(', ']':'[', '}':'{'}
    for c in s:
        if c in match:
            if not stack or stack[-1]!=match[c]: return False
            stack.pop()
        else: stack.append(c)
    return not stack

def evalRPN(tokens):
    stack=[]
    for t in tokens:
        if t in '+-*/':
            b,a=stack.pop(),stack.pop()
            if t=='+': stack.append(a+b)
            elif t=='-': stack.append(a-b)
            elif t=='*': stack.append(a*b)
            else: stack.append(int(a/b))
        else: stack.append(int(t))
    return stack[0]

def sortStack(stack):
    temp=[]
    while stack:
        val=stack.pop()
        while temp and temp[-1]>val: stack.append(temp.pop())
        temp.append(val)
    return temp

def dailyTemperatures(temps):
    n = len(temps)
    ans = [0] * n
    stack = []          # stores indices
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            idx = stack.pop()
            ans[idx] = i - idx
        stack.append(i)
    return ans
# [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

from collections import deque
class MyStack:
    def __init__(self): self.q=deque()
    def push(self,x):
        self.q.append(x)
        for _ in range(len(self.q)-1): self.q.append(self.q.popleft())
    def pop(self): return self.q.popleft()
    def top(self): return self.q[0]
    def empty(self): return not self.q

def timeRequiredToBuy(tickets, k):
    total=0
    for i,t in enumerate(tickets):
        if i<=k: total+=min(t,tickets[k])
        else: total+=min(t,tickets[k]-1)
    return total

from collections import deque
def reverseFirstK(q, k):
    stack=[]
    for _ in range(k): stack.append(q.popleft())
    while stack: q.append(stack.pop())
    for _ in range(len(q)-k): q.append(q.popleft())
    return q

from collections import deque
def maxSlidingWindow(nums, k):
    dq = deque()   # stores indices, decreasing values
    res = []
    for i, n in enumerate(nums):
        # remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # remove smaller elements from back
        while dq and nums[dq[-1]] <= n:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res
# [1,3,-1,-3,5,3,6,7] k=3 → [3,3,5,5,6,7]

from collections import deque
def averageOfLevels(root):
    res,q=[],deque([root])
    while q:
        total,sz=0,len(q)
        for _ in range(sz):
            n=q.popleft(); total+=n.val
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        res.append(total/sz)
    return res

from collections import deque
def minDepth(root):
    if not root: return 0
    q=deque([(root,1)])
    while q:
        node,d=q.popleft()
        if not node.left and not node.right: return d
        if node.left: q.append((node.left,d+1))
        if node.right: q.append((node.right,d+1))

from collections import deque
def levelOrder(root):
    if not root: return []
    res,q=[],deque([root])
    while q:
        level=[]
        for _ in range(len(q)):
            n=q.popleft(); level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        res.append(level)
    return res

def maxDepth(root):
    if not root: return 0
    return 1+max(maxDepth(root.left),maxDepth(root.right))

def isSameTree(p,q):
    if not p and not q: return True
    if not p or not q or p.val!=q.val: return False
    return isSameTree(p.left,q.left) and isSameTree(p.right,q.right)

def hasPathSum(root, targetSum):
    if not root: return False
    if not root.left and not root.right: return root.val==targetSum
    rem=targetSum-root.val
    return hasPathSum(root.left,rem) or hasPathSum(root.right,rem)

def diameterOfBinaryTree(root):
    mx=[0]
    def depth(node):
        if not node: return 0
        l,r=depth(node.left),depth(node.right)
        mx[0]=max(mx[0],l+r); return 1+max(l,r)
    depth(root); return mx[0]

def invertTree(root):
    if not root: return None
    root.left,root.right=invertTree(root.right),invertTree(root.left)
    return root

def lowestCommonAncestor(root, p, q):
    if not root or root==p or root==q: return root
    left=lowestCommonAncestor(root.left,p,q)
    right=lowestCommonAncestor(root.right,p,q)
    if left and right: return root
    return left or right

def searchBST(root, val):
    if not root or root.val==val: return root
    if val<root.val: return searchBST(root.left,val)
    return searchBST(root.right,val)

def insertIntoBST(root, val):
    if not root: return TreeNode(val)
    if val<root.val: root.left=insertIntoBST(root.left,val)
    else: root.right=insertIntoBST(root.right,val)
    return root

def sortedArrayToBST(nums):
    if not nums: return None
    mid=len(nums)//2; root=TreeNode(nums[mid])
    root.left=sortedArrayToBST(nums[:mid])
    root.right=sortedArrayToBST(nums[mid+1:])
    return root

def deleteNode(root, key):
    if not root: return None
    if key<root.val: root.left=deleteNode(root.left,key)
    elif key>root.val: root.right=deleteNode(root.right,key)
    else:
        if not root.left: return root.right
        if not root.right: return root.left
        succ=root.right
        while succ.left: succ=succ.left
        root.val=succ.val
        root.right=deleteNode(root.right,succ.val)
    return root

def findTarget(root, k):
    seen=set()
    def dfs(node):
        if not node: return False
        if k-node.val in seen: return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val<root.val and q.val<root.val: root=root.left
        elif p.val>root.val and q.val>root.val: root=root.right
        else: return root

def getMinimumDifference(root):
    res,prev=[float('inf')],[None]
    def inorder(node):
        if not node: return
        inorder(node.left)
        if prev[0] is not None: res[0]=min(res[0],node.val-prev[0])
        prev[0]=node.val; inorder(node.right)
    inorder(root); return res[0]

def balanceBST(root):
    nums=[]
    def inorder(n):
        if not n: return
        inorder(n.left); nums.append(n.val); inorder(n.right)
    def build(l,r):
        if l>r: return None
        mid=(l+r)//2; node=TreeNode(nums[mid])
        node.left=build(l,mid-1); node.right=build(mid+1,r); return node
    inorder(root); return build(0,len(nums)-1)

def kthSmallest(root, k):
    cnt,res=[0],[0]
    def inorder(node):
        if not node or cnt[0]>=k: return
        inorder(node.left)
        cnt[0]+=1
        if cnt[0]==k: res[0]=node.val
        inorder(node.right)
    inorder(root); return res[0]

import heapq
def findKthLargest(nums, k):
    heap=[]
    for n in nums:
        heapq.heappush(heap,n)
        if len(heap)>k: heapq.heappop(heap)
    return heap[0]

import heapq
def kClosest(points, k):
    heap=[]
    for x,y in points:
        heapq.heappush(heap,(-x*x-y*y,[x,y]))
        if len(heap)>k: heapq.heappop(heap)
    return [p for _,p in heap]

from collections import Counter
import heapq
def topKFrequent(nums, k):
    freq=Counter(nums); heap=[]
    for val,cnt in freq.items():
        heapq.heappush(heap,(cnt,val))
        if len(heap)>k: heapq.heappop(heap)
    return [v for _,v in heap]

import heapq
from collections import Counter,deque
def leastInterval(tasks, n):
    freq=Counter(tasks)
    heap=[-c for c in freq.values()]; heapq.heapify(heap)
    cooldown=deque(); time=0
    while heap or cooldown:
        time+=1
        if heap:
            cnt=1+heapq.heappop(heap)
            if cnt: cooldown.append((cnt,time+n))
        if cooldown and cooldown[0][1]==time:
            heapq.heappush(heap,cooldown.popleft()[0])
    return time

from collections import deque
def cloneGraph(node):
    if not node: return None
    clones={node:Node(node.val)}; q=deque([node])
    while q:
        curr=q.popleft()
        for nb in curr.neighbors:
            if nb not in clones:
                clones[nb]=Node(nb.val); q.append(nb)
            clones[curr].neighbors.append(clones[nb])
    return clones[node]

def findCheapestPrice(n, flights, src, dst, k):
    prices=[float('inf')]*n; prices[src]=0
    for _ in range(k+1):
        tmp=prices[:]           # MUST COPY!
        for u,v,w in flights:
            if prices[u]!=float('inf'):
                tmp[v]=min(tmp[v],prices[u]+w)
        prices=tmp
    return prices[dst] if prices[dst]!=float('inf') else -1

def canFinish(numCourses, prerequisites):
    graph={i:[] for i in range(numCourses)}
    for c,p in prerequisites: graph[c].append(p)
    state=[0]*numCourses
    def dfs(c):
        if state[c]==1: return False  # cycle!
        if state[c]==2: return True
        state[c]=1
        for p in graph[c]:
            if not dfs(p): return False
        state[c]=2; return True
    return all(dfs(c) for c in range(numCourses))

from collections import deque, defaultdict
def countComponents(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v); graph[v].append(u)
    visited = set()
    def bfs(node):
        q = deque([node]); visited.add(node)
        while q:
            cur = q.popleft()
            for nb in graph[cur]:
                if nb not in visited:
                    visited.add(nb); q.append(nb)
    count = 0
    for node in range(n):
        if node not in visited:
            bfs(node); count += 1
    return count

from collections import deque
def pacificAtlantic(heights):
    rows, cols = len(heights), len(heights[0])
    def bfs(starts):
        visited = set(starts); q = deque(starts)
        while q:
            r, c = q.popleft()
            for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr,nc = r+dr, c+dc
                if (0<=nr<rows and 0<=nc<cols
                    and (nr,nc) not in visited
                    and heights[nr][nc]>=heights[r][c]):
                    visited.add((nr,nc)); q.append((nr,nc))
        return visited
    pac = bfs([(r,0) for r in range(rows)]+[(0,c) for c in range(cols)])
    atl = bfs([(r,cols-1) for r in range(rows)]+[(rows-1,c) for c in range(cols)])
    return list(pac & atl)