100 coding · 195 theory · FAANG curated

Python Interview Questions — Coding & Theory

The most-asked Python interview content at Google, Amazon, Meta, Apple, Microsoft, and Netflix — 100 coding problems mapped against the canonical Blind 75 / NeetCode 150, plus 195 theory questions covering Python internals, OOP, decorators, generators, the GIL, async, exceptions, modules, and the standard library.

100Coding
195Theory
128Easy
143Medium
24Hard
Difficulty
Pattern
100 questions
  1. #1

    Two Sum

    Easy
    Arrays & Hashing AmazonGoogleMetaAppleMicrosoft

    Approach: Hash map: for each number n, check if target - n was already seen.

    ▼ Show solution ▲ Hide solution
    python
    def twoSum(nums, target):
        seen = {}
        for i, n in enumerate(nums):
            if target - n in seen:
                return [seen[target - n], i]
            seen[n] = i
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  2. #2

    Contains Duplicate

    Easy
    Arrays & Hashing AmazonApple

    Approach: Compare set size to list size.

    ▼ Show solution ▲ Hide solution
    python
    def containsDuplicate(nums):
        return len(set(nums)) != len(nums)
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  3. #3

    Valid Anagram

    Easy
    Arrays & Hashing AmazonBloombergUber

    Approach: Compare character counts.

    ▼ Show solution ▲ Hide solution
    python
    from collections import Counter
    
    def isAnagram(s, t):
        return Counter(s) == Counter(t)
    ⏱ Time O(n) · Space O(1) (26 letters)
    Open on LeetCode ↗
  4. #4

    Group Anagrams

    Medium
    Arrays & Hashing AmazonMetaUberMicrosoft

    Approach: Group by sorted-letter tuple (or 26-int count tuple) as dict key.

    ▼ Show solution ▲ Hide solution
    python
    from collections import defaultdict
    
    def groupAnagrams(strs):
        groups = defaultdict(list)
        for s in strs:
            groups[tuple(sorted(s))].append(s)
        return list(groups.values())
    ⏱ Time O(n·k log k) · Space O(n·k)
    Open on LeetCode ↗
  5. #5

    Top K Frequent Elements

    Medium
    Arrays & Hashing AmazonMetaUberYelp

    Approach: Counter + most_common, or bucket sort by frequency for O(n).

    ▼ Show solution ▲ Hide solution
    python
    from collections import Counter
    
    def topKFrequent(nums, k):
        return [n for n, _ in Counter(nums).most_common(k)]
    ⏱ Time O(n log k) · Space O(n)
    Open on LeetCode ↗
  6. #6

    Product of Array Except Self

    Medium
    Arrays & Hashing AmazonAppleMetaLinkedIn

    Approach: Two passes: prefix products left-to-right, then multiply by suffix products right-to-left.

    ▼ Show solution ▲ Hide solution
    python
    def productExceptSelf(nums):
        n = len(nums)
        out = [1] * n
        left = 1
        for i in range(n):
            out[i] = left
            left *= nums[i]
        right = 1
        for i in range(n - 1, -1, -1):
            out[i] *= right
            right *= nums[i]
        return out
    ⏱ Time O(n) · Space O(1) extra
    Open on LeetCode ↗
  7. #7

    Valid Sudoku

    Medium
    Arrays & Hashing AppleUber

    Approach: One set tracking (row,val), (val,col), (box,val) — reject on duplicate.

    ▼ Show solution ▲ Hide solution
    python
    def isValidSudoku(board):
        seen = set()
        for r in range(9):
            for c in range(9):
                v = board[r][c]
                if v == '.':
                    continue
                for k in ((r, v), (v, c), (r // 3, c // 3, v)):
                    if k in seen:
                        return False
                    seen.add(k)
        return True
    ⏱ Time O(1) (81 cells) · Space O(1)
    Open on LeetCode ↗
  8. #8

    Encode and Decode Strings

    Medium
    Arrays & Hashing GoogleMeta

    Approach: Prefix each string with its length + delimiter; decode by reading the length.

    ▼ Show solution ▲ Hide solution
    python
    class Codec:
        def encode(self, strs):
            return ''.join(f'{len(s)}#{s}' for s in strs)
    
        def decode(self, s):
            out, i = [], 0
            while i < len(s):
                j = s.index('#', i)
                n = int(s[i:j])
                out.append(s[j + 1:j + 1 + n])
                i = j + 1 + n
            return out
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  9. #9

    Longest Consecutive Sequence

    Medium
    Arrays & Hashing GoogleMetaMicrosoft

    Approach: Use a set. Only start counting from numbers whose predecessor is not present.

    ▼ Show solution ▲ Hide solution
    python
    def longestConsecutive(nums):
        s = set(nums)
        best = 0
        for n in s:
            if n - 1 not in s:
                cur = n
                while cur + 1 in s:
                    cur += 1
                best = max(best, cur - n + 1)
        return best
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  10. #10

    Best Time to Buy and Sell Stock

    Easy
    Arrays & Hashing AmazonMetaBloomberg

    Approach: Track running minimum; profit = max(profit, price - minSoFar).

    ▼ Show solution ▲ Hide solution
    python
    def maxProfit(prices):
        low, profit = float('inf'), 0
        for p in prices:
            low = min(low, p)
            profit = max(profit, p - low)
        return profit
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  11. #11

    Valid Palindrome

    Easy
    Two Pointers MetaMicrosoft

    Approach: Filter alphanumerics, lowercase, compare to its reverse.

    ▼ Show solution ▲ Hide solution
    python
    def isPalindrome(s):
        cleaned = [c.lower() for c in s if c.isalnum()]
        return cleaned == cleaned[::-1]
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  12. #12

    Two Sum II — Input Array Is Sorted

    Medium
    Two Pointers AmazonMicrosoft

    Approach: Two pointers from both ends; move based on sum vs. target.

    ▼ Show solution ▲ Hide solution
    python
    def twoSum(nums, target):
        l, r = 0, len(nums) - 1
        while l < r:
            s = nums[l] + nums[r]
            if s == target:
                return [l + 1, r + 1]
            if s < target:
                l += 1
            else:
                r -= 1
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  13. #13

    3Sum

    Medium
    Two Pointers MetaAmazonGoogleApple

    Approach: Sort, then fix one number and two-pointer the rest. Skip duplicates.

    ▼ Show solution ▲ Hide solution
    python
    def threeSum(nums):
        nums.sort()
        res = []
        for i, a in enumerate(nums):
            if i and a == nums[i - 1]:
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                s = a + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
        return res
    ⏱ Time O(n²) · Space O(1) (excluding output)
    Open on LeetCode ↗
  14. #14

    Container With Most Water

    Medium
    Two Pointers AmazonAppleBloomberg

    Approach: Two pointers — always move the smaller side inward.

    ▼ Show solution ▲ Hide solution
    python
    def maxArea(h):
        l, r, best = 0, len(h) - 1, 0
        while l < r:
            best = max(best, (r - l) * min(h[l], h[r]))
            if h[l] < h[r]:
                l += 1
            else:
                r -= 1
        return best
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  15. #15

    Trapping Rain Water

    Hard
    Two Pointers AmazonGoogleAppleGoldman Sachs

    Approach: Two pointers; water at each index = max-so-far on that side minus its height.

    ▼ Show solution ▲ Hide solution
    python
    def trap(h):
        l, r = 0, len(h) - 1
        lmax = rmax = total = 0
        while l < r:
            if h[l] < h[r]:
                lmax = max(lmax, h[l])
                total += lmax - h[l]
                l += 1
            else:
                rmax = max(rmax, h[r])
                total += rmax - h[r]
                r -= 1
        return total
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  16. #16

    Best Time to Buy and Sell Stock II

    Medium
    Sliding Window AmazonBloomberg

    Approach: Sum every positive day-over-day delta.

    ▼ Show solution ▲ Hide solution
    python
    def maxProfit(prices):
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  17. #17

    Longest Substring Without Repeating Characters

    Medium
    Sliding Window AmazonMetaGoogleMicrosoft

    Approach: Sliding window. When a repeat appears inside the window, jump the left edge past it.

    ▼ Show solution ▲ Hide solution
    python
    def lengthOfLongestSubstring(s):
        seen = {}
        l = best = 0
        for r, c in enumerate(s):
            if c in seen and seen[c] >= l:
                l = seen[c] + 1
            seen[c] = r
            best = max(best, r - l + 1)
        return best
    ⏱ Time O(n) · Space O(min(n, alphabet))
    Open on LeetCode ↗
  18. #18

    Longest Repeating Character Replacement

    Medium
    Sliding Window GoogleAmazon

    Approach: Window valid if (size − mostFrequent) ≤ k; shrink left when invalid.

    ▼ Show solution ▲ Hide solution
    python
    from collections import Counter
    
    def characterReplacement(s, k):
        cnt = Counter()
        l = best = top = 0
        for r, c in enumerate(s):
            cnt[c] += 1
            top = max(top, cnt[c])
            if r - l + 1 - top > k:
                cnt[s[l]] -= 1
                l += 1
            best = max(best, r - l + 1)
        return best
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  19. #19

    Permutation in String

    Medium
    Sliding Window MetaMicrosoft

    Approach: Maintain a frequency window of size len(s1) over s2 and compare counters.

    ▼ Show solution ▲ Hide solution
    python
    from collections import Counter
    
    def checkInclusion(s1, s2):
        if len(s1) > len(s2):
            return False
        need = Counter(s1)
        have = Counter(s2[:len(s1)])
        if have == need:
            return True
        for i in range(len(s1), len(s2)):
            have[s2[i]] += 1
            have[s2[i - len(s1)]] -= 1
            if have[s2[i - len(s1)]] == 0:
                del have[s2[i - len(s1)]]
            if have == need:
                return True
        return False
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  20. #20

    Minimum Window Substring

    Hard
    Sliding Window MetaAmazonUberLinkedIn

    Approach: Expand right until all needed chars covered, then shrink left while still valid.

    ▼ Show solution ▲ Hide solution
    python
    from collections import Counter
    
    def minWindow(s, t):
        need = Counter(t)
        missing = len(t)
        l = best_l = 0
        best = ''
        for r, c in enumerate(s):
            if need[c] > 0:
                missing -= 1
            need[c] -= 1
            if missing == 0:
                while need[s[l]] < 0:
                    need[s[l]] += 1
                    l += 1
                if not best or r - l + 1 < len(best):
                    best = s[l:r + 1]
                need[s[l]] += 1
                missing += 1
                l += 1
        return best
    ⏱ Time O(n) · Space O(k) where k = |t|
    Open on LeetCode ↗
  21. #21

    Sliding Window Maximum

    Hard
    Sliding Window AmazonGoogleCitadel

    Approach: Monotonic deque holding indices of candidates in decreasing order of value.

    ▼ Show solution ▲ Hide solution
    python
    from collections import deque
    
    def maxSlidingWindow(nums, k):
        dq, out = deque(), []
        for i, n in enumerate(nums):
            while dq and nums[dq[-1]] < n:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                out.append(nums[dq[0]])
        return out
    ⏱ Time O(n) · Space O(k)
    Open on LeetCode ↗
  22. #22

    Valid Parentheses

    Easy
    Stack AmazonGoogleMetaMicrosoft

    Approach: Stack: push openers, pop and match on closers.

    ▼ Show solution ▲ Hide solution
    python
    def isValid(s):
        pairs = {')': '(', ']': '[', '}': '{'}
        stack = []
        for c in s:
            if c in pairs:
                if not stack or stack.pop() != pairs[c]:
                    return False
            else:
                stack.append(c)
        return not stack
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  23. #23

    Min Stack

    Medium
    Stack AmazonGoogleBloomberg

    Approach: Store (value, currentMin) pairs so getMin is O(1).

    ▼ Show solution ▲ Hide solution
    python
    class MinStack:
        def __init__(self):
            self.stack = []
    
        def push(self, v):
            m = v if not self.stack else min(v, self.stack[-1][1])
            self.stack.append((v, m))
    
        def pop(self):
            self.stack.pop()
    
        def top(self):
            return self.stack[-1][0]
    
        def getMin(self):
            return self.stack[-1][1]
    ⏱ All ops O(1) · Space O(n)
    Open on LeetCode ↗
  24. #24

    Evaluate Reverse Polish Notation

    Medium
    Stack AmazonLinkedIn

    Approach: Push numbers; on operator, pop b then a, push a OP b. Use int(a/b) for truncated division.

    ▼ Show solution ▲ Hide solution
    python
    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]
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  25. #25

    Generate Parentheses

    Medium
    Stack AmazonUberBloomberg

    Approach: Backtrack — add '(' if open < n, add ')' if close < open.

    ▼ Show solution ▲ Hide solution
    python
    def generateParenthesis(n):
        out = []
        def bt(s, o, c):
            if len(s) == 2 * n:
                out.append(s)
                return
            if o < n: bt(s + '(', o + 1, c)
            if c < o: bt(s + ')', o, c + 1)
        bt('', 0, 0)
        return out
    ⏱ Time O(4ⁿ / √n) · Space O(n)
    Open on LeetCode ↗
  26. #26

    Daily Temperatures

    Medium
    Stack AmazonGoogleBloomberg

    Approach: Monotonic decreasing stack of indices; on warmer day, pop and record distance.

    ▼ Show solution ▲ Hide solution
    python
    def dailyTemperatures(t):
        out = [0] * len(t)
        stack = []
        for i, v in enumerate(t):
            while stack and t[stack[-1]] < v:
                j = stack.pop()
                out[j] = i - j
            stack.append(i)
        return out
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  27. #27

    Car Fleet

    Medium
    Stack AmazonGoogle

    Approach: Sort by position desc. Walk forward; a car only forms a new fleet if its arrival time > current max.

    ▼ Show solution ▲ Hide solution
    python
    def carFleet(target, position, speed):
        pairs = sorted(zip(position, speed), reverse=True)
        fleets, last = 0, 0
        for p, s in pairs:
            t = (target - p) / s
            if t > last:
                last = t
                fleets += 1
        return fleets
    ⏱ Time O(n log n) · Space O(n)
    Open on LeetCode ↗
  28. #28

    Largest Rectangle in Histogram

    Hard
    Stack AmazonMicrosoftCitadel

    Approach: Monotonic increasing stack of (index, height); pop while current height is smaller.

    ▼ Show solution ▲ Hide solution
    python
    def largestRectangleArea(h):
        stack, best = [], 0
        for i, v in enumerate(h + [0]):
            start = i
            while stack and stack[-1][1] > v:
                j, hh = stack.pop()
                best = max(best, hh * (i - j))
                start = j
            stack.append((start, v))
        return best
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  29. #29

    Binary Search

    Easy
    Binary Search AmazonAppleMicrosoft

    Approach: Standard iterative binary search.

    ▼ Show solution ▲ Hide solution
    python
    def search(nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            if nums[m] < target:
                l = m + 1
            else:
                r = m - 1
        return -1
    ⏱ Time O(log n) · Space O(1)
    Open on LeetCode ↗
  30. #30

    Search a 2D Matrix

    Medium
    Binary Search AmazonAppleBloomberg

    Approach: Treat the matrix as a 1D sorted array of length rows·cols.

    ▼ Show solution ▲ Hide solution
    python
    def searchMatrix(m, target):
        rows, cols = len(m), len(m[0])
        l, r = 0, rows * cols - 1
        while l <= r:
            mid = (l + r) // 2
            v = m[mid // cols][mid % cols]
            if v == target:
                return True
            if v < target:
                l = mid + 1
            else:
                r = mid - 1
        return False
    ⏱ Time O(log(rows·cols)) · Space O(1)
    Open on LeetCode ↗
  31. #31

    Koko Eating Bananas

    Medium
    Binary Search GoogleAmazon

    Approach: Binary search on speed k in [1, max(piles)]; check feasibility in O(n).

    ▼ Show solution ▲ Hide solution
    python
    from math import ceil
    
    def minEatingSpeed(piles, h):
        l, r = 1, max(piles)
        while l < r:
            m = (l + r) // 2
            if sum(ceil(p / m) for p in piles) <= h:
                r = m
            else:
                l = m + 1
        return l
    ⏱ Time O(n log M) · Space O(1)
    Open on LeetCode ↗
  32. #32

    Find Minimum in Rotated Sorted Array

    Medium
    Binary Search AmazonMicrosoft

    Approach: Compare mid to right; if mid > right, min is to the right of mid.

    ▼ Show solution ▲ Hide solution
    python
    def findMin(nums):
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m
        return nums[l]
    ⏱ Time O(log n) · Space O(1)
    Open on LeetCode ↗
  33. #33

    Search in Rotated Sorted Array

    Medium
    Binary Search AmazonMetaLinkedIn

    Approach: Decide which half is sorted, then check if target is within that half.

    ▼ Show solution ▲ Hide solution
    python
    def search(nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            if nums[l] <= nums[m]:
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -1
    ⏱ Time O(log n) · Space O(1)
    Open on LeetCode ↗
  34. #34

    Time Based Key-Value Store

    Medium
    Binary Search GoogleUberCitadel

    Approach: Store each key's appends sorted by timestamp; binary search the largest ≤ t.

    ▼ Show solution ▲ Hide solution
    python
    from collections import defaultdict
    
    class TimeMap:
        def __init__(self):
            self.data = defaultdict(list)
    
        def set(self, k, v, t):
            self.data[k].append((t, v))
    
        def get(self, k, t):
            arr = self.data[k]
            l, r, res = 0, len(arr) - 1, ''
            while l <= r:
                m = (l + r) // 2
                if arr[m][0] <= t:
                    res = arr[m][1]
                    l = m + 1
                else:
                    r = m - 1
            return res
    ⏱ set O(1) · get O(log n)
    Open on LeetCode ↗
  35. #35

    Median of Two Sorted Arrays

    Hard
    Binary Search GoogleAmazonAppleAdobe

    Approach: Binary-search a partition of the shorter array so all left ≤ all right.

    ▼ Show solution ▲ Hide solution
    python
    def findMedianSortedArrays(a, b):
        if len(a) > len(b):
            a, b = b, a
        m, n = len(a), len(b)
        half = (m + n + 1) // 2
        l, r = 0, m
        while l <= r:
            i = (l + r) // 2
            j = half - i
            al = a[i - 1] if i else -float('inf')
            ar = a[i] if i < m else float('inf')
            bl = b[j - 1] if j else -float('inf')
            br = b[j] if j < n else float('inf')
            if al <= br and bl <= ar:
                if (m + n) % 2:
                    return max(al, bl)
                return (max(al, bl) + min(ar, br)) / 2
            if al > br:
                r = i - 1
            else:
                l = i + 1
    ⏱ Time O(log min(m, n)) · Space O(1)
    Open on LeetCode ↗
  36. #36

    Reverse Linked List

    Easy
    Linked List AmazonAppleMetaMicrosoft

    Approach: Iterate, repointing each node's next to previous.

    ▼ Show solution ▲ Hide solution
    python
    def reverseList(head):
        prev = None
        while head:
            head.next, prev, head = prev, head, head.next
        return prev
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  37. #37

    Merge Two Sorted Lists

    Easy
    Linked List AmazonAppleMicrosoft

    Approach: Dummy head + tail pointer; splice smaller node each step.

    ▼ Show solution ▲ Hide solution
    python
    def mergeTwoLists(a, b):
        dummy = tail = ListNode()
        while a and b:
            if a.val < b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b
        return dummy.next
    ⏱ Time O(n + m) · Space O(1)
    Open on LeetCode ↗
  38. #38

    Reorder List

    Medium
    Linked List AmazonMetaMicrosoft

    Approach: Find middle (fast/slow), reverse second half, then interleave.

    ▼ Show solution ▲ Hide solution
    python
    def reorderList(head):
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        prev, cur = None, slow.next
        slow.next = None
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        a, b = head, prev
        while b:
            a_nxt, b_nxt = a.next, b.next
            a.next = b
            b.next = a_nxt
            a, b = a_nxt, b_nxt
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  39. #39

    Remove Nth Node From End of List

    Medium
    Linked List AmazonMetaMicrosoft

    Approach: Two pointers; advance fast by n then move both until fast.next is None.

    ▼ Show solution ▲ Hide solution
    python
    def removeNthFromEnd(head, n):
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            fast, slow = fast.next, slow.next
        slow.next = slow.next.next
        return dummy.next
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  40. #40

    Copy List with Random Pointer

    Medium
    Linked List MetaAmazonUberBloomberg

    Approach: Two-pass with old→new hash map.

    ▼ Show solution ▲ Hide solution
    python
    def copyRandomList(head):
        mp = {None: None}
        cur = head
        while cur:
            mp[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            mp[cur].next = mp[cur.next]
            mp[cur].random = mp[cur.random]
            cur = cur.next
        return mp[head]
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  41. #41

    Add Two Numbers

    Medium
    Linked List AmazonMetaMicrosoftBloomberg

    Approach: Walk both lists adding digits + carry into a new list.

    ▼ Show solution ▲ Hide solution
    python
    def addTwoNumbers(a, b):
        dummy = tail = ListNode()
        carry = 0
        while a or b or carry:
            v = (a.val if a else 0) + (b.val if b else 0) + carry
            carry, v = divmod(v, 10)
            tail.next = ListNode(v)
            tail = tail.next
            if a: a = a.next
            if b: b = b.next
        return dummy.next
    ⏱ Time O(max(m, n)) · Space O(max(m, n))
    Open on LeetCode ↗
  42. #42

    Linked List Cycle

    Easy
    Linked List AmazonMetaMicrosoft

    Approach: Floyd's tortoise and hare — slow & fast pointers must meet inside a cycle.

    ▼ Show solution ▲ Hide solution
    python
    def hasCycle(head):
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow is fast:
                return True
        return False
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  43. #43

    Find the Duplicate Number

    Medium
    Linked List AmazonGoogleApple

    Approach: Treat indices as a linked list; cycle entry is the duplicate (Floyd's).

    ▼ Show solution ▲ Hide solution
    python
    def findDuplicate(nums):
        slow = fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow2 = nums[0]
        while slow != slow2:
            slow, slow2 = nums[slow], nums[slow2]
        return slow
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  44. #44

    LRU Cache

    Medium
    Linked List AmazonMetaGoogleMicrosoft

    Approach: OrderedDict — move accessed key to the end; pop the oldest on overflow.

    ▼ Show solution ▲ Hide solution
    python
    from collections import OrderedDict
    
    class LRUCache:
        def __init__(self, capacity):
            self.cap = capacity
            self.cache = OrderedDict()
    
        def get(self, key):
            if key not in self.cache:
                return -1
            self.cache.move_to_end(key)
            return self.cache[key]
    
        def put(self, key, value):
            if key in self.cache:
                self.cache.move_to_end(key)
            self.cache[key] = value
            if len(self.cache) > self.cap:
                self.cache.popitem(last=False)
    ⏱ get/put O(1) · Space O(capacity)
    Open on LeetCode ↗
  45. #45

    Merge k Sorted Lists

    Hard
    Linked List AmazonGoogleMetaUber

    Approach: Min-heap of (val, list-index, node) — pop smallest, push its next.

    ▼ Show solution ▲ Hide solution
    python
    import heapq
    
    def mergeKLists(lists):
        pq = []
        for i, lst in enumerate(lists):
            if lst:
                heapq.heappush(pq, (lst.val, i, lst))
        dummy = tail = ListNode()
        while pq:
            _, i, node = heapq.heappop(pq)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(pq, (node.next.val, i, node.next))
        return dummy.next
    ⏱ Time O(N log k) · Space O(k)
    Open on LeetCode ↗
  46. #46

    Invert Binary Tree

    Easy
    Trees Google

    Approach: Recursively swap left and right.

    ▼ Show solution ▲ Hide solution
    python
    def invertTree(root):
        if not root:
            return None
        root.left, root.right = invertTree(root.right), invertTree(root.left)
        return root
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  47. #47

    Maximum Depth of Binary Tree

    Easy
    Trees AmazonLinkedIn

    Approach: 1 + max(depth(left), depth(right)).

    ▼ Show solution ▲ Hide solution
    python
    def maxDepth(root):
        if not root:
            return 0
        return 1 + max(maxDepth(root.left), maxDepth(root.right))
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  48. #48

    Diameter of Binary Tree

    Easy
    Trees GoogleMetaAmazon

    Approach: DFS — diameter through a node = leftHeight + rightHeight.

    ▼ Show solution ▲ Hide solution
    python
    def diameterOfBinaryTree(root):
        best = 0
        def depth(n):
            nonlocal best
            if not n:
                return 0
            l, r = depth(n.left), depth(n.right)
            best = max(best, l + r)
            return 1 + max(l, r)
        depth(root)
        return best
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  49. #49

    Balanced Binary Tree

    Easy
    Trees AmazonBloomberg

    Approach: Post-order: return -1 if any subtree is unbalanced.

    ▼ Show solution ▲ Hide solution
    python
    def isBalanced(root):
        def height(n):
            if not n:
                return 0
            l = height(n.left)
            if l == -1: return -1
            r = height(n.right)
            if r == -1 or abs(l - r) > 1: return -1
            return 1 + max(l, r)
        return height(root) != -1
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  50. #50

    Same Tree

    Easy
    Trees AmazonBloomberg

    Approach: Recurse both trees in lockstep.

    ▼ Show solution ▲ Hide solution
    python
    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)
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  51. #51

    Subtree of Another Tree

    Easy
    Trees AmazonMeta

    Approach: At each node of s, check if subtree rooted there equals t.

    ▼ Show solution ▲ Hide solution
    python
    def isSubtree(s, t):
        if not s:
            return False
        return isSameTree(s, t) or isSubtree(s.left, t) or isSubtree(s.right, t)
    ⏱ Time O(m·n) · Space O(h)
    Open on LeetCode ↗
  52. #52

    Lowest Common Ancestor of a BST

    Medium
    Trees AmazonMetaLinkedIn

    Approach: Walk down — first node where p and q split is the LCA.

    ▼ Show solution ▲ Hide solution
    python
    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
    ⏱ Time O(h) · Space O(1)
    Open on LeetCode ↗
  53. #53

    Binary Tree Level Order Traversal

    Medium
    Trees AmazonAppleMetaLinkedIn

    Approach: BFS, emit one list per level.

    ▼ Show solution ▲ Hide solution
    python
    from collections import deque
    
    def levelOrder(root):
        if not root: return []
        q, out = 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)
            out.append(level)
        return out
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  54. #54

    Binary Tree Right Side View

    Medium
    Trees AmazonMetaBloomberg

    Approach: BFS, append the last node of each level.

    ▼ Show solution ▲ Hide solution
    python
    from collections import deque
    
    def rightSideView(root):
        if not root: return []
        q, out = deque([root]), []
        while q:
            out.append(q[-1].val)
            for _ in range(len(q)):
                n = q.popleft()
                if n.left: q.append(n.left)
                if n.right: q.append(n.right)
        return out
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  55. #55

    Count Good Nodes in Binary Tree

    Medium
    Trees Microsoft

    Approach: DFS carrying the max value seen on the path.

    ▼ Show solution ▲ Hide solution
    python
    def goodNodes(root):
        def dfs(n, mx):
            if not n:
                return 0
            good = 1 if n.val >= mx else 0
            mx = max(mx, n.val)
            return good + dfs(n.left, mx) + dfs(n.right, mx)
        return dfs(root, root.val)
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  56. #56

    Validate Binary Search Tree

    Medium
    Trees AmazonMetaMicrosoft

    Approach: DFS with (lo, hi) bounds for each subtree.

    ▼ Show solution ▲ Hide solution
    python
    def isValidBST(root):
        def dfs(n, lo, hi):
            if not n:
                return True
            if not (lo < n.val < hi):
                return False
            return dfs(n.left, lo, n.val) and dfs(n.right, n.val, hi)
        return dfs(root, -float('inf'), float('inf'))
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  57. #57

    Kth Smallest Element in a BST

    Medium
    Trees AmazonMetaBloomberg

    Approach: Iterative in-order traversal, stop at k.

    ▼ Show solution ▲ Hide solution
    python
    def kthSmallest(root, k):
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right
    ⏱ Time O(h + k) · Space O(h)
    Open on LeetCode ↗
  58. #58

    Construct Binary Tree from Preorder and Inorder

    Medium
    Trees AmazonMetaBloomberg

    Approach: Use an inorder index map; root is the next preorder value.

    ▼ Show solution ▲ Hide solution
    python
    def buildTree(preorder, inorder):
        idx = {v: i for i, v in enumerate(inorder)}
        pre = iter(preorder)
        def build(l, r):
            if l > r:
                return None
            v = next(pre)
            node = TreeNode(v)
            node.left = build(l, idx[v] - 1)
            node.right = build(idx[v] + 1, r)
            return node
        return build(0, len(inorder) - 1)
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  59. #59

    Binary Tree Maximum Path Sum

    Hard
    Trees AmazonMetaMicrosoft

    Approach: DFS — returns max single-arm gain; updates global max with both arms.

    ▼ Show solution ▲ Hide solution
    python
    def maxPathSum(root):
        best = -float('inf')
        def dfs(n):
            nonlocal best
            if not n:
                return 0
            l = max(dfs(n.left), 0)
            r = max(dfs(n.right), 0)
            best = max(best, n.val + l + r)
            return n.val + max(l, r)
        dfs(root)
        return best
    ⏱ Time O(n) · Space O(h)
    Open on LeetCode ↗
  60. #60

    Serialize and Deserialize Binary Tree

    Hard
    Trees AmazonMetaGoogleLinkedIn

    Approach: Preorder with '#' for None; comma-join for serialize, iter for deserialize.

    ▼ Show solution ▲ Hide solution
    python
    class Codec:
        def serialize(self, root):
            vals = []
            def dfs(n):
                if not n:
                    vals.append('#'); return
                vals.append(str(n.val))
                dfs(n.left); dfs(n.right)
            dfs(root)
            return ','.join(vals)
    
        def deserialize(self, data):
            it = iter(data.split(','))
            def dfs():
                v = next(it)
                if v == '#': return None
                n = TreeNode(int(v))
                n.left, n.right = dfs(), dfs()
                return n
            return dfs()
    ⏱ Time O(n) · Space O(n)
    Open on LeetCode ↗
  61. #61

    Implement Trie (Prefix Tree)

    Medium
    Tries AmazonGoogleMicrosoft

    Approach: Node = dict of children + 'end' flag.

    ▼ Show solution ▲ Hide solution
    python
    class Trie:
        def __init__(self):
            self.children = {}
            self.end = False
    
        def insert(self, w):
            cur = self
            for c in w:
                cur = cur.children.setdefault(c, Trie())
            cur.end = True
    
        def search(self, w):
            cur = self._walk(w)
            return bool(cur) and cur.end
    
        def startsWith(self, p):
            return self._walk(p) is not None
    
        def _walk(self, w):
            cur = self
            for c in w:
                if c not in cur.children:
                    return None
                cur = cur.children[c]
            return cur
    ⏱ insert/search/startsWith O(|w|)
    Open on LeetCode ↗
  62. #62

    Design Add and Search Words Data Structure

    Medium
    Tries AmazonMetaGoogle

    Approach: Trie + DFS for '.' wildcards.

    ▼ Show solution ▲ Hide solution
    python
    class WordDictionary:
        def __init__(self):
            self.root = {}
    
        def addWord(self, w):
            cur = self.root
            for c in w:
                cur = cur.setdefault(c, {})
            cur['$'] = True
    
        def search(self, w):
            def dfs(node, i):
                if i == len(w):
                    return node.get('$', False)
                c = w[i]
                if c == '.':
                    return any(dfs(child, i + 1) for k, child in node.items() if k != '$')
                return c in node and dfs(node[c], i + 1)
            return dfs(self.root, 0)
    ⏱ addWord O(|w|) · search O(26^dots · |w|)
    Open on LeetCode ↗
  63. #63

    Word Search II

    Hard
    Tries AmazonGoogleMeta

    Approach: Trie of all target words + DFS from each cell.

    ▼ Show solution ▲ Hide solution
    python
    def findWords(board, words):
        root = {}
        for w in words:
            cur = root
            for c in w:
                cur = cur.setdefault(c, {})
            cur['$'] = w
        rows, cols = len(board), len(board[0])
        out = []
        def dfs(r, c, node):
            ch = board[r][c]
            if ch not in node:
                return
            nxt = node[ch]
            if '$' in nxt:
                out.append(nxt.pop('$'))
            board[r][c] = '#'
            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:
                    dfs(nr, nc, nxt)
            board[r][c] = ch
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)
        return out
    ⏱ Time O(M·N·4^L) · Space O(total chars in words)
    Open on LeetCode ↗
  64. #64

    Kth Largest Element in a Stream

    Easy
    Heap / Priority Queue AmazonApple

    Approach: Maintain a min-heap of size k.

    ▼ Show solution ▲ Hide solution
    python
    import heapq
    
    class KthLargest:
        def __init__(self, k, nums):
            self.k = k
            self.h = nums
            heapq.heapify(self.h)
            while len(self.h) > k:
                heapq.heappop(self.h)
    
        def add(self, v):
            heapq.heappush(self.h, v)
            if len(self.h) > self.k:
                heapq.heappop(self.h)
            return self.h[0]
    ⏱ add O(log k) · Space O(k)
    Open on LeetCode ↗
  65. #65

    Last Stone Weight

    Easy
    Heap / Priority Queue AmazonGoogle

    Approach: Max-heap (negate values); repeatedly smash two largest.

    ▼ Show solution ▲ Hide solution
    python
    import heapq
    
    def lastStoneWeight(stones):
        h = [-s for s in stones]
        heapq.heapify(h)
        while len(h) > 1:
            a, b = -heapq.heappop(h), -heapq.heappop(h)
            if a != b:
                heapq.heappush(h, -(a - b))
        return -h[0] if h else 0
    ⏱ Time O(n log n) · Space O(n)
    Open on LeetCode ↗
  66. #66

    K Closest Points to Origin

    Medium
    Heap / Priority Queue AmazonMetaLinkedIn

    Approach: heapq.nsmallest by squared distance.

    ▼ Show solution ▲ Hide solution
    python
    import heapq
    
    def kClosest(points, k):
        return heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)
    ⏱ Time O(n log k) · Space O(k)
    Open on LeetCode ↗
  67. #67

    Kth Largest Element in an Array

    Medium
    Heap / Priority Queue AmazonMetaLinkedIn

    Approach: heapq.nlargest(k) → last element, or quickselect.

    ▼ Show solution ▲ Hide solution
    python
    import heapq
    
    def findKthLargest(nums, k):
        return heapq.nlargest(k, nums)[-1]
    ⏱ Time O(n log k) · Space O(k)
    Open on LeetCode ↗
  68. #68

    Task Scheduler

    Medium
    Heap / Priority Queue AmazonMetaUber

    Approach: Math — answer = max(len(tasks), (max−1)·(n+1) + tasksWithMaxCount).

    ▼ Show solution ▲ Hide solution
    python
    from collections import Counter
    
    def leastInterval(tasks, n):
        cnt = Counter(tasks)
        mx = max(cnt.values())
        most = sum(1 for v in cnt.values() if v == mx)
        return max(len(tasks), (mx - 1) * (n + 1) + most)
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  69. #69

    Find Median from Data Stream

    Hard
    Heap / Priority Queue AmazonGoogleMetaMicrosoft

    Approach: Two heaps — max-heap (lower half) and min-heap (upper half) kept balanced.

    ▼ Show solution ▲ Hide solution
    python
    import heapq
    
    class MedianFinder:
        def __init__(self):
            self.lo = []  # max-heap (negated)
            self.hi = []  # min-heap
    
        def addNum(self, n):
            heapq.heappush(self.lo, -n)
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
            if len(self.hi) > len(self.lo):
                heapq.heappush(self.lo, -heapq.heappop(self.hi))
    
        def findMedian(self):
            if len(self.lo) > len(self.hi):
                return -self.lo[0]
            return (-self.lo[0] + self.hi[0]) / 2
    ⏱ add O(log n) · find O(1)
    Open on LeetCode ↗
  70. #70

    Subsets

    Medium
    Backtracking AmazonMetaBloomberg

    Approach: For each number, double the result list (include / exclude).

    ▼ Show solution ▲ Hide solution
    python
    def subsets(nums):
        out = [[]]
        for n in nums:
            out += [s + [n] for s in out]
        return out
    ⏱ Time O(n·2ⁿ) · Space O(n·2ⁿ)
    Open on LeetCode ↗
  71. #71

    Combination Sum

    Medium
    Backtracking AmazonMicrosoftApple

    Approach: Backtrack — at each step, reuse candidate or move on.

    ▼ Show solution ▲ Hide solution
    python
    def combinationSum(candidates, target):
        out = []
        def bt(start, remain, path):
            if remain == 0:
                out.append(path[:]); return
            for i in range(start, len(candidates)):
                c = candidates[i]
                if c <= remain:
                    path.append(c)
                    bt(i, remain - c, path)
                    path.pop()
        bt(0, target, [])
        return out
    ⏱ Time exponential (depends on target/min(candidates))
    Open on LeetCode ↗
  72. #72

    Permutations

    Medium
    Backtracking AmazonLinkedInBloomberg

    Approach: Backtrack with a 'used' boolean array.

    ▼ Show solution ▲ Hide solution
    python
    def permute(nums):
        out = []
        def bt(path, used):
            if len(path) == len(nums):
                out.append(path[:]); return
            for i, n in enumerate(nums):
                if not used[i]:
                    used[i] = True
                    path.append(n)
                    bt(path, used)
                    path.pop()
                    used[i] = False
        bt([], [False] * len(nums))
        return out
    ⏱ Time O(n·n!) · Space O(n)
    Open on LeetCode ↗
  73. #73

    Word Search

    Medium
    Backtracking AmazonMicrosoftBloomberg

    Approach: DFS from each cell, marking visited via in-place edit.

    ▼ Show solution ▲ Hide solution
    python
    def exist(board, word):
        rows, cols = len(board), len(board[0])
        def dfs(r, c, i):
            if i == len(word):
                return True
            if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]:
                return False
            tmp, board[r][c] = board[r][c], '#'
            ok = any(dfs(r + dr, c + dc, i + 1)
                     for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
            board[r][c] = tmp
            return ok
        return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
    ⏱ Time O(M·N·4^L) · Space O(L)
    Open on LeetCode ↗
  74. #74

    N-Queens

    Hard
    Backtracking AmazonMicrosoftApple

    Approach: Backtrack by row; track used columns and both diagonals via sets.

    ▼ Show solution ▲ Hide solution
    python
    def solveNQueens(n):
        out = []
        cols, d1, d2 = set(), set(), set()
        board = [['.'] * n for _ in range(n)]
        def bt(r):
            if r == n:
                out.append([''.join(row) for row in board]); return
            for c in range(n):
                if c in cols or r + c in d1 or r - c in d2:
                    continue
                cols.add(c); d1.add(r + c); d2.add(r - c)
                board[r][c] = 'Q'
                bt(r + 1)
                board[r][c] = '.'
                cols.remove(c); d1.remove(r + c); d2.remove(r - c)
        bt(0)
        return out
    ⏱ Time O(n!) · Space O(n)
    Open on LeetCode ↗
  75. #75

    Number of Islands

    Medium
    Graphs AmazonGoogleMetaMicrosoft

    Approach: DFS / BFS from each unvisited '1', marking the island.

    ▼ Show solution ▲ Hide solution
    python
    def numIslands(grid):
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
                return
            grid[r][c] = '0'
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc)
        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(r, c)
                    count += 1
        return count
    ⏱ Time O(M·N) · Space O(M·N)
    Open on LeetCode ↗
  76. #76

    Max Area of Island

    Medium
    Graphs MetaAmazonGoogle

    Approach: DFS returning size of each island.

    ▼ Show solution ▲ Hide solution
    python
    def maxAreaOfIsland(grid):
        rows, cols = len(grid), len(grid[0])
        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
        return max((dfs(r, c) for r in range(rows) for c in range(cols)), default=0)
    ⏱ Time O(M·N) · Space O(M·N)
    Open on LeetCode ↗
  77. #77

    Clone Graph

    Medium
    Graphs AmazonMetaGoogleBloomberg

    Approach: DFS with old→new map.

    ▼ Show solution ▲ Hide solution
    python
    def cloneGraph(node):
        if not node:
            return None
        mp = {}
        def dfs(n):
            if n in mp:
                return mp[n]
            clone = Node(n.val)
            mp[n] = clone
            for nb in n.neighbors:
                clone.neighbors.append(dfs(nb))
            return clone
        return dfs(node)
    ⏱ Time O(V + E) · Space O(V)
    Open on LeetCode ↗
  78. #78

    Walls and Gates

    Medium
    Graphs MetaGoogleUber

    Approach: Multi-source BFS from every gate.

    ▼ Show solution ▲ Hide solution
    python
    from collections import deque
    INF = 2147483647
    
    def wallsAndGates(rooms):
        rows, cols = len(rooms), len(rooms[0])
        q = deque()
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    q.append((r, c))
        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 rooms[nr][nc] == INF:
                    rooms[nr][nc] = rooms[r][c] + 1
                    q.append((nr, nc))
    ⏱ Time O(M·N) · Space O(M·N)
    Open on LeetCode ↗
  79. #79

    Rotting Oranges

    Medium
    Graphs AmazonApple

    Approach: Multi-source BFS from rotten oranges; track time and fresh count.

    ▼ Show solution ▲ Hide solution
    python
    from collections import deque
    
    def orangesRotting(grid):
        rows, cols = len(grid), len(grid[0])
        q = deque(); fresh = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2: q.append((r, c, 0))
                elif grid[r][c] == 1: fresh += 1
        minutes = 0
        while q:
            r, c, t = q.popleft()
            minutes = t
            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 grid[nr][nc] == 1:
                    grid[nr][nc] = 2; fresh -= 1
                    q.append((nr, nc, t + 1))
        return minutes if fresh == 0 else -1
    ⏱ Time O(M·N) · Space O(M·N)
    Open on LeetCode ↗
  80. #80

    Pacific Atlantic Water Flow

    Medium
    Graphs AmazonGoogle

    Approach: Two multi-source DFS from each ocean; answer = intersection of reachable cells.

    ▼ Show solution ▲ Hide solution
    python
    def pacificAtlantic(h):
        rows, cols = len(h), len(h[0])
        pac, atl = set(), set()
        def dfs(r, c, visited, prev):
            if (r, c) in visited or r < 0 or c < 0 or r >= rows or c >= cols or h[r][c] < prev:
                return
            visited.add((r, c))
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc, visited, h[r][c])
        for c in range(cols):
            dfs(0, c, pac, h[0][c])
            dfs(rows - 1, c, atl, h[rows - 1][c])
        for r in range(rows):
            dfs(r, 0, pac, h[r][0])
            dfs(r, cols - 1, atl, h[r][cols - 1])
        return list(pac & atl)
    ⏱ Time O(M·N) · Space O(M·N)
    Open on LeetCode ↗
  81. #81

    Surrounded Regions

    Medium
    Graphs AmazonGoogle

    Approach: Mark border-connected 'O's as safe, flip remaining 'O' to 'X'.

    ▼ Show solution ▲ Hide solution
    python
    def solve(board):
        if not board:
            return
        rows, cols = len(board), len(board[0])
        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != 'O':
                return
            board[r][c] = 'S'
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc)
        for r in range(rows):
            dfs(r, 0); dfs(r, cols - 1)
        for c in range(cols):
            dfs(0, c); dfs(rows - 1, c)
        for r in range(rows):
            for c in range(cols):
                board[r][c] = 'O' if board[r][c] == 'S' else 'X'
    ⏱ Time O(M·N) · Space O(M·N)
    Open on LeetCode ↗
  82. #82

    Course Schedule

    Medium
    Graphs AmazonAppleMetaBloomberg

    Approach: Topological sort (Kahn's). Possible iff all courses can be queued.

    ▼ Show solution ▲ Hide solution
    python
    from collections import defaultdict, deque
    
    def canFinish(n, prerequisites):
        graph = defaultdict(list)
        indeg = [0] * n
        for a, b in prerequisites:
            graph[b].append(a); indeg[a] += 1
        q = deque(i for i in range(n) if indeg[i] == 0)
        done = 0
        while q:
            c = q.popleft(); done += 1
            for nxt in graph[c]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)
        return done == n
    ⏱ Time O(V + E) · Space O(V + E)
    Open on LeetCode ↗
  83. #83

    Course Schedule II

    Medium
    Graphs AmazonMetaMicrosoft

    Approach: Same Kahn's topo sort, output the order taken.

    ▼ Show solution ▲ Hide solution
    python
    from collections import defaultdict, deque
    
    def findOrder(n, prerequisites):
        graph = defaultdict(list)
        indeg = [0] * n
        for a, b in prerequisites:
            graph[b].append(a); indeg[a] += 1
        q = deque(i for i in range(n) if indeg[i] == 0)
        order = []
        while q:
            c = q.popleft(); order.append(c)
            for nxt in graph[c]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)
        return order if len(order) == n else []
    ⏱ Time O(V + E) · Space O(V + E)
    Open on LeetCode ↗
  84. #84

    Redundant Connection

    Medium
    Graphs AmazonGoogle

    Approach: Union-Find — first edge whose endpoints already share a root is the answer.

    ▼ Show solution ▲ Hide solution
    python
    def findRedundantConnection(edges):
        parent = list(range(len(edges) + 1))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for u, v in edges:
            ru, rv = find(u), find(v)
            if ru == rv:
                return [u, v]
            parent[ru] = rv
    ⏱ Time O(n·α(n)) ≈ O(n) · Space O(n)
    Open on LeetCode ↗
  85. #85

    Number of Connected Components in an Undirected Graph

    Medium
    Graphs AmazonGoogle

    Approach: Union-Find — count = n − successful unions.

    ▼ Show solution ▲ Hide solution
    python
    def countComponents(n, edges):
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        comp = n
        for u, v in edges:
            ru, rv = find(u), find(v)
            if ru != rv:
                parent[ru] = rv
                comp -= 1
        return comp
    ⏱ Time O((n + e)·α(n)) · Space O(n)
    Open on LeetCode ↗
  86. #86

    Word Ladder

    Hard
    Graphs AmazonGoogleMeta

    Approach: BFS over a pattern graph: each '*'-masked word indexes its 1-letter neighbors.

    ▼ Show solution ▲ Hide solution
    python
    from collections import defaultdict, deque
    
    def ladderLength(begin, end, wordList):
        if end not in wordList:
            return 0
        L = len(begin)
        pat = defaultdict(list)
        for w in wordList:
            for i in range(L):
                pat[w[:i] + '*' + w[i + 1:]].append(w)
        q = deque([(begin, 1)]); seen = {begin}
        while q:
            w, d = q.popleft()
            for i in range(L):
                key = w[:i] + '*' + w[i + 1:]
                for nb in pat[key]:
                    if nb == end: return d + 1
                    if nb not in seen:
                        seen.add(nb)
                        q.append((nb, d + 1))
        return 0
    ⏱ Time O(N·L²) · Space O(N·L²)
    Open on LeetCode ↗
  87. #87

    Climbing Stairs

    Easy
    Dynamic Programming AmazonAppleAdobe

    Approach: Fibonacci-style DP — ways(n) = ways(n−1) + ways(n−2).

    ▼ Show solution ▲ Hide solution
    python
    def climbStairs(n):
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  88. #88

    Min Cost Climbing Stairs

    Easy
    Dynamic Programming AmazonApple

    Approach: dp[i] = min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2]).

    ▼ Show solution ▲ Hide solution
    python
    def minCostClimbingStairs(cost):
        a, b = 0, 0
        for i in range(2, len(cost) + 1):
            a, b = b, min(b + cost[i - 1], a + cost[i - 2])
        return b
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  89. #89

    House Robber

    Medium
    Dynamic Programming AmazonGoogleMicrosoft

    Approach: dp[i] = max(dp[i−1], dp[i−2] + nums[i]). Only need two rolling values.

    ▼ Show solution ▲ Hide solution
    python
    def rob(nums):
        a, b = 0, 0
        for n in nums:
            a, b = b, max(b, a + n)
        return b
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  90. #90

    House Robber II

    Medium
    Dynamic Programming AmazonMicrosoft

    Approach: Run House Robber on two slices: skip first house, skip last house.

    ▼ Show solution ▲ Hide solution
    python
    def rob(nums):
        if len(nums) == 1:
            return nums[0]
        def line(arr):
            a, b = 0, 0
            for n in arr:
                a, b = b, max(b, a + n)
            return b
        return max(line(nums[1:]), line(nums[:-1]))
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  91. #91

    Longest Palindromic Substring

    Medium
    Dynamic Programming AmazonMicrosoftApple

    Approach: Expand around each center (odd and even length).

    ▼ Show solution ▲ Hide solution
    python
    def longestPalindrome(s):
        best = ''
        for i in range(len(s)):
            for l, r in ((i, i), (i, i + 1)):
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    if r - l + 1 > len(best):
                        best = s[l:r + 1]
                    l -= 1; r += 1
        return best
    ⏱ Time O(n²) · Space O(1)
    Open on LeetCode ↗
  92. #92

    Decode Ways

    Medium
    Dynamic Programming MetaAmazonMicrosoft

    Approach: dp[i] = dp[i−1] (1-digit) + dp[i−2] (2-digit) if valid.

    ▼ Show solution ▲ Hide solution
    python
    def numDecodings(s):
        if not s or s[0] == '0':
            return 0
        a, b = 1, 1
        for i in range(1, len(s)):
            cur = 0
            if s[i] != '0':
                cur += b
            two = int(s[i - 1:i + 1])
            if 10 <= two <= 26:
                cur += a
            a, b = b, cur
        return b
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  93. #93

    Coin Change

    Medium
    Dynamic Programming AmazonMetaGoogle

    Approach: Unbounded knapsack DP — dp[a] = min(dp[a], dp[a−c] + 1).

    ▼ Show solution ▲ Hide solution
    python
    def coinChange(coins, amount):
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    dp[a] = min(dp[a], dp[a - c] + 1)
        return dp[amount] if dp[amount] <= amount else -1
    ⏱ Time O(amount · |coins|) · Space O(amount)
    Open on LeetCode ↗
  94. #94

    Maximum Product Subarray

    Medium
    Dynamic Programming AmazonLinkedIn

    Approach: Track current max AND min (negatives can flip).

    ▼ Show solution ▲ Hide solution
    python
    def maxProduct(nums):
        res = lo = hi = nums[0]
        for n in nums[1:]:
            a, b = n * lo, n * hi
            lo, hi = min(n, a, b), max(n, a, b)
            res = max(res, hi)
        return res
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗
  95. #95

    Word Break

    Medium
    Dynamic Programming AmazonMetaGoogle

    Approach: dp[i] true if some j < i has dp[j] true and s[j:i] is in dict.

    ▼ Show solution ▲ Hide solution
    python
    def wordBreak(s, wordDict):
        words = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
        return dp[-1]
    ⏱ Time O(n²) · Space O(n)
    Open on LeetCode ↗
  96. #96

    Longest Increasing Subsequence

    Medium
    Dynamic Programming AmazonMicrosoftAdobe

    Approach: Patience sort: maintain 'tails' and binary-search each number's position.

    ▼ Show solution ▲ Hide solution
    python
    import bisect
    
    def lengthOfLIS(nums):
        tails = []
        for n in nums:
            i = bisect.bisect_left(tails, n)
            if i == len(tails):
                tails.append(n)
            else:
                tails[i] = n
        return len(tails)
    ⏱ Time O(n log n) · Space O(n)
    Open on LeetCode ↗
  97. #97

    Unique Paths

    Medium
    Dynamic Programming AmazonAppleBloomberg

    Approach: Each cell = left + above; rolling 1D array suffices.

    ▼ Show solution ▲ Hide solution
    python
    def uniquePaths(m, n):
        row = [1] * n
        for _ in range(1, m):
            for c in range(1, n):
                row[c] += row[c - 1]
        return row[-1]
    ⏱ Time O(m·n) · Space O(n)
    Open on LeetCode ↗
  98. #98

    Longest Common Subsequence

    Medium
    Dynamic Programming AmazonMicrosoftGoogle

    Approach: Classic 2D DP table — match adds 1, mismatch takes max(top, left).

    ▼ Show solution ▲ Hide solution
    python
    def longestCommonSubsequence(a, b):
        m, n = len(a), len(b)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]
    ⏱ Time O(m·n) · Space O(m·n)
    Open on LeetCode ↗
  99. #99

    Edit Distance

    Hard
    Dynamic Programming AmazonGoogleMetaMicrosoft

    Approach: 2D DP — match → diag; else 1 + min(insert, delete, replace).

    ▼ Show solution ▲ Hide solution
    python
    def minDistance(a, b):
        m, n = len(a), len(b)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1): dp[i][0] = i
        for j in range(n + 1): dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[m][n]
    ⏱ Time O(m·n) · Space O(m·n)
    Open on LeetCode ↗
  100. #100

    Best Time to Buy and Sell Stock with Cooldown

    Medium
    Dynamic Programming GoogleAmazon

    Approach: 3-state machine: hold / sold / rest — transitions each day.

    ▼ Show solution ▲ Hide solution
    python
    def maxProfit(prices):
        hold, sold, rest = -float('inf'), 0, 0
        for p in prices:
            prev_hold = hold
            hold = max(hold, rest - p)
            rest = max(rest, sold)
            sold = prev_hold + p
        return max(sold, rest)
    ⏱ Time O(n) · Space O(1)
    Open on LeetCode ↗