時間與空間複雜度 — 經典 LC 程式碼逐題解析

1. TIME  : how many primitive ops as input n grows?
           -> count loops, recursion calls, work-per-call
2. SPACE : how much EXTRA memory (excludes the input itself)?
           -> data structures you allocate + recursion stack depth
3. CAN I DO BETTER?  (interviewers always ask)
           -> sort first? hashmap? two pointers? in-place?

n ≤ 10        → O(n!) / O(2^n)     backtracking, permutations
n ≤ 20        → O(2^n)             bitmask DP, subsets
n ≤ 100       → O(n³)              Floyd-Warshall, 3-nested DP
n ≤ 1,000     → O(n²)              nested loops, naive DP
n ≤ 100,000   → O(n log n)         sort, heap, balanced BST
n ≤ 1,000,000 → O(n)               single/two pass, sliding window, hashmap
n ≥ 10^9      → O(log n) / O(√n)   binary search, math

# python — LC 1
# time = O(n)   : single pass over nums
# space = O(n)  : hashmap can hold up to n entries
class Solution:
    def twoSum(self, nums, target):
        seen = {}                       # value -> index
        for i, x in enumerate(nums):
            if target - x in seen:      # O(1) average lookup
                return [seen[target - x], i]
            seen[x] = i

# python — LC 20
# time = O(n)   : each char pushed/popped at most once
# space = O(n)  : worst case all opening brackets "((((("
class Solution:
    def isValid(self, s):
        pair = {')': '(', ']': '[', '}': '{'}
        stack = []
        for c in s:
            if c in pair:
                if not stack or stack.pop() != pair[c]:
                    return False
            else:
                stack.append(c)
        return not stack

# python — LC 84
# time = O(n)   : each bar pushed once + popped once  (amortized O(1) per bar)
# space = O(n)  : the monotonic stack
class Solution:
    def largestRectangleArea(self, heights):
        stack = []          # indices, increasing heights
        heights.append(0)   # sentinel flushes the stack at the end
        best = 0
        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] > h:
                top = stack.pop()
                left = stack[-1] if stack else -1
                width = i - left - 1
                best = max(best, heights[top] * width)
            stack.append(i)
        return best

# python — LC 3
# time = O(n)        : left & right pointers each move forward ≤ n times
# space = O(min(n,Σ)): the window set, bounded by alphabet size Σ
class Solution:
    def lengthOfLongestSubstring(self, s):
        seen = set()
        left = best = 0
        for right, c in enumerate(s):
            while c in seen:        # shrink until window valid
                seen.remove(s[left])
                left += 1
            seen.add(c)
            best = max(best, right - left + 1)
        return best

# python — LC 704
# time = O(log n) : search space halves each iteration
# space = O(1)    : two pointers, iterative
class Solution:
    def search(self, nums, target):
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

# python — LC 875
# time = O(n log m) : binary search over speeds [1..max_pile] (log m), each check scans n piles
# space = O(1)
import math
class Solution:
    def minEatingSpeed(self, piles, h):
        def hours(speed):
            return sum(math.ceil(p / speed) for p in piles)   # O(n)
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            if hours(mid) <= h:     # feasible -> try slower
                hi = mid
            else:
                lo = mid + 1
        return lo

# python — LC 56
# time = O(n log n) : sorting dominates; the merge sweep is O(n)
# space = O(n)      : output list (O(log n)..O(n) for the sort itself)
class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])      # O(n log n)
        res = []
        for s, e in intervals:                  # O(n) sweep
            if res and s <= res[-1][1]:
                res[-1][1] = max(res[-1][1], e)  # overlap -> extend
            else:
                res.append([s, e])
        return res

# python — LC 215   (min-heap of size k approach)
# time = O(n log k) : n pushes/pops on a heap capped at size k
# space = O(k)      : heap holds at most k elements
import heapq
class Solution:
    def findKthLargest(self, nums, k):
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)     # evict smallest -> heap keeps top-k
        return heap[0]                  # smallest of the top-k = kth largest

# python — LC 104
# time = O(n)  : visit every node once
# space = O(h) : recursion stack = tree height  (h = log n balanced, h = n skewed)
class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

# python — LC 102
# time = O(n)  : each node enqueued/dequeued once
# space = O(w) : queue holds the widest level; w ≈ n/2 for a full tree -> O(n)
from collections import deque
class Solution:
    def levelOrder(self, root):
        if not root:
            return []
        res, q = [], deque([root])
        while q:
            level = []
            for _ in range(len(q)):          # snapshot current level size
                node = q.popleft()
                level.append(node.val)
                if node.left:  q.append(node.left)
                if node.right: q.append(node.right)
            res.append(level)
        return res

# python — LC 200
# time = O(m·n)  : every cell visited at most once
# space = O(m·n) : recursion stack worst case (grid is one big island / snake)
class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        def sink(r, c):
            if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] != '1':
                return
            grid[r][c] = '0'                 # mark visited in-place
            sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
        count = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == '1':
                    count += 1
                    sink(r, c)
        return count

# python — LC 207  (Kahn's BFS)
# time = O(V + E)  : build graph O(E), process each node + edge once
# space = O(V + E) : adjacency list + indegree array + queue
from collections import deque, defaultdict
class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for nxt, pre in prerequisites:
            graph[pre].append(nxt)
            indeg[nxt] += 1
        q = deque(i for i in range(numCourses) if indeg[i] == 0)
        done = 0
        while q:
            node = q.popleft()
            done += 1
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    q.append(nb)
        return done == numCourses      # all taken => no cycle

# python — LC 70
# time = O(n)  : one pass building dp
# space = O(1) : only keep the last two values (rolling variables)
class Solution:
    def climbStairs(self, n):
        a, b = 1, 1            # ways(0), ways(1)
        for _ in range(n - 1):
            a, b = b, a + b    # Fibonacci recurrence
        return b

# python — LC 322
# time = O(n · amount) : for each of `amount` sub-targets, try all n coins
# space = O(amount)    : 1D dp over target values
class Solution:
    def coinChange(self, coins, amount):
        INF = amount + 1
        dp = [0] + [INF] * amount         # dp[t] = min coins to make t
        for t in range(1, amount + 1):
            for c in coins:
                if c <= t:
                    dp[t] = min(dp[t], dp[t - c] + 1)
        return dp[amount] if dp[amount] != INF else -1

# python — LC 300  (V1: classic DP)
# time = O(n²)  : for each i, scan all j < i
# space = O(n)
class Solution:
    def lengthOfLIS(self, nums):
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

# python — LC 300  (V2: patience sorting + binary search)
# time = O(n log n) : n elements, each binary-searched into `tails`
# space = O(n)
import bisect
class Solution:
    def lengthOfLIS(self, nums):
        tails = []                       # tails[k] = smallest tail of an LIS of length k+1
        for x in nums:
            i = bisect.bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x             # replace -> keeps tails minimal
        return len(tails)

# python — LC 78
# time = O(n · 2^n)  : 2^n subsets, each costs O(n) to copy into the result
# space = O(n)       : recursion depth + current path (output not counted as aux)
class Solution:
    def subsets(self, nums):
        res = []
        def dfs(start, path):
            res.append(path[:])               # O(n) copy
            for i in range(start, len(nums)):
                path.append(nums[i])
                dfs(i + 1, path)
                path.pop()                    # undo (backtrack)
        dfs(0, [])
        return res

# python — LC 46
# time = O(n · n!) : n! permutations, each O(n) to build/copy
# space = O(n)     : recursion depth + used set
class Solution:
    def permute(self, nums):
        res = []
        def dfs(path, remaining):
            if not remaining:
                res.append(path[:])
                return
            for i in range(len(remaining)):
                dfs(path + [remaining[i]], remaining[:i] + remaining[i+1:])
        dfs([], nums)
        return res

# python — LC 42
# time = O(n)  : single pass, two converging pointers
# space = O(1) : just a few scalars (vs O(n) for the prefix/suffix-array version)
class Solution:
    def trap(self, height):
        l, r = 0, len(height) - 1
        left_max = right_max = water = 0
        while l < r:
            if height[l] < height[r]:
                left_max = max(left_max, height[l])
                water += left_max - height[l]
                l += 1
            else:
                right_max = max(right_max, height[r])
                water += right_max - height[r]
                r -= 1
        return water

SINGLE LOOP over n           → O(n)
TWO NESTED LOOPS (full)      → O(n²)
LOOP that halves/doubles     → O(log n)
LOOP + inner binary search   → O(n log n)
SORT anything                → O(n log n)  (then often an O(n) sweep)
RECURSION                    → (#calls) × (work per call); space = max depth
BACKTRACKING                 → (#solutions) × (cost each); space = recursion depth
HEAP of size k, n ops        → O(n log k)
GRAPH traversal              → O(V + E)
GRID traversal               → O(rows · cols)
DP                           → (#states) × (transition cost)
AMORTIZED (each item ≤1 push/pop) → O(n) even with an inner while-loop

□ Did I count the recursion stack?      (DFS = O(height), not O(1))
□ Is the output counted or excluded?    (usually excluded as "aux space")
□ Can a 2D dp collapse to 1D rolling?   (dp[i] depends only on dp[i-1]?)
□ Can two pointers replace an array?    (prefix-array → running variable)
□ In-place possible?                    (mark grid, reverse array, swap)

1. Two O(n) passes = still O(n)        (constants drop)
2. heapify = O(n);  n× heappush = O(n log n)   ← NOT the same!
3. Inner `while` ≠ automatically O(n²) — check amortized (sliding window, monotonic stack)
4. Slicing/concatenating inside a loop hides an O(n) cost → can make it O(n²)
5. HashMap is O(1) AVERAGE, O(n) worst (collisions) — say this out loud
6. Recursion space = stack depth = tree/recursion height