Minimum/Maximum Values

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

# Python handles big integers natively, but many problems
# require simulating 32-bit behavior or preventing logical overflow.
 
import sys
 
# 32-bit signed integer limits
INT32_MIN = -2**31      # -2,147,483,648
INT32_MAX = 2**31 - 1   # 2,147,483,647
 
 
def safe_add_32bit(a: int, b: int) -> int | None:
    """
    Add two 32-bit integers safely.
    Returns None if result would overflow.
    """
    result = a + b
    if result < INT32_MIN or result > INT32_MAX:
        return None  # Or raise OverflowError
    return result
 
 
def reverse_integer(x: int) -> int:
    """
    Reverse digits of a 32-bit signed integer.
    Return 0 if reversal would overflow.
    
    This is a classic interview problem where overflow is the key test.
    """
    sign = -1 if x < 0 else 1
    x = abs(x)
    
    reversed_num = 0
    while x > 0:
        digit = x % 10
        
        # Check for overflow BEFORE it happens
        if reversed_num > (INT32_MAX - digit) // 10:
            return 0
        
        reversed_num = reversed_num * 10 + digit
        x //= 10
    
    reversed_num *= sign
    
    # Check final result in range
    if reversed_num < INT32_MIN or reversed_num > INT32_MAX:
        return 0
    
    return reversed_num
 
 
def safe_multiply(a: int, b: int, limit: int = INT32_MAX) -> int | None:
    """
    Multiply safely, returning None if overflow would occur.
    
    Key insight: Check BEFORE multiplying using division.
    """
    if a == 0 or b == 0:
        return 0
    
    # Handle signs
    result_positive = (a > 0) == (b > 0)
    a, b = abs(a), abs(b)
    
    # Check: would a * b exceed limit?
    # Rearrange: a * b > limit → a > limit / b
    if a > limit // b:
        return None
    
    result = a * b
    return result if result_positive else -result
 
 
def binary_search_midpoint_safe(left: int, right: int) -> int:
    """
    Calculate midpoint without overflow.
    
    Classic bug: (left + right) // 2 overflows when left + right > MAX_INT
    Solution: left + (right - left) // 2
    """
    # ❌ WRONG: Can overflow
    # mid = (left + right) // 2
    
    # ✅ CORRECT: Cannot overflow (assuming left <= right)
    mid = left + (right - left) // 2
    
    return mid
 
 
def string_to_integer(s: str) -> int:
    """
    Parse string to integer, handling overflow like atoi.
    Clamp to INT32_MIN or INT32_MAX on overflow.
    """
    s = s.strip()
    if not s:
        return 0
    
    # Handle sign
    sign = 1
    start = 0
    if s[0] in '+-':
        sign = -1 if s[0] == '-' else 1
        start = 1
    
    result = 0
    for i in range(start, len(s)):
        if not s[i].isdigit():
            break
        
        digit = int(s[i])
        
        # Check for overflow BEFORE adding
        if result > (INT32_MAX - digit) // 10:
            return INT32_MAX if sign == 1 else INT32_MIN
        
        result = result * 10 + digit
    
    return result * sign

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

import math
from typing import TypeVar
 
T = TypeVar('T')
 
 
def safe_divide(numerator: float, denominator: float) -> float | None:
    """
    Safe division that handles zero denominator.
    """
    if denominator == 0:
        return None  # Or raise ZeroDivisionError with context
    return numerator / denominator
 
 
def safe_modulo(value: int, divisor: int) -> int | None:
    """
    Safe modulo that handles zero divisor.
    """
    if divisor == 0:
        return None
    return value % divisor
 
 
def gcd(a: int, b: int) -> int:
    """
    Greatest Common Divisor with zero handling.
    By convention: gcd(x, 0) = gcd(0, x) = x
    And: gcd(0, 0) = 0 (by some definitions)
    """
    # Edge case: both zero
    if a == 0 and b == 0:
        return 0  # Or raise error - depends on definition
    
    # Edge case: one is zero
    if a == 0:
        return abs(b)
    if b == 0:
        return abs(a)
    
    # Standard Euclidean algorithm
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
 
 
def count_trailing_zeros(n: int) -> int:
    """
    Count trailing zeros in factorial of n.
    
    Edge case: 0! = 1, which has 0 trailing zeros
    """
    if n < 0:
        raise ValueError("Factorial undefined for negative numbers")
    
    # Edge case: 0! = 1, no trailing zeros
    if n == 0:
        return 0
    
    # Count factors of 5 (since we have more 2s than 5s)
    count = 0
    power_of_5 = 5
    while power_of_5 <= n:
        count += n // power_of_5
        power_of_5 *= 5
    
    return count
 
 
def power_with_edge_cases(base: float, exponent: int) -> float:
    """
    Calculate base^exponent with edge case handling.
    """
    # Edge case: 0^0 - mathematically controversial, typically 1
    if base == 0 and exponent == 0:
        return 1.0  # Convention in most programming contexts
    
    # Edge case: 0^negative - division by zero
    if base == 0 and exponent < 0:
        raise ValueError("0 raised to negative power is undefined")
    
    # Edge case: 0^positive = 0
    if base == 0:
        return 0.0
    
    # Edge case: any^0 = 1
    if exponent == 0:
        return 1.0
    
    # Edge case: 1^anything = 1
    if base == 1:
        return 1.0
    
    # Edge case: (-1)^even = 1, (-1)^odd = -1
    if base == -1:
        return 1.0 if exponent % 2 == 0 else -1.0
    
    # Standard calculation
    if exponent > 0:
        return base ** exponent
    else:
        return 1.0 / (base ** (-exponent))
 
 
def find_single_number(nums: list[int]) -> int:
    """
    Find the single number that appears once (others appear twice).
    Uses XOR - but needs to handle the case where answer is 0.
    
    Edge case: If the single number IS 0, XOR still works correctly
    because 0 ^ 0 = 0 (appears twice, cancels) and x ^ 0 = x.
    """
    result = 0
    for num in nums:
        result ^= num
    return result  # Works even if answer is 0!
 
 
def product_except_self(nums: list[int]) -> list[int]:
    """
    Return array where each element is product of all other elements.
    
    Edge cases with zeros:
    - No zeros: Normal calculation
    - One zero: Only the zero position has non-zero result
    - Multiple zeros: All positions are zero
    """
    n = len(nums)
    if n == 0:
        return []
    
    # Count zeros and track their position
    zero_count = 0
    zero_index = -1
    total_product = 1
    
    for i, num in enumerate(nums):
        if num == 0:
            zero_count += 1
            zero_index = i
        else:
            total_product *= num
    
    result = [0] * n
    
    if zero_count > 1:
        # Multiple zeros: all products are 0
        return result
    elif zero_count == 1:
        # One zero: only its position has non-zero product
        result[zero_index] = total_product
        return result
    else:
        # No zeros: divide total by each element
        for i in range(n):
            result[i] = total_product // nums[i]
        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

def integer_divide_toward_zero(dividend: int, divisor: int) -> int:
    """
    Divide integers with truncation toward zero.
    Python's // operator floors, which differs for negatives.
    
    Examples:
    7 // 2 = 3, -7 // 2 = -4 (floor)
    But we want: 7 / 2 = 3, -7 / 2 = -3 (truncate toward zero)
    """
    if divisor == 0:
        raise ZeroDivisionError("Division by zero")
    
    # Use true division and truncate toward zero
    return int(dividend / divisor)
 
 
def modulo_positive_result(value: int, mod: int) -> int:
    """
    Modulo that always returns positive result.
    Useful for array index wrapping, circular buffers, etc.
    
    Python's % already returns positive for positive mod,
    but this makes it explicit and cross-language safe.
    """
    if mod <= 0:
        raise ValueError("Modulus must be positive")
    
    result = value % mod
    if result < 0:
        result += mod
    return result
 
 
def sqrt_integer(n: int) -> int:
    """
    Integer square root (floor of sqrt).
    
    Edge case: Negative input - no real square root
    """
    if n < 0:
        raise ValueError("Cannot compute square root of negative number")
    
    if n == 0:
        return 0
    
    # Binary search for sqrt
    left, right = 1, n
    
    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid
        
        if square == n:
            return mid
        elif square < n:
            left = mid + 1
        else:
            right = mid - 1
    
    return right  # Floor of sqrt
 
 
def is_palindrome_number(x: int) -> bool:
    """
    Check if integer is a palindrome.
    
    Edge cases:
    - Negative numbers are NOT palindromes (the '-' doesn't mirror)
    - Numbers ending in 0 are only palindrome if they are 0
    """
    # Edge case: Negative numbers
    if x < 0:
        return False
    
    # Edge case: Numbers ending in 0 (except 0 itself)
    if x != 0 and x % 10 == 0:
        return False
    
    # Reverse half the number
    reversed_half = 0
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10
    
    # Check both even and odd length cases
    return x == reversed_half or x == reversed_half // 10
 
 
def ceil_division(a: int, b: int) -> int:
    """
    Ceiling division for integers.
    
    For positive numbers: (a + b - 1) // b
    But this doesn't work correctly for negatives!
    """
    if b == 0:
        raise ZeroDivisionError("Division by zero")
    
    # For positive/positive: ceiling division
    if (a >= 0 and b > 0) or (a <= 0 and b < 0):
        return (a + b - 1) // b if a > 0 else a // b
    else:
        # Mixed signs: ceiling is toward zero
        return a // b
 
 
def absolute_difference(a: int, b: int) -> int:
    """
    Compute |a - b| safely, handling overflow.
    
    Naive: abs(a - b) can overflow if a - b overflows
    """
    # If same sign, subtraction is safe
    if (a >= 0 and b >= 0) or (a < 0 and b < 0):
        return abs(a - b)
    
    # Different signs: convert to addition
    # |a - b| where a and b have opposite signs
    # = |a| + |b| when opposite signs
    return abs(a) + abs(b)
 
 
def compare_without_subtraction(a: int, b: int) -> int:
    """
    Compare two integers without subtraction (to avoid overflow).
    
    Returns: -1 if a < b, 0 if a == b, 1 if a > b
    """
    if a == b:
        return 0
    
    # Same sign: normal comparison is safe
    if (a >= 0 and b >= 0) or (a < 0 and b < 0):
        return -1 if a < b else 1
    
    # Different signs: positive is always greater
    return 1 if a >= 0 else -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
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

import math
 
 
def safe_float_equals(a: float, b: float, epsilon: float = 1e-9) -> bool:
    """
    Compare floating-point numbers with tolerance.
    
    Never use == for floating-point comparison!
    0.1 + 0.2 == 0.3 is False due to representation error.
    """
    # Edge case: Handle infinities
    if math.isinf(a) and math.isinf(b):
        return (a > 0) == (b > 0)  # Same sign infinity
    
    # Edge case: Handle NaN
    if math.isnan(a) or math.isnan(b):
        return False  # NaN is not equal to anything, including NaN
    
    # Relative and absolute tolerance combined
    return abs(a - b) <= epsilon * max(1.0, abs(a), abs(b))
 
 
def is_finite(x: float) -> bool:
    """Check if value is finite (not inf, not nan)."""
    return not (math.isinf(x) or math.isnan(x))
 
 
def safe_divide_float(a: float, b: float) -> float:
    """
    Safe float division with edge case handling.
    """
    # Edge case: NaN input
    if math.isnan(a) or math.isnan(b):
        return float('nan')
    
    # Edge case: Division by zero
    if b == 0:
        if a == 0:
            return float('nan')  # 0/0 is undefined
        return float('inf') if a > 0 else float('-inf')
    
    # Edge case: Infinity divided by infinity
    if math.isinf(a) and math.isinf(b):
        return float('nan')
    
    return a / b
 
 
def sqrt_safe(x: float) -> float:
    """
    Square root with edge case handling.
    """
    if math.isnan(x):
        return float('nan')
    
    if x < 0:
        return float('nan')  # Or raise ValueError
    
    if x == 0:
        return 0.0  # Preserves sign of zero
    
    if math.isinf(x):
        return float('inf')
    
    return math.sqrt(x)
 
 
def sum_array_precise(arr: list[float]) -> float:
    """
    Sum floating-point array with improved precision.
    Uses Kahan summation to reduce accumulation of rounding errors.
    """
    if not arr:
        return 0.0
    
    total = 0.0
    compensation = 0.0  # Running compensation for lost low-order bits
    
    for value in arr:
        # Edge case: Skip NaN values or handle specially
        if math.isnan(value):
            continue
        
        y = value - compensation      # Compensated value
        t = total + y                  # New total
        compensation = (t - total) - y # What we lost in the addition
        total = t
    
    return total
 
 
def binary_search_float(f, low: float, high: float, epsilon: float = 1e-9) -> float:
    """
    Binary search on floating-point range.
    
    Edge cases:
    - Infinite loop if epsilon too small (reaches precision limit)
    - Must handle case where low and high are very close
    """
    while high - low > epsilon:
        mid = (low + high) / 2
        
        # Prevent infinite loop at precision limit
        if mid == low or mid == high:
            break
        
        if f(mid):
            high = mid
        else:
            low = mid
    
    return (low + high) / 2
 
 
# Example: Representation issues
def demonstrate_float_issues():
    """Show common floating-point surprises."""
    
    # Equality surprise
    print(0.1 + 0.2 == 0.3)  # False!
    print(0.1 + 0.2)         # 0.30000000000000004
    
    # Use safe comparison instead
    print(safe_float_equals(0.1 + 0.2, 0.3))  # True
    
    # Accumulation error
    total = 0.0
    for _ in range(10):
        total += 0.1
    print(total == 1.0)  # False!
    print(total)         # 0.9999999999999999
    
    # Signed zero
    print(0.0 == -0.0)        # True
    print(1.0 / 0.0)          # inf
    print(1.0 / -0.0)         # -inf (different!)
    
    # NaN comparisons
    nan = float('nan')
    print(nan == nan)         # False!
    print(nan != nan)         # True!
    print(math.isnan(nan))    # True (correct way to check)

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

def binary_search_boundary_aware(arr: list[int], target: int) -> int:
    """
    Binary search with explicit boundary handling.
    
    Edge cases addressed:
    1. Empty array
    2. Target smaller than all elements
    3. Target larger than all elements
    4. Target at first/last position
    5. Midpoint overflow (conceptually - Python handles big ints)
    """
    if not arr:
        return -1
    
    left, right = 0, len(arr) - 1
    
    # Edge: Target outside array range
    if target < arr[left] or target > arr[right]:
        return -1
    
    while left <= right:
        # Safe midpoint calculation
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
 
 
def binary_search_first_occurrence(arr: list[int], target: int) -> int:
    """
    Find FIRST occurrence of target (handles duplicates).
    
    Boundary case: Multiple equal values - need leftmost.
    """
    if not arr:
        return -1
    
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid      # Found one, but continue searching left
            right = mid - 1   # Key: still search left half
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result
 
 
def binary_search_last_occurrence(arr: list[int], target: int) -> int:
    """
    Find LAST occurrence of target (handles duplicates).
    
    Boundary case: Multiple equal values - need rightmost.
    """
    if not arr:
        return -1
    
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid      # Found one, but continue searching right
            left = mid + 1    # Key: still search right half
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result
 
 
def sliding_window_max_boundary(nums: list[int], k: int) -> list[int]:
    """
    Sliding window maximum with boundary handling.
    
    Boundaries:
    1. k > len(nums): Invalid window
    2. k = len(nums): Single window = max of all
    3. Window formation: First k-1 elements don't form complete window
    """
    from collections import deque
    
    if not nums or k <= 0:
        return []
    
    # Edge: Window larger than array
    if k > len(nums):
        return []
    
    # Edge: Window equals array
    if k == len(nums):
        return [max(nums)]
    
    result = []
    dq = deque()  # Stores indices
    
    for i in range(len(nums)):
        # Remove indices outside window (left boundary)
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements (they can't be max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Only add to result after window is fully formed (right boundary)
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result
 
 
def kadane_with_edge_cases(nums: list[int]) -> int:
    """
    Maximum subarray sum (Kadane's algorithm) with edge cases.
    
    Edge cases:
    1. Empty array - undefined / return 0
    2. All negative - return maximum (least negative)
    3. Single element - return that element
    4. Overflow - sum could exceed int limits
    """
    if not nums:
        return 0  # Or raise error
    
    # Initialize with first element (not 0!)
    # This handles all-negative case correctly
    max_sum = nums[0]
    current_sum = nums[0]
    
    for i in range(1, len(nums)):
        # Either extend current subarray or start new
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum