43. Multiply Strings

At a Glance

Topic: math-geometry
Pattern: String math (grade-school multiplication)
Difficulty: Medium
Companies: Facebook, Amazon, Microsoft, Google, Twitter
Frequency: Medium
LeetCode: 43

Problem (one-liner)

Given two non-negative integer strings first and second without leading zeros (except "0"), return their product as a string without using built-in big integer libraries.

Recognition Cues

"Multiply strings" / numbers too large for 64-bit
Digit-by-digit convolution length len(first)+len(second)-1 positions

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — convert with bigint — violates constraint / language-dependent.
Optimal — array of length len(first)+len(second), accumulate digit_i * digit_j into result[i+j+1] with carries — O(n·m) time / O(n+m) space.

Optimal Solution

Go

package main

func multiply(first string, second string) string {
	if first == "0" || second == "0" {
		return "0"
	}
	digits := make([]int, len(first)+len(second))
	for leftIndex := len(first) - 1; leftIndex >= 0; leftIndex-- {
		for rightIndex := len(second) - 1; rightIndex >= 0; rightIndex-- {
			product := int(first[leftIndex]-'0')*int(second[rightIndex]-'0') + digits[leftIndex+rightIndex+1]
			digits[leftIndex+rightIndex+1] = product % 10
			digits[leftIndex+rightIndex] += product / 10
		}
	}
	start := 0
	for start < len(digits) && digits[start] == 0 {
		start++
	}
	result := make([]byte, len(digits)-start)
	for offset := range result {
		result[offset] = byte('0' + digits[start+offset])
	}
	return string(result)
}

JavaScript

function multiply(first, second) {
	if (first === '0' || second === '0') {
		return '0';
	}
	const digitCount = first.length + second.length;
	const digits = new Array(digitCount).fill(0);
	for (let leftIndex = first.length - 1; leftIndex >= 0; leftIndex--) {
		for (let rightIndex = second.length - 1; rightIndex >= 0; rightIndex--) {
			const product =
				(first.charCodeAt(leftIndex) - 48) * (second.charCodeAt(rightIndex) - 48) +
				digits[leftIndex + rightIndex + 1];
			digits[leftIndex + rightIndex + 1] = product % 10;
			digits[leftIndex + rightIndex] += Math.floor(product / 10);
		}
	}
	let start = 0;
	while (start < digits.length && digits[start] === 0) {
		start++;
	}
	return digits.slice(start).join('');
}