Skip to main content

36. Letter Combinations of a Phone Number

mediumAsked at Snowflake

Generate all letter combinations from a phone-keypad digit string. Snowflake asks this to test cartesian-product generation — the same enumeration shape that underlies their CROSS JOIN and LATERAL FLATTEN execution.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to set up LATERAL FLATTEN follow-up.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad screens.

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below.

Constraints

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Examples

Example 1

Input
digits = "23"
Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input
digits = ""
Output
[]

Example 3

Input
digits = "2"
Output
["a","b","c"]

Approaches

1. Iterative BFS (level-by-level)

Start with ['']. For each digit, append every letter to every existing string.

Time
O(3^n * 4^m)
Space
O(3^n * 4^m)
function letterCombinations(digits) {
  if (!digits) return [];
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  let result = [''];
  for (const d of digits) {
    const next = [];
    for (const prefix of result) {
      for (const c of map[d]) next.push(prefix + c);
    }
    result = next;
  }
  return result;
}

Tradeoff: Linear in output size. Allocates intermediate arrays per level.

2. Backtracking DFS (optimal)

Recurse digit-by-digit, pushing a letter, recursing, popping. Emit when length matches.

Time
O(3^n * 4^m * n)
Space
O(n) recursion
function letterCombinations(digits) {
  if (!digits) return [];
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  const result = [];
  function dfs(i, path) {
    if (i === digits.length) {
      result.push(path);
      return;
    }
    for (const c of map[digits[i]]) {
      dfs(i + 1, path + c);
    }
  }
  dfs(0, '');
  return result;
}

Tradeoff: Same output complexity; less intermediate allocation, easier to extend to filtering predicates.

Snowflake-specific tips

Snowflake interviewers want both versions and your trade-off on memory vs ease of extension. Bonus signal: pivot to LATERAL FLATTEN — Snowflake's UNNEST-like operator produces a cross-product of input row to expanded values, with the same fan-out behavior as this problem.

Common mistakes

  • Returning [''] for empty input instead of [] — read the spec carefully.
  • Hardcoding letter strings inside the recursion — extract the map for readability.
  • Mutating the path string then forgetting to unmutate after recursing (only an issue if using a list).

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Generate Parentheses (LC 22) — same backtracking shape with a constraint.
  • How does LATERAL FLATTEN work internally?
  • Letter Tile Possibilities (LC 1079).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why BFS vs DFS here?

BFS is easier to reason about (clear level-by-level expansion). DFS is more memory-efficient for very long inputs because the working set is just one path.

How does this map to LATERAL FLATTEN?

Snowflake's FLATTEN turns a 1-row input with an array column into one row per array element. Chained FLATTEN gives the same cartesian product behavior as concatenating letter sets digit-by-digit.

Practice these live with InterviewChamp.AI

Drill Letter Combinations of a Phone Number and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →