OneNoughtOne
0/361
Loading content...
Read aloud is unavailable in this browser.
You've designed the perfect algorithm. The time complexity is optimal, the space usage is reasonable, and your implementation passes all the provided test cases. You submit with confidence—only to receive a dreaded Wrong Answer or Runtime Error on hidden test cases.
This scenario is painfully familiar to every programmer, from coding competition veterans to senior engineers working on production systems. The cause? Edge cases—those boundary conditions and unusual inputs that your algorithm handles incorrectly because you never considered them.
The difference between a correct solution and a nearly-correct solution lies entirely in edge case handling. A solution that works for 99% of inputs but fails spectacularly on the remaining 1% is, in practical terms, wrong. In production systems, that 1% might represent critical transactions, security vulnerabilities, or data corruption risks.
By the end of this page, you will possess a systematic mental framework for identifying edge cases specific to each data structure. Rather than randomly testing inputs, you'll know precisely which boundary conditions to check based on the data structures your solution employs. This transforms edge case testing from guesswork into engineering discipline.
Before diving into specific data structures, we must establish the fundamental mindset that distinguishes exceptional engineers from merely competent ones.
Edge cases are not afterthoughts—they are design considerations.
When experienced engineers approach a problem, they don't first write the "happy path" solution and then retrofit edge case handling. Instead, they identify potential edge cases during the design phase, ensuring the algorithm's core logic inherently handles these scenarios or explicitly addresses them.
This proactive approach stems from understanding a crucial truth: every data structure has inherent edge cases dictated by its structural properties. An array has different edge cases than a linked list. A binary search tree has different edge cases than a hash table. Once you internalize the edge case profile of each data structure, you can systematically verify your solution against all relevant boundaries.
Every time you choose a data structure, immediately ask: 'What are the three smallest cases I need to handle?' For nearly every structure, these are: empty (zero elements), singleton (one element), and pair (two elements). If your algorithm works correctly for these three cases, you've eliminated a substantial class of bugs.
Arrays and lists are the most fundamental data structures, yet they harbor numerous edge cases that catch even experienced programmers. Their linear, indexed nature creates specific boundary conditions that must be systematically verified.
The Nature of Array Edge Cases:
Arrays are fixed-size (in most low-level implementations) or dynamically-resizing collections with O(1) random access. This structure implies edge cases around:
| Edge Case Category | Specific Case | Why It Fails | Example Scenario |
|---|---|---|---|
| Empty Array | Length = 0 | Index access causes out-of-bounds; loops don't execute | Find maximum in [] |
| Single Element | Length = 1 | Comparisons between elements fail; partition logic breaks | Sort [5], find pairs summing to k |
| Two Elements | Length = 2 | Minimum case for comparison-based operations | Merge two sorted arrays [1], [2] |
| First Element Access | Index 0 | Off-by-one in loop start; boundary update logic | Delete first element, sliding window start |
| Last Element Access | Index n-1 | Off-by-one in loop end; boundary termination | Delete last element, sliding window end |
| All Same Elements | [5,5,5,5,5] | Partitioning degeneracy; uniqueness assumptions | QuickSort pivot selection |
| Sorted Ascending | [1,2,3,4,5] | Already-sorted input; worst case for some algorithms | Insertion sort, certain pivot strategies |
| Sorted Descending | [5,4,3,2,1] | Reverse-sorted input; opposite worst case | Some search algorithms, merge operations |
| Negative Indices | Start or end < 0 | Language-dependent wraparound or error | Subarray with negative start |
| Index = Length | Access arr[n] | Off-by-one past array end | Loop termination condition errors |
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
def find_maximum(arr): """ Find maximum element in array. Demonstrates proper edge case handling. """ # Edge Case 1: Empty array if not arr: raise ValueError("Cannot find maximum of empty array") # Alternative: return None, return float('-inf') # Edge Case 2: Single element (works naturally with loop) maximum = arr[0] # Main logic handles all other cases including: # - Two elements # - All same elements # - Sorted/reverse sorted for i in range(1, len(arr)): # Note: starts at 1, not 0 if arr[i] > maximum: maximum = arr[i] return maximum def two_sum_indices(arr, target): """ Find two indices whose values sum to target. Returns None if no such pair exists. """ # Edge Case 1: Empty array - no pairs possible if not arr: return None # Edge Case 2: Single element - no pairs possible if len(arr) == 1: return None # Edge Case 3: Two elements - exactly one pair to check # (handled naturally by loop, but good to document) seen = {} for i, num in enumerate(arr): complement = target - num if complement in seen: return (seen[complement], i) seen[num] = i # Edge Case: No valid pair found return None def reverse_subarray(arr, start, end): """ Reverse subarray in-place from start to end (inclusive). """ # Edge Case: Invalid indices if start < 0 or end >= len(arr): raise IndexError("Index out of bounds") # Edge Case: start > end - invalid range if start > end: raise ValueError("Start must not exceed end") # Edge Case: start == end - single element, nothing to reverse # (handled naturally by while loop) # Edge Case: Empty array if not arr: return arr while start < end: arr[start], arr[end] = arr[end], arr[start] start += 1 end -= 1 return arrOff-by-one errors are the most common array-related bugs. They occur at loop boundaries (using <= instead of <), index calculations (forgetting that indices are 0-based), and slice operations (inclusive vs exclusive end). Always verify your loops with n=0, n=1, and n=2 cases.
Linked lists introduce a unique class of edge cases centered around pointer manipulation and node relationships. Unlike arrays with their fixed indexing, linked lists have dynamic connections that can break, cycle, or become inconsistent.
The Nature of Linked List Edge Cases:
Every linked list operation involves pointer manipulation—and every pointer manipulation is an opportunity for error. The key insight is that linked list edge cases arise from:
| Edge Case | When It Occurs | Common Failure Mode | Prevention Strategy |
|---|---|---|---|
| Null Head | Empty list | Null pointer dereference on head.next | Always check if head is null before access |
| Single Node List | Only head exists | Null dereference on head.next; update logic fails | Special case for single-node operations |
| Two Node List | head → node → null | Pointer swap logic fails; middle detection fails | Minimum case for relative-position operations |
| Operation on Head | Delete/insert at position 0 | Head reference not updated; orphaned old head | Use dummy head or explicit head update |
| Operation on Tail | Delete/insert at last position | Need to traverse to find previous node | Track tail pointer or use doubly-linked |
| Node Not Found | Search/delete non-existent value | Null return vs exception; infinite loop | Define clear return contract for not-found |
| Cycle Present | List contains loop | Infinite loop in traversal | Use Floyd's cycle detection before traversal |
| Self-Referencing Node | node.next = node | Special case of cycle | Check for immediate self-reference |
| Duplicate Values | Multiple nodes with same value | Delete-by-value ambiguity | Define semantics: first, last, or all |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def delete_node_at_position(head: ListNode, position: int) -> ListNode: """ Delete node at given position (0-indexed). Returns new head of list. Edge cases handled: 1. Empty list (head is None) 2. Invalid position (negative or beyond list length) 3. Delete head (position = 0) 4. Delete last node 5. Delete from single-node list """ # Edge Case 1: Empty list if head is None: raise ValueError("Cannot delete from empty list") # Edge Case 2: Negative position if position < 0: raise ValueError("Position cannot be negative") # Edge Case 3: Delete head node if position == 0: # Edge Case 3a: Single node list - return None (empty) # Edge Case 3b: Multi-node list - return second node return head.next # Traverse to node before the one to delete current = head for i in range(position - 1): if current.next is None: # Edge Case 4: Position beyond list length raise IndexError(f"Position {position} out of bounds") current = current.next # Edge Case 5: Position is exactly at list end (nothing to delete) if current.next is None: raise IndexError(f"Position {position} out of bounds") # Delete the node (works for last node too) current.next = current.next.next return head def find_middle_node(head: ListNode) -> ListNode: """ Find and return the middle node using slow/fast pointers. For even-length lists, returns the second middle node. Edge cases: 1. Empty list 2. Single node (it is the middle) 3. Two nodes (second is middle by convention) 4. Odd vs even length lists """ # Edge Case 1: Empty list if head is None: return None # Edge Case 2: Single node if head.next is None: return head slow = head fast = head # Fast pointer moves 2 steps, slow moves 1 # When fast reaches end, slow is at middle while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next return slow def has_cycle(head: ListNode) -> bool: """ Detect if linked list contains a cycle using Floyd's algorithm. Edge cases: 1. Empty list - no cycle possible 2. Single node without self-loop - no cycle 3. Single node with self-loop - cycle exists 4. Cycle at any position in list """ # Edge Case 1: Empty list if head is None: return False # Edge Case 2: Single node without cycle if head.next is None: return False slow = head fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next # Edge Case 3: Cycle detected (including self-loop) if slow == fast: return True return False def reverse_list(head: ListNode) -> ListNode: """ Reverse the linked list iteratively. Edge cases: 1. Empty list - return None 2. Single node - return same node (it's its own reverse) 3. Two nodes - simple swap """ # Edge Case 1: Empty list if head is None: return None # Edge Case 2: Single node - no reversal needed if head.next is None: return head prev = None current = head while current is not None: next_temp = current.next current.next = prev prev = current current = next_temp return prevMany linked list edge cases (especially those involving head modification) can be elegantly handled using a dummy head node. Create a new node that points to the real head: dummy = ListNode(-1); dummy.next = head. After operations, return dummy.next. This eliminates special-case code for head operations.
Trees introduce hierarchical relationships with their own unique edge cases. Unlike linear structures, trees have structural variations (balanced, skewed, complete) and recursive patterns that create subtle failure modes.
The Nature of Tree Edge Cases:
Tree edge cases arise from:
| Edge Case | Structure | Why It's Problematic | Algorithms Affected |
|---|---|---|---|
| Null Root | null | All operations must check before access | Every tree operation |
| Single Node | Only root exists | No children to traverse; height = 0 | Height, diameter, path sums |
| Root with One Child | Root → single child | Left-only vs right-only subtrees | Deletion, rotation, traversal |
| Left-Skewed Tree | Every node has only left child | Degenerates to linked list; O(n) height | BST operations become O(n) |
| Right-Skewed Tree | Every node has only right child | Same as left-skewed | BST search, insert, delete |
| Perfect Binary Tree | All leaves at same level, all nodes have 2 children | Maximum nodes for height; tests capacity | Level-order traversal, serialization |
| All Same Values (BST) | Every node has same value | BST property ambiguous; degenerate | BST insert, search, delete |
| Leaf Node Operations | Node with no children | Leaf detection, pruning logic | Deletion, path enumeration |
| Maximum Depth | Very deep tree | Stack overflow in recursion | All recursive algorithms |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def max_depth(root: TreeNode) -> int: """ Calculate maximum depth of binary tree. Edge cases: 1. Null root - depth is 0 2. Single node (no children) - depth is 1 3. One-sided tree - depth equals length of that side 4. Very deep tree - potential stack overflow """ # Edge Case 1: Null root if root is None: return 0 # Edge Case 2: Single node (handled naturally by recursion) # Left depth = 0, right depth = 0, max(0, 0) + 1 = 1 left_depth = max_depth(root.left) right_depth = max_depth(root.right) return max(left_depth, right_depth) + 1 def is_valid_bst(root: TreeNode) -> bool: """ Validate if tree is a valid Binary Search Tree. Edge cases: 1. Null root - valid (empty tree is trivially a BST) 2. Single node - valid (no violations possible) 3. All same values - INVALID (strict inequality required) 4. Duplicate values - depends on BST definition 5. Skewed tree - must check entire path """ def validate(node, min_val, max_val): # Edge Case 1: Null node - valid if node is None: return True # Edge Case 3 & 4: Value must be strictly within bounds # Using strict inequality means equal values are invalid if node.val <= min_val or node.val >= max_val: return False # Recursively validate subtrees with updated bounds return (validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)) return validate(root, float('-inf'), float('inf')) def inorder_traversal(root: TreeNode) -> list: """ Iterative inorder traversal using explicit stack. Handles deep trees without recursion stack overflow. Edge cases: 1. Null root - return empty list 2. Single node - return [node.val] 3. Left-only or right-only trees 4. Very deep trees (no stack overflow with iterative) """ result = [] stack = [] current = root # Edge Case 1: Null root handled by while condition while current is not None or stack: # Go as far left as possible while current is not None: stack.append(current) current = current.left # Process current node current = stack.pop() result.append(current.val) # Move to right subtree current = current.right return result def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: """ Find lowest common ancestor of two nodes in binary tree. Edge cases: 1. Null root - no LCA exists 2. Root is one of the nodes - root is LCA 3. Both nodes in left subtree 4. Both nodes in right subtree 5. Nodes in different subtrees - root is LCA 6. One node is ancestor of other """ # Edge Case 1: Null root if root is None: return None # Edge Case 2 & 6: Current node is one of the targets if root == p or root == q: return root # Search in both subtrees left_lca = lowest_common_ancestor(root.left, p, q) right_lca = lowest_common_ancestor(root.right, p, q) # Edge Case 5: Nodes in different subtrees if left_lca is not None and right_lca is not None: return root # Edge Case 3 & 4: Both nodes in one subtree return left_lca if left_lca is not None else right_lcaHash tables provide O(1) average-case operations but introduce a distinct set of edge cases around key handling, collision behavior, and the distinction between missing keys and explicit null values.
The Nature of Hash Table Edge Cases:
Hash table edge cases stem from:
| Edge Case | Description | Risk | Language/Library Behavior |
|---|---|---|---|
| Empty HashMap | No key-value pairs | get() returns null/None; iteration yields nothing | Safe but watch for null dereference on result |
| Key Not Found | Key never inserted | Same return as key→null mapping | Use containsKey/has/in before get, or get with default |
| Key Maps to Null | Key explicitly set to null | Indistinguishable from missing in some languages | Use containsKey to differentiate |
| Null Key | Using null as a key | Only some implementations allow this | Java HashMap: 1 null key allowed; Hashtable: no |
| Empty String Key | key = "" | Valid key but easy to confuse with missing | Ensure empty string is intentional |
| Hash Collision | Different keys, same hash | O(n) degradation with many collisions | Use good hash functions; know worst-case behavior |
| Key Mutability | Modifying key object after insertion | Key cannot be found anymore | Use immutable keys only (strings, numbers, tuples) |
| Concurrent Modification | Iterate while modifying | ConcurrentModificationException or undefined | Use concurrent collections or copy before iterate |
| Large Number of Keys | Millions of entries | Memory consumption, resize overhead | Consider streaming, partitioning, or databases |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124
def group_anagrams(strs: list[str]) -> list[list[str]]: """ Group strings that are anagrams of each other. Edge cases: 1. Empty list input - return empty list 2. List with one string - return [[string]] 3. Empty string in input - valid string, self-anagram 4. All strings are anagrams of each other 5. No two strings are anagrams 6. Duplicate strings """ from collections import defaultdict # Edge Case 1: Empty input if not strs: return [] anagram_map = defaultdict(list) for s in strs: # Edge Case 3: Empty string sorts to empty tuple - valid key # sorted("") returns [], tuple([]) = () - valid and consistent key = tuple(sorted(s)) anagram_map[key].append(s) # Edge Cases 4, 5, 6 handled naturally by grouping logic return list(anagram_map.values()) def two_sum_with_edge_cases(nums: list[int], target: int) -> list[int]: """ Find indices of two numbers that sum to target. Edge cases: 1. Empty list - no solution 2. Single element - no solution 3. Two elements that work 4. Multiple valid pairs - return first found 5. Duplicate values that sum to target 6. Zero in list (target could involve 0 + x = target) 7. Negative numbers """ # Edge Cases 1 & 2: Not enough elements if len(nums) < 2: return [] seen = {} # value -> index for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] # Edge Case 5: Duplicate values # We store index of first occurrence # If same number needed twice (e.g., 3 + 3 = 6), # complement will be found on second occurrence seen[num] = i # Edge Case: No valid pair exists return [] def first_non_repeating_char(s: str) -> int: """ Return index of first non-repeating character. Return -1 if no such character exists. Edge cases: 1. Empty string - no characters, return -1 2. Single character - it's non-repeating, return 0 3. All characters repeat - return -1 4. First character is non-repeating 5. Last character is non-repeating 6. Special characters and spaces """ from collections import Counter # Edge Case 1: Empty string if not s: return -1 # Edge Case 2: Single character if len(s) == 1: return 0 # Count occurrences - handles all character types char_count = Counter(s) # Find first non-repeating for i, char in enumerate(s): if char_count[char] == 1: return i # Edge Case 3: All characters repeat return -1 def safe_dict_get(d: dict, key, default=None): """ Safely get value from dict, distinguishing between: - Key not present - Key present with None value Edge cases demonstrated: """ # Standard get() cannot distinguish these cases: # d = {'a': None} # d.get('a') # returns None # d.get('b') # returns None - same result! # Solution 1: Use 'in' operator if key in d: return d[key] return default # Solution 2: Use sentinel value # _MISSING = object() # result = d.get(key, _MISSING) # if result is _MISSING: # return default # return resultStacks (LIFO) and queues (FIFO) are simpler than many data structures, but their edge cases around emptiness and underflow are critical to handle correctly.
The Nature of Stack/Queue Edge Cases:
Most stack and queue bugs come from:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113
def valid_parentheses(s: str) -> bool: """ Check if string has valid matching parentheses. Edge cases: 1. Empty string - valid (vacuously true) 2. Single character - invalid (unmatched) 3. Only opening brackets - invalid 4. Only closing brackets - invalid 5. Proper nesting of multiple types """ # Edge Case 1: Empty string if not s: return True # Edge Case 2: Odd length - cannot be balanced if len(s) % 2 == 1: return False stack = [] matching = {')': '(', '}': '{', ']': '['} for char in s: if char in '({[': stack.append(char) elif char in ')}]': # Edge Case 4: Closing bracket with empty stack if not stack: return False if stack[-1] != matching[char]: return False stack.pop() # Edge Case 3: Unmatched opening brackets return len(stack) == 0 def next_greater_element(nums: list[int]) -> list[int]: """ Find next greater element for each position using monotonic stack. Edge cases: 1. Empty array - return empty 2. Single element - no greater element, return [-1] 3. Descending array - all -1 (no greater elements) 4. Ascending array - each element's next is greater 5. All same elements - all -1 """ # Edge Case 1: Empty array if not nums: return [] n = len(nums) result = [-1] * n # Default: no greater element stack = [] # Stores indices for i in range(n): # Pop elements smaller than current while stack and nums[i] > nums[stack[-1]]: idx = stack.pop() result[idx] = nums[i] stack.append(i) # Elements remaining in stack have no greater element # (already initialized to -1) return result from collections import deque def sliding_window_maximum(nums: list[int], k: int) -> list[int]: """ Find maximum in each sliding window of size k. Edge cases: 1. Empty array - return empty 2. k > len(nums) - invalid, or return empty 3. k = 1 - each element is its own window max 4. k = len(nums) - single window, return [max(nums)] 5. All same elements - all windows have same max """ # Edge Case 1: Empty array if not nums: return [] # Edge Case 2: Window larger than array if k > len(nums): return [] # Edge Case 3: k = 1 if k == 1: return nums[:] result = [] dq = deque() # Stores indices of potential maximums for i in range(len(nums)): # Remove indices outside current window while dq and dq[0] < i - k + 1: dq.popleft() # Remove smaller elements (they cannot be maximum) while dq and nums[dq[-1]] < nums[i]: dq.pop() dq.append(i) # Add to result once we have a full window if i >= k - 1: result.append(nums[dq[0]]) return resultGraphs are among the most edge case-prone data structures due to their structural flexibility. A graph can have any number of nodes, any connectivity pattern, and may be directed, undirected, weighted, or cyclic.
The Nature of Graph Edge Cases:
Graph edge cases arise from:
| Edge Case | Description | Algorithms Affected |
|---|---|---|
| Empty Graph | No nodes, no edges | All traversal and path algorithms |
| Single Node | One node, no edges | Path finding, connectivity detection |
| Single Node with Self-Loop | Node with edge to itself | Cycle detection, path algorithms |
| Disconnected Components | Multiple isolated subgraphs | Traversal completeness, shortest paths |
| Fully Connected | Every node connects to every other | Performance testing, worst-case analysis |
| Tree (Acyclic) | Connected, no cycles | Cycle detection should return false |
| Multiple Cycles | Various interconnected cycles | Cycle detection, topological sort (should fail) |
| Negative Edge Weights | Edges with weight < 0 | Dijkstra fails; use Bellman-Ford |
| Negative Cycle | Cycle with negative total weight | No valid shortest path; must detect |
| Parallel Edges | Multiple edges between same nodes | Edge counting, path finding |
| Start Node Not in Graph | Query for non-existent node | Input validation required |
| Destination Unreachable | No path exists to target | Path reconstruction returns None/empty |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185
from collections import defaultdict, dequefrom typing import Optional def bfs_shortest_path( graph: dict, start, end) -> Optional[list]: """ Find shortest path in unweighted graph using BFS. Edge cases: 1. Empty graph - no path possible 2. Start not in graph - no path possible 3. End not in graph - no path possible 4. Start == End - path is [start] 5. No path exists (disconnected) 6. Multiple shortest paths (returns one) 7. Self-loops (handled correctly by visited set) """ # Edge Case 1: Empty graph if not graph: return None # Edge Case 2: Start not in graph if start not in graph: return None # Edge Case 3: End not in graph if end not in graph: return None # Edge Case 4: Start equals end if start == end: return [start] visited = {start} queue = deque([(start, [start])]) while queue: node, path = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: new_path = path + [neighbor] if neighbor == end: return new_path visited.add(neighbor) queue.append((neighbor, new_path)) # Edge Case 5: No path exists return None def has_cycle_directed(graph: dict) -> bool: """ Detect cycle in directed graph using DFS with coloring. Edge cases: 1. Empty graph - no cycle 2. Single node, no edges - no cycle 3. Single node with self-loop - has cycle 4. Tree structure - no cycle 5. Disconnected components - must check all """ # Edge Case 1: Empty graph if not graph: return False WHITE, GRAY, BLACK = 0, 1, 2 color = defaultdict(int) # All nodes start WHITE def dfs(node): color[node] = GRAY for neighbor in graph.get(node, []): if color[neighbor] == GRAY: # Edge Case 3: Back edge found (including self-loops) return True if color[neighbor] == WHITE: if dfs(neighbor): return True color[node] = BLACK return False # Edge Case 5: Check all nodes (might be disconnected) for node in graph: if color[node] == WHITE: if dfs(node): return True return False def topological_sort(graph: dict) -> Optional[list]: """ Return topological ordering of DAG. Returns None if graph has cycle (not a DAG). Edge cases: 1. Empty graph - return empty list 2. Single node - return [node] 3. Graph with cycle - return None 4. Multiple valid orderings - return any valid one 5. Disconnected components - all must be processed """ # Edge Case 1: Empty graph if not graph: return [] # Calculate in-degrees in_degree = defaultdict(int) for node in graph: for neighbor in graph[node]: in_degree[neighbor] += 1 # Find all nodes with no incoming edges queue = deque() for node in graph: if in_degree[node] == 0: queue.append(node) result = [] while queue: node = queue.popleft() result.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # Edge Case 3: Cycle detection if len(result) != len(graph): return None # Graph has cycle return result def number_of_islands(grid: list[list[str]]) -> int: """ Count number of islands (connected 1s) in 2D grid. Edge cases: 1. Empty grid - return 0 2. Grid with only water - return 0 3. Grid with only land (single island) - return 1 4. Single cell grid - 0 or 1 based on value 5. Diagonal connections (not counted as adjacent) """ # Edge Case 1: Empty grid if not grid or not grid[0]: return 0 rows, cols = len(grid), len(grid[0]) count = 0 def dfs(r, c): # Boundary check and water/visited check if (r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1'): return # Mark as visited grid[r][c] = '#' # Explore 4 directions (not diagonals) dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) for r in range(rows): for c in range(cols): if grid[r][c] == '1': count += 1 dfs(r, c) return countWe've examined edge cases across the fundamental data structures. The key insight is that edge cases are not random—they're systematic and predictable. Each data structure has characteristic edge cases that arise from its structural properties.
Here's a unified mental framework for edge case analysis:
You now understand how each data structure carries its own characteristic edge cases. In the next page, we'll dive deep into the most fundamental edge cases: empty inputs and single elements, which form the foundation of robust algorithm design.