Solved Questions

Which structure, and why

The ask is literally have I seen this before. Membership questions with no ordering involved point straight at a hash set, which answers seen or not seen in O(1).

Intuition

Walk the array once and keep every value you have seen in a set. The moment a value is already in the set you have found the duplicate. One pass, O(n) time, O(n) space.

Complexity

Time O(n)Space O(n)

One pass over n numbers. The set stores every distinct value, so it can grow to n.

Flow

Submission

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for k in nums:
            if k in seen:
                return True
            else:
                seen.add(k)
        return False

Which structure, and why

The order of characters does not matter, only how many of each there are. When position is irrelevant and frequency is everything, reach for a hash map used as a counter.

Intuition

Two strings are anagrams exactly when every character appears the same number of times in both. Count the characters of each string and compare the two counts.

Complexity

Time O(n)Space O(k)

Counting each string is linear in its length. The two counters hold k distinct characters, 26 if the alphabet is English letters.

Flow

Submission

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

Which structure, and why

Every element needs a specific partner, target minus itself, and that lookup must be fast. A hash map from value to index turns find the complement into an O(1) question and kills the brute force pair loop.

Intuition

For each number, the partner it needs is target minus that number. Keep a map from value to index as you scan; if the partner was seen earlier the map hands you its index instantly, so one pass is enough.

Complexity

Time O(n)Space O(n)

One pass. The map stores a value-to-index pair for each number seen so far, so it can hold n entries.

Flow

Submission

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = {}
        for i, j in enumerate(nums):
            diff = target - nums[i]
            if diff in num_dict:
                return [num_dict[diff], i]
            num_dict[j] = i

Which structure, and why

Grouping things that are equal after some transformation is a hash map keyed by a canonical form. Here anagrams collapse to the same key once you sort their letters.

Intuition

Anagrams become identical when their letters are sorted, so the sorted string is a canonical key. Bucket every word under its sorted key and each bucket is one answer group.

Complexity

Time O(n k log k)Space O(n k)

Each of n words is sorted in k log k, then stored under that key. The map holds every character of every word.

Flow

Submission

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for i in strs:
            d[''.join(sorted(i))].append(i)
        return list(d.values())

Which structure, and why

Anything phrased as most frequent starts with a hash map of counts, because counting is what maps do. Selecting the top k afterwards can be a heap, or a bucket per frequency when you want linear time in n.

Intuition

Count how often each number appears, then drop each distinct value into a bucket indexed by that count. Sweep the buckets from high frequency to low and pick until you have k. No sort of the distinct keys is required.

Complexity

Time O(n)Space O(n)

Counting is one pass. There are at most n buckets and at most n distinct keys, so filling and sweeping the buckets is linear.

Flow

Submission

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = {}
        for i in nums:
            if i not in freq:
                freq[i] = 1
            else:
                freq[i] += 1

        bucket = [[] for _ in range(len(nums) + 1)]
        for num, count in freq.items():
            bucket[count].append(num)

        res = []
        for m in range(len(bucket) - 1, 0, -1):
            for j in bucket[m]:
                if len(res) == k:
                    continue
                res.append(j)
        return res

Which structure, and why

Each answer combines everything to the left of a position with everything to its right. That left times right shape is a prefix and suffix accumulation over plain arrays; no clever structure, just two passes.

Intuition

The answer at index i is the product of everything to its left times everything to its right. A forward pass writes the prefix products, a backward pass multiplies in the suffix products, and no division is ever needed.

Complexity

Time O(n)Space O(1)

Two linear passes. The output array is required, so extra space is only the two running products.

Flow

Submission

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [1] * length

        prefix = 1
        for i in range(length):
            answer[i] = prefix
            prefix *= nums[i]

        suffix = 1
        for i in range(length - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]

        return answer

Which structure, and why

The O(n) requirement on unsorted data forbids sorting, and the only question the algorithm ever asks is does the number k plus 1 exist. Pure existence checks mean a hash set.

Intuition

Only count a run from its start, and a number starts a run exactly when number minus one is absent. From each start keep asking whether the next integer exists in the set and count how far the run goes; every number is visited a constant number of times.

Complexity

Time O(n)Space O(n)

Building the set is linear. Each number is used as a run start at most once and visited a constant number of times inside the inner while.

Flow

Submission

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_long = 0
        nums = set(nums)
        for i in nums:
            if i - 1 not in nums:
                current_long = 1
                current_num = i
                while current_num + 1 in nums:
                    current_long += 1
                    current_num += 1
                max_long = max(current_long, max_long)
        return max_long

Which structure, and why

The grid is just a bag of n squared numbers with one extra and one hole. Membership of 1 through n squared is a hash set question, not a matrix algorithm.

Intuition

Flatten the grid into a list while you walk it. The first value already in the list is the duplicate. Then scan 1 through n squared and the integer absent from the list is the missing one.

Complexity

Time O(n^4)Space O(n^2)

The grid has n squared cells. Membership is checked against a list, which is linear in the cells already stored, so the nested scans are O(n^4). A set would drop this to O(n^2).

Flow

Submission

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        arr = []
        n = len(grid[0])
        twice_number = 0
        missing_number = 0
        for k in grid:
            for m in k:
                if m in arr:
                    twice_number = m
                else:
                    arr.append(m)
        for i in range(1, (n * n) + 1):
            if i not in arr:
                missing_number = i
        return [twice_number, missing_number]

Which structure, and why

The word sorted plus constant space rules out the hash map version of Two Sum. On sorted input a pair search needs no extra structure at all: two pointers whose moves are forced by the comparison.

Intuition

The array is sorted, so put a pointer at each end. A sum that is too big can only shrink by moving the right pointer left, and one that is too small can only grow by moving the left pointer right. Each step rules out one index for good.

Complexity

Time O(n)Space O(1)

The two pointers start at the ends and each index moves at most once. No extra structure.

Flow

Submission

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            total_sum = numbers[left] + numbers[right]
            if total_sum == target:
                return [left + 1, right + 1]
            if target < total_sum:
                right -= 1
            else:
                left += 1
        return []

Which structure, and why

A k-sum problem shrinks by fixing one element and solving the smaller sum on the rest. Once the array is sorted, the inner pair search is the classic two pointer sweep, and a set of tuples handles duplicate triples.

Intuition

Sort the array, then fix one number and the problem collapses into Two Sum II on the remainder: two pointers walking toward each other looking for the negated value. A set of tuples absorbs duplicate triples.

Complexity

Time O(n^2)Space O(n)

Sorting is n log n. Then each of n fixed values runs a linear two-pointer scan. The result set stores the unique triples.

Flow

Submission

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        result = set()
        for i, v in enumerate(nums):
            l = i + 1
            r = len(nums) - 1
            while l < r:
                total = nums[l] + nums[r] + nums[i]
                if total == 0:
                    result.add((nums[i], nums[l], nums[r]))
                    l += 1
                    r -= 1
                elif total < 0:
                    l += 1
                else:
                    r -= 1
        return list(result)

Which structure, and why

The answer ranges over pairs and the score is width times the smaller height. When giving up width is only ever worth it for a taller wall, two pointers starting at the ends can prune the whole pair space safely.

Intuition

Start with the widest container, one wall at each end. The shorter wall limits the area, so moving the taller wall inward can never help. Always step the shorter side inward and track the best area seen.

Complexity

Time O(n)Space O(1)

Each pointer moves inward at most n times. Only a few integers are stored besides the input.

Flow

Submission

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        l = 0
        r = len(heights) - 1
        max_area = 0
        while l < r:
            height = min(heights[l], heights[r])
            distance = r - l
            area = height * distance
            max_area = max(max_area, area)
            if heights[r] > heights[l]:
                l += 1
            else:
                r -= 1
        return max_area

Which structure, and why

The most recently opened bracket must be the first one closed, which is last in, first out spelled out. Any nesting, matching, or undo behaviour is a stack.

Intuition

A closer must match the most recent unmatched opener, which is exactly what a stack remembers. Push openers, pop when the matching closer arrives, and fail on anything else. A valid string ends with an empty stack.

Complexity

Time O(n)Space O(n)

Each character is pushed or popped at most once. The stack can hold every opener in a fully nested string.

Flow

Submission

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        bracket = {
            '(': ')',
            '{': '}',
            '[': ']',
        }
        for i in s:
            if i in bracket:
                stack.append(i)
            elif stack and i == bracket[stack[-1]]:
                stack.pop()
            else:
                return False
        return False if stack else True

Which structure, and why

Postfix means operands arrive before their operator, so you must remember recent values and consume the newest two when an operator shows up. Remember recent, consume newest is the definition of a stack.

Intuition

In postfix notation an operator always applies to the two most recent values. Push numbers; on an operator pop the right then the left operand, compute, and push the result back. The one value left at the end is the answer.

Complexity

Time O(n)Space O(n)

Each token is processed once. The stack holds numbers still waiting for an operator, at most n of them.

Flow

Submission

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token in ['+', '-', '*', '/']:
                b = stack.pop()
                a = stack.pop()
                if token == '+':
                    stack.append(a + b)
                elif token == '-':
                    stack.append(a - b)
                elif token == '*':
                    stack.append(a * b)
                else:   # '/' truncates toward zero
                    stack.append(int(a / b))
            else:
                stack.append(int(token))
        return stack[-1]

Which structure, and why

Next greater element to the right is the signature of a monotonic stack: keep the indices still waiting in decreasing temperature order, and resolve them the moment something bigger arrives.

Intuition

Keep a stack of day indices still waiting for a warmer day. Each new temperature resolves every colder day sitting on top of the stack, and the index gap is that day’s answer. Every index is pushed and popped at most once, so the whole thing is linear.

Complexity

Time O(n)Space O(n)

Each day is pushed once and popped at most once, so the nested while is still linear. The stack and the answer array are both O(n).

Flow

Submission

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        result = [0] * len(temperatures)
        for i, value in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < value:
                prev_day = stack.pop()
                result[prev_day] = i - prev_day
            stack.append(i)
        return result

Which structure, and why

Sorted input plus locate one value is the most literal binary search signal there is. Sorted means one comparison can discard half the data, so no structure beyond two index pointers is needed.

Intuition

Keep a closed interval that must contain the target if it exists. Probe the middle; the comparison tells you which half is impossible, so discard it and repeat until the pointers cross. Each probe halves the search space.

Complexity

Time O(log n)Space O(1)

Each comparison discards half of the remaining closed interval. Only three indices are stored.

Flow

Submission

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif target > nums[mid]:
                low = mid + 1
            else:
                high = mid - 1
        return -1

Which structure, and why

Those two conditions together mean the matrix read row by row is one fully sorted list. Whenever data is globally sorted, flatten it in your head and binary search the index range.

Intuition

Rows are sorted and each row continues the previous one, so the matrix is one sorted list in disguise. Binary search over the range 0 to rows times cols minus 1 and map mid back to a cell with divide and modulo.

Complexity

Time O(log(m n))Space O(1)

The matrix is treated as one sorted list of m times n cells, so binary search does log of that length. Mapping mid to a row and column is O(1).

Flow

Submission

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        low = 0
        high = rows * cols - 1
        while low <= high:
            mid = (low + high) // 2
            row = mid // cols
            col = mid % cols
            value = matrix[row][col]
            if target == value:
                return True
            elif target > value:
                low = mid + 1
            else:
                high = mid - 1
        return False

Which structure, and why

Best pair where the left element must come first and be small is a one pass sweep that remembers the minimum so far. It is a sliding window whose left edge only ever jumps forward to a new cheapest day.

Intuition

The left pointer tracks the cheapest day seen so far. Every later day is either a new cheapest buy or a candidate sell against that buy; record the best spread as you sweep once across the prices.

Complexity

Time O(n)Space O(1)

One pass. The left pointer only jumps forward, and a handful of integers track the best profit.

Flow

Submission

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        left = 0
        max_profit = 0
        for right in range(1, len(prices)):
            if prices[right] < prices[left]:
                left = right
            else:
                max_profit = max(max_profit, prices[right] - prices[left])
        return max_profit

Which structure, and why

Longest substring satisfying a constraint is the variable sliding window pattern: grow the right edge, shrink the left edge only when the constraint breaks. The constraint here is no duplicates, which is exactly what a hash set of the window contents tracks.

Intuition

Grow a window to the right and keep a set of the characters inside it. When the incoming character is already in the set, shrink from the left until it is gone. The window is duplicate free at all times, so its size is always a candidate answer.

Complexity

Time O(n)Space O(k)

Each character enters and leaves the window at most once. The set holds the distinct characters currently inside it, at most the alphabet size k.

Flow

Submission

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        max_length = 0
        seen = set()
        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            seen.add(s[right])
            max_length = max(max_length, right - left + 1)
        return max_length

Which structure, and why

The input is already a linked list and the operation is rewiring next pointers in place. No auxiliary structure is needed; three pointers named prev, curr, and next are the entire toolkit.

Intuition

Walk the list once, flipping each node’s next pointer to the node behind it. Save the next node before flipping so the rest of the list is never lost. When curr runs off the end, prev is the new head.

Complexity

Time O(n)Space O(1)

Each node is visited once. Only three pointers are kept besides the list itself.

Flow

Submission

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        prev = None
        while curr is not None:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Which structure, and why

Two sorted streams combine by repeatedly taking the smaller head, the merge step of merge sort. With linked nodes, a dummy head plus a tail pointer removes every empty list special case.

Intuition

A dummy head removes every edge case about starting the merged list. Repeatedly attach the smaller of the two current heads to the tail, then splice whichever list survives onto the end.

Complexity

Time O(n + m)Space O(1)

Every node from both lists is attached exactly once. The dummy and tail pointers are constant extra space.

Flow

Submission

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 or list2
        return dummy.next

Which structure, and why

Cycle detection in O(1) space is the fast and slow pointer trick. Whenever a linked list question mentions cycles, middles, or nth from the end, think two pointers at different speeds before thinking hash set.

Intuition

Send a slow pointer one step at a time and a fast pointer two. On a straight list the fast one simply runs off the end. On a cycle the fast one laps the slow one, and the moment they meet you know the loop exists.

Complexity

Time O(n)Space O(1)

The fast pointer runs at most a constant factor ahead of the slow one. Two pointers, no extra set.

Flow

Submission

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Which structure, and why

The operation is identical at every node and each subtree is a smaller copy of the same problem. That self similarity is the cue for plain tree recursion; the call stack is the only structure involved.

Intuition

A mirrored tree is just every node with its children swapped. Swap the two child pointers at the current node, then recurse into both children so the swap happens everywhere.

Complexity

Time O(n)Space O(h)

Every node is swapped once. Recursion depth is the height of the tree, n in the worst case of a straight line.

Flow

Submission

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        temp = root.left
        root.left = root.right
        root.right = temp
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

Which structure, and why

Depth of a tree is defined by the depth of its subtrees, so the answer at a node is built from the answers of its children. Whenever a tree property composes bottom up like that, it is a post order recursion.

Intuition

The depth of a tree is one more than the depth of its deeper subtree, and an empty tree has depth zero. That single sentence is the whole recursion.

Complexity

Time O(n)Space O(h)

Each node is visited once. The call stack follows the height of the tree.

Flow

Submission

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_height = self.maxDepth(root.left)
        right_height = self.maxDepth(root.right)
        return 1 + max(left_height, right_height)

Which structure, and why

The best path through any given node splits cleanly into left height plus right height, so each node combines information computed from its children. Combine children at every node is again the post order tree recursion shape.

Intuition

The longest path through a node is the height of its left subtree plus the height of its right subtree. Compute that candidate at every node and keep the maximum, since the best path might not pass through the root.

Complexity

Time O(n^2)Space O(h)

Height is recomputed from scratch at every node, and diameter then recurses into both children, so the work sums to quadratic on a skewed tree. Space is the recursion depth.

Flow

Submission

class Solution:
    def calculate_height(self, root: Optional[TreeNode]):
        if root is None:
            return 0
        left_height = self.calculate_height(root.left)
        right_height = self.calculate_height(root.right)
        return max(left_height, right_height) + 1

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_height = self.calculate_height(root.left)
        right_height = self.calculate_height(root.right)
        current_diameter = left_height + right_height

        left_diameter = self.diameterOfBinaryTree(root.left)
        right_diameter = self.diameterOfBinaryTree(root.right)

        return max(left_diameter, right_diameter, current_diameter)

Which structure, and why

The moment an API asks about prefixes, a hash set of whole words stops being enough, because a set cannot share partial matches. Words that share prefixes want to share a path, and a tree of characters, a trie, is exactly that.

Intuition

Each node maps a character to a child node, so a word is a path from the root. Insert walks the path and creates missing nodes, marking the final node as a word end. Search walks the same path and checks the mark, while startsWith only needs the path to exist.

Complexity

Time O(L)Space O(total characters)

Insert, search, and startsWith each walk one character of the argument, so they are linear in that word's length L. The trie stores a node per distinct prefix.

Flow

Submission

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endWord = False

class PrefixTree:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for k in word:
            if k not in curr.children:
                curr.children[k] = TrieNode()
            curr = curr.children[k]
        curr.endWord = True

    def search(self, word: str) -> bool:
        curr = self.root
        for k in word:
            if k not in curr.children:
                return False
            curr = curr.children[k]
        return curr.endWord

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for k in prefix:
            if k not in curr.children:
                return False
            curr = curr.children[k]
        return True

Which structure, and why

Every element is a binary choice, take it or skip it, and you want all combinations of those choices. That choose, recurse, undo shape is backtracking, and the call tree is the power set.

Intuition

Walk the array from left to right. At index i, first put nums[i] in the current subset and recurse, then pop it and recurse without it. When i runs off the end, the current subset is one complete answer.

Complexity

Time O(n 2^n)Space O(n)

There are 2^n subsets and each is copied in O(n). Extra space besides the output is the current path of length at most n.

Flow

Submission

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subset = []
        res = []

        def dfs(i):
            if len(nums) == i:
                res.append(subset.copy())
                return
            subset.append(nums[i])
            dfs(i + 1)
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

Which structure, and why

Duplicates in the input make the naive take or skip tree emit the same subset more than once. Sorting first lets you skip a run of equal values on the skip branch, which is the standard duplicate-aware backtracking move.

Intuition

Sort so equal numbers sit together. Take the current value and recurse as usual. On the skip branch, jump past every copy of that value so you never start the same subset twice.

Complexity

Time O(n 2^n)Space O(n)

Sorting is n log n. The take-or-skip tree still has O(2^n) leaves in the worst case, and each recorded subset is copied in O(n). The skip-equals loop does not change the bound.

Flow

Submission

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        subset = []
        res = []
        nums.sort()

        def dfs(i):
            if i == len(nums):
                res.append(subset.copy())
                return
            subset.append(nums[i])
            dfs(i + 1)
            subset.pop()
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i = i + 1
            dfs(i + 1)

        dfs(0)
        return res

Which structure, and why

You are building a list of picks that must hit an exact sum, and reuse is allowed. That is backtracking with a running total: stay on the same index to reuse, or step forward to skip.

Intuition

Keep a running total. If it equals the target, record the path. If it overshoots or the index runs out, stop. First append the current number and recurse on the same index so it can be reused, then pop and move to the next index.

Complexity

Time O(n^{T/m})Space O(T/m)

Each position may reuse a number, so the recursion depth is about target divided by the smallest candidate m, and each level branches by n. The path holds at most that many picks.

Flow

Submission

class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        subset = []
        res = []

        def dfs(i, total):
            if target == total:
                res.append(subset.copy())
                return
            if total > target or i >= len(nums):
                return
            subset.append(nums[i])
            dfs(i, total + nums[i])
            subset.pop()
            dfs(i + 1, total)

        dfs(0, 0)
        return res

Which structure, and why

Same backtracking as combination sum, but each index is used once and duplicate combinations must be suppressed. Sort, take the current value at i plus one, and on the skip branch jump past equal neighbours.

Intuition

Sort first. Take candidates[i] and recurse on i plus one so that value cannot be reused. After popping, skip every later copy of the same number before the skip recurse, so two identical combinations never start.

Complexity

Time O(2^n)Space O(n)

Each candidate is taken or skipped once after sorting, so the tree is O(2^n) in the worst case. The current subset is at most n long.

Flow

Submission

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()

        def dfs(i, subset, total):
            if total == target:
                res.append(subset.copy())
                return
            if i >= len(candidates) or target < total:
                return
            subset.append(candidates[i])
            dfs(i + 1, subset, total + candidates[i])
            while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]:
                i += 1
            subset.pop()
            dfs(i + 1, subset, total)

        dfs(0, [], 0)
        return res

Which structure, and why

A permutation is a path that uses each number once. Backtracking with a used-membership check (here, is this value already in the current path) generates every ordering.

Intuition

At each depth, try every number that is not already in the current path, push it, recurse, then pop. When the path is as long as the input, you have one permutation.

Complexity

Time O(n n!)Space O(n)

There are n! permutations and each is copied in O(n). The path and the membership scan of the path are O(n) extra.

Flow

Submission

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []

        def dfs():
            if len(subset) == len(nums):
                res.append(subset.copy())
                return
            for num in nums:
                if num in subset:
                    continue
                subset.append(num)
                dfs()
                subset.pop()

        dfs()
        return res

Which structure, and why

You are generating strings under two counters, opens used and closes used, with the invariant that you never have more closes than opens. That is backtracking on a character stack.

Intuition

An open is legal while fewer than n opens have been placed. A close is legal only while it would not outrun the opens already placed. When both counts hit n, the stack is one valid string.

Complexity

Time O(4^n / sqrt(n))Space O(n)

The number of well-formed strings is the nth Catalan number, which is Theta(4^n / n^{3/2}), and each string is built in O(n). The stack holds at most 2n characters.

Flow

Submission

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        stack = []

        def dfs(openCount, closeCount):
            if openCount == n and closeCount == n:
                res.append(''.join(stack))
                return
            if openCount < n:
                stack.append('(')
                dfs(openCount + 1, closeCount)
                stack.pop()
            if closeCount < openCount:
                stack.append(')')
                dfs(openCount, closeCount + 1)
                stack.pop()

        dfs(0, 0)
        return res

Which structure, and why

The board is a graph of four-direction neighbours, and you need a path whose labels match the word. That is DFS backtracking with a visited set that must be undone on the way out.

Intuition

From every cell, try to match the word starting at index 0. A step is legal only if the cell is in bounds, unused, and holds the next letter. Mark the cell, recurse in four directions, then unmark it so later starts can reuse it.

Complexity

Time O(m n 4^L)Space O(L)

A search can start at every cell. From there the four-direction DFS is bounded by 4^L for a word of length L. The visited set holds at most L cells.

Flow

Submission

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows = len(board)
        cols = len(board[0])
        visited = set()

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (
                r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or (r, c) in visited
                or board[r][c] != word[i]
            ):
                return False
            visited.add((r, c))
            found = (
                dfs(r, c + 1, i + 1)
                or dfs(r + 1, c, i + 1)
                or dfs(r - 1, c, i + 1)
                or dfs(r, c - 1, i + 1)
            )
            visited.remove((r, c))
            return found

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

Which structure, and why

A running kth largest while values keep arriving is the bounded heap pattern. A min heap capped at size k holds exactly the k best seen so far, and the kth largest is always sitting at the root.

Intuition

Keep a min heap holding only the k largest values seen so far, so its root is always the kth largest. Each add either joins the club and evicts the smallest member, or is too small and falls straight out.

Complexity

Time O(log k) per addSpace O(k)

The heap is trimmed to k on init and stays size k. Each add is a heap push and maybe a pop. Init heapify plus trims is O(n log k).

Flow

Submission

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.minHeap = nums
        self.k = k
        heapq.heapify(self.minHeap)
        while len(self.minHeap) > k:
            heapq.heappop(self.minHeap)

    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val)
        if len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap)
        return self.minHeap[0]

Which structure, and why

Every round needs the current maximum, and the pool changes between rounds. Repeated max or min from a changing collection is the textbook job of a priority queue, and sorting once would not survive the re-inserts.

Intuition

You always smash the two heaviest stones, and a max heap hands you exactly those. Python only has a min heap, so store negatives. Push back the difference after each smash and repeat until at most one stone remains.

Complexity

Time O(n log n)Space O(n)

Each smash is two pops and one push on a heap of at most n stones, and there are fewer than n smashes.

Flow

Submission

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        maxHeap = []
        for i in stones:
            heapq.heappush(maxHeap, -i)
        while len(maxHeap) > 1:
            x = heapq.heappop(maxHeap)
            y = heapq.heappop(maxHeap)
            val = -(y - x)
            heapq.heappush(maxHeap, val)
        return -maxHeap[0]

Which structure, and why

K best by some score without needing a full ordering means you should not sort everything. A heap capped at size k, with the worst current candidate on top, keeps eviction cheap and gives O(n log k).

Intuition

Keep a max heap of size k keyed on negated distance. Whenever it grows past k, pop the farthest point currently held. Whatever survives the whole pass is the k closest, without sorting all the points.

Complexity

Time O(n log k)Space O(k)

Each of n points is pushed onto a heap of size at most k, so each push or pop is log k. Only k points are stored.

Flow

Submission

import math
import heapq

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        max_heap = []
        for i in points:
            heapq.heappush(max_heap, (-self.calculate_distance(i[0], i[1], 0, 0), i))
            if len(max_heap) > k:
                heapq.heappop(max_heap)
        res = []
        for i in max_heap:
            res.append(i[1])
        return res

    def calculate_distance(self, x1, y1, x2, y2):
        return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

Which structure, and why

Selection by rank rather than full order hints at a heap or quickselect. Trimming a min heap down to k elements leaves the k largest inside with the answer at the root.

Intuition

Push every number into a min heap, then pop until only k values remain. The smallest survivor sits at the root, and with exactly the k largest values left, that root is the kth largest overall.

Complexity

Time O(n log n)Space O(n)

Every number is pushed onto a heap that can grow to n before it is trimmed to k, so the bound is n log n and n extra space. Trimming first would be n log k.

Flow

Submission

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []
        for i in nums:
            heapq.heappush(min_heap, i)
        while len(min_heap) > k:
            heapq.heappop(min_heap)
        return min_heap[0]

Which structure, and why

An island is a connected component on a grid graph. Counting components means: every time you find an unvisited land cell, you have a new island, then flood-fill so you never count it again.

Intuition

Scan every cell. When you hit land that is not yet visited, increment the count and DFS in four directions, marking every reachable land cell. Water and already-seen cells are walls for that search.

Complexity

Time O(m n)Space O(m n)

Each cell is visited a constant number of times. The visited set can hold every land cell, and DFS depth can be the whole grid.

Flow

Submission

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        visited = set()
        count = 0

        def dfs(r, c):
            if (
                r < 0
                or c < 0
                or r >= rows
                or c >= cols
                or grid[r][c] == '0'
                or (r, c) in visited
            ):
                return
            visited.add((r, c))
            dfs(r + 1, c)
            dfs(r, c + 1)
            dfs(r - 1, c)
            dfs(r, c - 1)

        for i in range(rows):
            for k in range(cols):
                if grid[i][k] == '1' and (i, k) not in visited:
                    count += 1
                    dfs(i, k)
        return count

Which structure, and why

Same connected-component scan as number of islands, except each flood-fill returns a size instead of just marking. The answer is the maximum of those sizes.

Intuition

DFS from an unvisited land cell returns 1 plus the area of its four neighbours. Track the best size seen while you walk the whole grid.

Complexity

Time O(m n)Space O(m n)

Same grid DFS as number of islands: every cell is entered at most once. Visited and the call stack are bounded by the grid size.

Flow

Submission

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        visited = set()
        max_area = 0

        def dfs(r, c):
            if (
                r < 0
                or c < 0
                or r >= rows
                or c >= cols
                or grid[r][c] == 0
                or (r, c) in visited
            ):
                return 0
            visited.add((r, c))
            area = 0
            area += dfs(r + 1, c)
            area += dfs(r, c + 1)
            area += dfs(r - 1, c)
            area += dfs(r, c - 1)
            return area + 1

        for i in range(rows):
            for k in range(cols):
                if grid[i][k] == 1 and (i, k) not in visited:
                    max_area = max(max_area, dfs(i, k))
        return max_area

Which structure, and why

Distance to the nearest source on an unweighted grid is multi-source BFS. Put every treasure in the queue first so the first time you reach a room is the shortest path.

Intuition

Enqueue every treasure at distance 0. Then expand layer by layer into empty rooms that have not been visited, writing the current distance into the cell. Walls and already-seen cells are skipped.

Complexity

Time O(m n)Space O(m n)

Multi-source BFS visits each cell a constant number of times. The queue and visited set can hold the whole grid.

Flow

Submission

from collections import deque

class Solution:
    def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        rows = len(grid)
        cols = len(grid[0])
        visited = set()
        q = deque()

        def addRoom(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == -1 or (r, c) in visited:
                return
            q.append([r, c])
            visited.add((r, c))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    q.append([r, c])
                    visited.add((r, c))

        dist = 0
        while q:
            for i in range(len(q)):
                r, c = q.popleft()
                grid[r][c] = dist
                addRoom(r + 1, c)
                addRoom(r, c + 1)
                addRoom(r - 1, c)
                addRoom(r, c - 1)
            dist += 1

Which structure, and why

A deep copy of a possibly cyclic object graph must copy each node once and rewire neighbours to the copies, not the originals. That is a graph traversal plus a map from old node to new node.

Intuition

The accepted submission uses Python deepcopy, which walks every reachable object once and rebuilds it, so the clone is correct. An interview write-up of the same idea is a hashmap DFS: clone the node, store it, then clone each neighbour.

Complexity

Time O(n + e)Space O(n)

deepcopy walks every node and every edge once. It stores a copy of each of the n nodes.

Flow

Submission

from copy import deepcopy

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        return deepcopy(node)

Which structure, and why

The number of ways to reach step n is ways(n-1) plus ways(n-2). That one-step recurrence on a single index is 1-D DP, and it is Fibonacci in disguise.

Intuition

You can only arrive from one step below or two steps below. Keep the last two way-counts and roll them forward until n. The base is: 1 step has 1 way, 2 steps have 2.

Complexity

Time O(n)Space O(1)

The loop runs from 3 to n. Only the last two way-counts are kept.

Flow

Submission

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

Which structure, and why

The cheapest way to leave index i is cost[i] plus the cheaper of the two next landings. Overlapping subproblems on a line of stairs: memoized recursion, or 1-D DP.

Intuition

dfs(i) is the min cost of finishing from step i: pay cost[i], then take the cheaper of dfs(i+1) and dfs(i+2). Cache each i. The answer is the cheaper of starting at 0 or starting at 1.

Complexity

Time O(n)Space O(n)

Each index is computed once and cached. The memo array and the recursion depth are both O(n).

Flow

Submission

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [-1] * len(cost)

        def dfs(i):
            if len(cost) <= i:
                return 0
            if dp[i] != -1:
                return dp[i]
            dp[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
            return dp[i]

        return min(dfs(0), dfs(1))

Which structure, and why

The decision at house i depends on later houses, and the same suffix is asked more than once. Cache the answer for each index: 1-D DP as memoized recursion.

Intuition

From house i you take cost[i] and then jump at least two houses ahead, choosing the better of i+2 and i+3. Memoize each i. The street starts at house 0 or house 1, so return the max of those two starts.

Complexity

Time O(n)Space O(n)

Each house index is memoized once. Recursion jumps by 2 or 3, but the cache still has n slots and the call stack is O(n) in the worst case.

Flow

Submission

class Solution:
    def rob(self, cost: List[int]) -> int:
        dp = [-1] * len(cost)

        def dfs(i):
            if len(cost) <= i or i < 0:
                return 0
            if dp[i] != -1:
                return dp[i]
            dp[i] = cost[i] + max(dfs(i + 2), dfs(i + 3))
            return dp[i]

        return max(dfs(0), dfs(1))