Sum of Two Character Array Integers

Overview

The problem asks us to take two character arrays representing signed integers and return their numerical sum. Since the inputs are provided as lists of characters (e.g., ['-', '1', '0']), we must first reconstruct the actual integer value by handling the optional negative sign and the positional value of each digit. Once both integers are parsed, a simple addition yields the result.

Brute Force

The most direct approach is to leverage high-level language features. In Python, we can join the character arrays into strings and then use the built-in int() constructor to perform the conversion. This handles signs and digit positioning automatically.

def sum_char_arrays(num1: list[str], num2: list[str]) -> int:
    # Join the characters into a single string
    str1 = "".join(num1)
    str2 = "".join(num2)
    
    # Convert strings to integers and return the sum
    return int(str1) + int(str2)

Time complexity: O(N + M) — We iterate through both arrays once to join them into strings and once more to parse the characters into an integer. Space complexity: O(N + M) — We create intermediate string representations of the arrays before conversion.

Optimal / Best Approach

To solve this more "algorithmically" and avoid intermediate string allocations, we can manually parse the arrays. We identify if the first character is a negative sign, then iterate through the remaining digits, maintaining a running total by multiplying the current sum by 10 and adding the new digit. This mimics how a compiler or a low-level library parses a string.

def sum_char_arrays(num1: list[str], num2: list[str]) -> int:
    def parse_array(arr: list[str]) -> int:
        if not arr:
            return 0
        
        is_negative = False
        start_idx = 0
        
        # Check for sign
        if arr[0] == '-':
            is_negative = True
            start_idx = 1
        elif arr[0] == '+': # Handle optional plus sign if needed
            start_idx = 1
            
        value = 0
        for i in range(start_idx, len(arr)):
            # Convert char to int using ASCII offset
            digit = ord(arr[i]) - ord('0')
            value = value * 10 + digit
            
        return -value if is_negative else value

    return parse_array(num1) + parse_array(num2)

Time complexity: O(N + M) — We perform a single pass over each array of length N and M. Space complexity: O(1) — We use a constant amount of extra space for variables regardless of input size (excluding the recursion stack if implemented recursively, though here it is iterative).

Edge Cases

• Single Digit Zero: Input ["0"] correctly yields 0.
• Maximum/Minimum Constraints: The problem specifies a range of [-100, 100]. Our manual parsing handles "-100" and "100" correctly as the loop processes all available digits.
• Negative Signs: The logic checks arr[0] specifically to determine the multiplier (1 or -1).

Why This Works

The value of a number like 123 is actually $1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0$. By iterating from left to right and multiplying the "current total" by 10 before adding the next digit, we effectively shift the existing digits to their correct power-of-ten positions.

Fast