Common Edge Cases by Data Structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

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 arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

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 prev

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

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_lca

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

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 result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

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 result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

from collections import defaultdict, deque
from 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 count