Common Bug Patterns in DSA

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

# BUGGY: Classic off-by-one in binary search
def binary_search_buggy(arr, target):
    left, right = 0, len(arr)  # BUG: should be len(arr) - 1 for inclusive
    
    while left < right:  # BUG: should check left <= right for inclusive bounds
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1  # BUG: inconsistent with initial right = len(arr)
    
    return -1
 
# CORRECT: Consistent inclusive bounds
def binary_search_correct(arr, target):
    if not arr:  # Handle empty array - boundary case!
        return -1
    
    left, right = 0, len(arr) - 1  # CORRECT: inclusive on both ends
    
    while left <= right:  # CORRECT: includes the case where left == right
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1  # CORRECT: consistent with inclusive bounds
    
    return -1
 
# BUGGY: Wrong loop bounds in prefix sum
def prefix_sum_buggy(arr):
    n = len(arr)
    prefix = [0] * n  # BUG: n+1 needed for 0-indexed prefix sums
    
    for i in range(n):
        prefix[i] = prefix[i-1] + arr[i]  # BUG: prefix[-1] on first iteration!
    
    return prefix
 
# CORRECT: Proper prefix sum with correct bounds
def prefix_sum_correct(arr):
    n = len(arr)
    prefix = [0] * (n + 1)  # CORRECT: extra element for "empty prefix"
    
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]  # CORRECT: 1-indexed prefix
    
    return prefix
    # prefix[0] = 0 (sum of zero elements)
    # prefix[1] = arr[0]
    # prefix[k] = sum of first k elements

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

# BUGGY: Wrong initialization for maximum subarray
def max_subarray_buggy(nums):
    max_sum = 0  # BUG: What if all numbers are negative?
    current_sum = 0
    
    for num in nums:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum  # Returns 0 for [-5, -3, -1], should return -1
 
# CORRECT: Initialize with first element
def max_subarray_correct(nums):
    if not nums:
        return 0  # Or raise an error - define behavior for empty input!
    
    max_sum = nums[0]  # CORRECT: Start with first element
    current_sum = nums[0]
    
    for i in range(1, len(nums)):  # Start from index 1
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum  # Returns -1 for [-5, -3, -1], correctly!
 
# BUGGY: DP initialization error
def unique_paths_buggy(m: int, n: int) -> int:
    """Count unique paths from top-left to bottom-right in an m×n grid."""
    dp = [[0] * n for _ in range(m)]
    
    # BUG: Forgot to initialize first row and column!
    # Without initialization, dp[0][0] = 0, so everything stays 0.
    
    for i in range(m):
        for j in range(n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]  # Also buggy for i=0 or j=0
    
    return dp[m-1][n-1]  # Returns 0 always!
 
# CORRECT: Proper DP initialization
def unique_paths_correct(m: int, n: int) -> int:
    dp = [[0] * n for _ in range(m)]
    
    # Initialize: only one way to reach any cell in first row or column
    for i in range(m):
        dp[i][0] = 1  # CORRECT: First column
    for j in range(n):
        dp[0][j] = 1  # CORRECT: First row
    
    # Fill rest of the table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]
 
# BUGGY: Graph initialization error
from collections import deque
 
def bfs_shortest_path_buggy(graph, start, end):
    """Find shortest path length from start to end."""
    queue = deque([(start, 0)])
    # BUG: Forgot to initialize visited set with start!
    visited = set()
    
    while queue:
        node, dist = queue.popleft()
        
        if node == end:
            return dist
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # BUG: start might be visited multiple times from different paths
 
# CORRECT: Initialize visited with start node
def bfs_shortest_path_correct(graph, start, end):
    queue = deque([(start, 0)])
    visited = {start}  # CORRECT: Mark start as visited immediately
    
    while queue:
        node, dist = queue.popleft()
        
        if node == end:
            return dist
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1

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

# BUGGY: Order of update error in DP
def house_robber_buggy(nums):
    """Maximum sum skipping adjacent elements."""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev_prev = nums[0]  # Maximum sum ending at i-2
    prev = max(nums[0], nums[1])  # Maximum sum ending at i-1
    
    for i in range(2, len(nums)):
        # BUG: Update prev before using it to calculate current!
        prev = max(prev, prev_prev + nums[i])  # Uses wrong prev!
        prev_prev = prev  # Now prev_prev = current, not the old prev
    
    return prev  # Wrong answer due to order bug
 
# CORRECT: Use temporary variable for correct order
def house_robber_correct(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev_prev = nums[0]
    prev = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        current = max(prev, prev_prev + nums[i])  # CORRECT: compute first
        prev_prev = prev  # CORRECT: shift window
        prev = current
    
    return prev
 
# BUGGY: In-place modification while iterating
def remove_duplicates_buggy(nums):
    """Remove duplicates from sorted array in-place."""
    for i, num in enumerate(nums):
        # BUG: Modifying nums while iterating causes chaos
        if i > 0 and num == nums[i-1]:
            nums.pop(i)  # Shifts remaining elements, indices now wrong!
    
    return len(nums)
 
# CORRECT: Two-pointer approach for in-place modification
def remove_duplicates_correct(nums):
    if len(nums) <= 1:
        return len(nums)
    
    write_idx = 1  # Where to write the next unique element
    
    for read_idx in range(1, len(nums)):
        if nums[read_idx] != nums[read_idx - 1]:
            nums[write_idx] = nums[read_idx]
            write_idx += 1
    
    return write_idx  # Length of the unique portion
 
# BUGGY: Reference mutation in backtracking
def permutations_buggy(nums):
    result = []
    
    def backtrack(current, remaining):
        if not remaining:
            result.append(current)  # BUG: Appends reference, not copy!
            return
        
        for i, num in enumerate(remaining):
            current.append(num)  # Mutate current
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()  # Restore current
    
    backtrack([], nums)
    return result  # All elements are empty lists!
 
# CORRECT: Append a copy, not the reference
def permutations_correct(nums):
    result = []
    
    def backtrack(current, remaining):
        if not remaining:
            result.append(current.copy())  # CORRECT: Append a copy!
            # Or: result.append(current[:]) 
            # Or: result.append(list(current))
            return
        
        for i, num in enumerate(remaining):
            current.append(num)
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    
    backtrack([], nums)
    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

# BUGGY: Wrong recurrence for coin change
def coin_change_buggy(coins, amount):
    """Minimum coins to make amount."""
    memo = {}
    
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        if remaining in memo:
            return memo[remaining]
        
        # BUG: Recurrence is wrong - we're not finding MINIMUM
        result = 0
        for coin in coins:
            result += dp(remaining - coin)  # BUG: Adding instead of min!
        
        memo[remaining] = result
        return result
    
    result = dp(amount)
    return result if result != float('inf') else -1
 
# CORRECT: Proper minimum recurrence
def coin_change_correct(coins, amount):
    memo = {}
    
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        if remaining in memo:
            return memo[remaining]
        
        result = float('inf')  # CORRECT: Start with infinity
        for coin in coins:
            # CORRECT: Take minimum of all choices
            result = min(result, 1 + dp(remaining - coin))
        
        memo[remaining] = result
        return result
    
    result = dp(amount)
    return result if result != float('inf') else -1
 
# BUGGY: Incomplete memoization key
def longest_common_subsequence_buggy(text1, text2):
    """LCS with buggy memoization."""
    memo = {}
    
    def dp(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        
        # BUG: Only using 'i' as key, ignoring 'j'!
        if i in memo:  # Wrong key - collides for different j values
            return memo[i]
        
        if text1[i] == text2[j]:
            result = 1 + dp(i + 1, j + 1)
        else:
            result = max(dp(i + 1, j), dp(i, j + 1))
        
        memo[i] = result
        return result
    
    return dp(0, 0)
 
# CORRECT: Full state in memoization key
def longest_common_subsequence_correct(text1, text2):
    memo = {}
    
    def dp(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        
        # CORRECT: Use tuple (i, j) as key
        if (i, j) in memo:
            return memo[(i, j)]
        
        if text1[i] == text2[j]:
            result = 1 + dp(i + 1, j + 1)
        else:
            result = max(dp(i + 1, j), dp(i, j + 1))
        
        memo[(i, j)] = result
        return result
    
    return dp(0, 0)
 
# BUGGY: Missing state in subproblem definition
def can_partition_to_equal_sum_buggy(nums):
    """Check if array can be partitioned into two equal-sum subsets."""
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    memo = {}
    
    def dp(i, current_sum):
        if current_sum == target:
            return True
        if i >= len(nums):
            return False
        
        # BUG: Only memoizing on current_sum, not considering index!
        if current_sum in memo:  # Different i values will collide
            return memo[current_sum]
        
        # Include or exclude current number
        result = dp(i + 1, current_sum + nums[i]) or dp(i + 1, current_sum)
        memo[current_sum] = result
        return result
    
    return dp(0, 0)
 
# CORRECT: Full state in memoization
def can_partition_to_equal_sum_correct(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    memo = {}
    
    def dp(i, current_sum):
        if current_sum == target:
            return True
        if i >= len(nums) or current_sum > target:
            return False
        
        # CORRECT: State is (i, current_sum)
        if (i, current_sum) in memo:
            return memo[(i, current_sum)]
        
        result = dp(i + 1, current_sum + nums[i]) or dp(i + 1, current_sum)
        memo[(i, current_sum)] = result
        return result
    
    return dp(0, 0)