Module Week 8

Pascal's Triangle

LeetCode 118

Easy ▼

Source

LeetCode 118 - Pascal's Triangle

Problem

Given an integer numRows, return the first numRows rows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

Function Signature

generate(numRows: int) -> List[List[int]]

Examples

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Input: numRows = 1
Output: [[1]]

This can be solved without recursion just as easily (if not easier) as it can with recursion. It is included as a warmup as there are not many problems in this topic graded less than medium. If you want recursion practice, go recursive.

Each row starts and ends with 1. Every other value is the sum of the two values directly above it in the previous row.

This is a straightforward construction problem. Build the triangle row by row. Each row has one more element than the last. The first and last elements are always 1; the middle elements come from summing pairs in the previous row.

⚙ Knowledge Hub: Recursion

Start with row 0 which is simply [1]
For each subsequent row i, create an array of length i + 1 filled with 1s
For each middle index j (from 1 to i - 1), set row[j] = previous[j-1] + previous[j]
Append the row to the triangle
Repeat until you have numRows rows

If you want to practise recursion: write a function that generates numRows - 1 rows first, then builds the final row from the last row returned.

def generate(numRows):
    triangle = []
    for i in range(numRows):
        row = [1] * (i + 1)
        for j in range(1, i):
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
        triangle.append(row)
    return triangle

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> tri;
    for (int i = 0; i < numRows; i++) {
        vector<int> row(i + 1, 1);
        for (int j = 1; j < i; j++)
            row[j] = tri[i-1][j-1] + tri[i-1][j];
        tri.push_back(row);
    }
    return tri;
}

public IList<IList<int>> Generate(int numRows) {
    var tri = new List<IList<int>>();
    for (int i = 0; i < numRows; i++) {
        var row = new int[i + 1];
        row[0] = row[i] = 1;
        for (int j = 1; j < i; j++)
            row[j] = tri[i-1][j-1] + tri[i-1][j];
        tri.Add(row.ToList());
    }
    return tri;
}

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> tri = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) row.add(1);
            else row.add(tri.get(i-1).get(j-1) + tri.get(i-1).get(j));
        }
        tri.add(row);
    }
    return tri;
}

Letter Combinations of a Phone Number

LeetCode 17

Medium ▼

Source

LeetCode 17 - Letter Combinations of a Phone Number

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. The mapping of digits to letters is the same as on a telephone keypad (2 = abc, 3 = def, …, 9 = wxyz). Return the answer in any order.

Function Signature

letterCombinations(digits: string) -> List[string]

Examples

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

Input: digits = ""
Output: []

This can be solved using recursion. It is very similar to the string permutation problem in this week's lecture. You need to accumulate the results in a list, rather than print the values out.

A straightforward way to do this in an object-oriented language is to add a list to the solution class provided by LeetCode, and append the strings to the list as you find them, rather than printing them out. Alternatively, a reference to a list can be passed as a parameter to the recursive function.

The code you produce here will be useful in the contest.

Use recursion / backtracking. Map each digit to its letters. At each step, pick one letter for the current digit and recurse on the remaining digits. When you have processed every digit, the current string is a complete combination.

⚙ Knowledge Hub: Recursion

Create a mapping from each digit to its letters (e.g. '2' -> "abc")
Write a recursive function backtrack(index, current)
Base case: if index == len(digits), append current to the result list
Recursive step: for each letter mapped to digits[index], call backtrack(index + 1, current + letter)
Start with backtrack(0, "")

Think of it as a tree of choices. Each level of the tree corresponds to one digit, and each branch corresponds to one of that digit's letters.

def letterCombinations(digits):
    if not digits:
        return []
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    result = []
    def backtrack(index, current):
        if index == len(digits):
            result.append(current)
            return
        for ch in mapping[digits[index]]:
            backtrack(index + 1, current + ch)
    backtrack(0, "")
    return result

class Solution {
    vector<string> result;
    string mapping[10] = {"","","abc","def","ghi",
                          "jkl","mno","pqrs","tuv","wxyz"};
    void backtrack(string& digits, int i, string& cur) {
        if (i == (int)digits.size()) { result.push_back(cur); return; }
        for (char ch : mapping[digits[i] - '0']) {
            cur.push_back(ch);
            backtrack(digits, i + 1, cur);
            cur.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        string cur;
        backtrack(digits, 0, cur);
        return result;
    }
};

public class Solution {
    IList<string> result = new List<string>();
    string[] map = {"","","abc","def","ghi",
                    "jkl","mno","pqrs","tuv","wxyz"};
    void Backtrack(string digits, int i, string cur) {
        if (i == digits.Length) { result.Add(cur); return; }
        foreach (char ch in map[digits[i] - '0'])
            Backtrack(digits, i + 1, cur + ch);
    }
    public IList<string> LetterCombinations(string digits) {
        if (digits.Length == 0) return result;
        Backtrack(digits, 0, "");
        return result;
    }
}

class Solution {
    List<String> result = new ArrayList<>();
    String[] map = {"","","abc","def","ghi",
                    "jkl","mno","pqrs","tuv","wxyz"};
    void backtrack(String digits, int i, StringBuilder cur) {
        if (i == digits.length()) { result.add(cur.toString()); return; }
        for (char ch : map[digits.charAt(i) - '0'].toCharArray()) {
            cur.append(ch);
            backtrack(digits, i + 1, cur);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return result;
        backtrack(digits, 0, new StringBuilder());
        return result;
    }
}

Decode Ways

LeetCode 91

Medium ▼

Source

LeetCode 91 - Decode Ways

Problem

A message containing letters A-Z can be encoded as numbers using the mapping 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". Given a string s containing only digits, return the total number of ways to decode it. The answer is guaranteed to fit in a 32-bit integer.

Function Signature

numDecodings(s: string) -> int

Examples

Input: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1 2) or "L" (12).

Input: s = "226"
Output: 3
Explanation: "226" can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero. "6" is different from "06".

Solve this with top-down dynamic programming. Get a recursive solution working first, then you will probably find the larger test cases time out. At this point, add memoisation and you should succeed.

At each position you have a choice: decode one digit (if it is 1-9) or two digits (if they form a number 10-26). A '0' on its own cannot be decoded.

Use top-down dynamic programming (recursion with memoisation). Define a function dp(i) that returns the number of ways to decode the substring from index i to the end. Cache the result for each i so you never recompute it.

⚙ Knowledge Hub: Dynamic Programming ⚙ Knowledge Hub: Recursion

Write dp(i) which returns the number of decodings from index i onwards
Base case: i == len(s) -> return 1 (one valid decoding reached)
If s[i] == '0', return 0 - no valid decoding starts with zero
Take one digit: ways = dp(i + 1)
If i + 1 < len(s) and the two-digit number s[i..i+1] is ≤ 26, also add dp(i + 2)
Store the result in a memo dictionary before returning

Without memoisation this is exponential. With it, each index is computed once, giving O(n) time.

def numDecodings(s):
    memo = {}
    def dp(i):
        if i in memo:
            return memo[i]
        if i == len(s):
            return 1
        if s[i] == '0':
            return 0
        ways = dp(i + 1)
        if i + 1 < len(s) and int(s[i:i+2]) <= 26:
            ways += dp(i + 2)
        memo[i] = ways
        return ways
    return dp(0)

class Solution {
    unordered_map<int, int> memo;
    int dp(const string& s, int i) {
        if (memo.count(i)) return memo[i];
        if (i == (int)s.size()) return 1;
        if (s[i] == '0') return 0;
        int ways = dp(s, i + 1);
        if (i + 1 < (int)s.size() && stoi(s.substr(i, 2)) <= 26)
            ways += dp(s, i + 2);
        return memo[i] = ways;
    }
public:
    int numDecodings(string s) {
        return dp(s, 0);
    }
};

public class Solution {
    Dictionary<int, int> memo = new Dictionary<int, int>();
    int Dp(string s, int i) {
        if (memo.ContainsKey(i)) return memo[i];
        if (i == s.Length) return 1;
        if (s[i] == '0') return 0;
        int ways = Dp(s, i + 1);
        if (i + 1 < s.Length && int.Parse(s.Substring(i, 2)) <= 26)
            ways += Dp(s, i + 2);
        memo[i] = ways;
        return ways;
    }
    public int NumDecodings(string s) {
        return Dp(s, 0);
    }
}

class Solution {
    Map<Integer, Integer> memo = new HashMap<>();
    int dp(String s, int i) {
        if (memo.containsKey(i)) return memo.get(i);
        if (i == s.length()) return 1;
        if (s.charAt(i) == '0') return 0;
        int ways = dp(s, i + 1);
        if (i + 1 < s.length()
                && Integer.parseInt(s.substring(i, i + 2)) <= 26)
            ways += dp(s, i + 2);
        memo.put(i, ways);
        return ways;
    }
    public int numDecodings(String s) {
        return dp(s, 0);
    }
}

The Coin Change Problem

HackerRank

Medium ▼

Source

HackerRank - The Coin Change Problem

Problem

Given an amount n and a list of coin denominations c, determine the number of ways to make change for n. Each denomination may be used any number of times. The order of coins does not matter - {1, 2} and {2, 1} count as the same combination.

Function Signature

getWays(n: int, c: List[int]) -> int

Examples

Input: n = 4, c = [1, 2, 3]
Output: 4
Explanation: {1,1,1,1}, {1,1,2}, {2,2}, {1,3}

Input: n = 10, c = [2, 5, 3, 6]
Output: 5

This is a classic dynamic programming problem, which you can solve using top-down dynamic programming. As always with top-down DP, get the recursive solution working on the small test cases, then bolt on the memoisation.

The key subtlety is avoiding duplicate combinations. Because order does not matter, you must not count {1, 2} and {2, 1} separately. The standard way to handle this is to process coins in order and never go back to an earlier coin.

Use top-down dynamic programming. Define dp(amount, idx) where amount is the remaining value to fill and idx is the current coin index. At each step you either use the current coin (stay at idx) or skip it (move to idx + 1).

⚙ Knowledge Hub: Dynamic Programming

Write dp(amount, idx)
Base case: amount == 0 -> return 1 (found a valid combination)
If amount < 0 or idx == len(c) -> return 0 (invalid path)
Recursive step: dp(amount - c[idx], idx) + dp(amount, idx + 1)
The first call uses the current coin again; the second skips it
Cache on (amount, idx) to avoid recomputation

By always moving forward through the coin list (never backwards), each combination is generated exactly once, eliminating duplicates.

def getWays(n, c):
    memo = {}
    def dp(amount, idx):
        if amount == 0:
            return 1
        if amount < 0 or idx == len(c):
            return 0
        if (amount, idx) in memo:
            return memo[(amount, idx)]
        ways = dp(amount - c[idx], idx) + dp(amount, idx + 1)
        memo[(amount, idx)] = ways
        return ways
    return dp(n, 0)

map<pair<int,int>, long long> memo;

long long dp(int amount, int idx, vector<long>& c) {
    if (amount == 0) return 1;
    if (amount < 0 || idx == (int)c.size()) return 0;
    auto key = make_pair(amount, idx);
    if (memo.count(key)) return memo[key];
    long long ways = dp(amount - (int)c[idx], idx, c)
                   + dp(amount, idx + 1, c);
    return memo[key] = ways;
}

long long getWays(int n, vector<long> c) {
    memo.clear();
    return dp(n, 0, c);
}

static Dictionary<(int,int), long> memo =
    new Dictionary<(int,int), long>();

static long Dp(int amount, int idx, List<long> c) {
    if (amount == 0) return 1;
    if (amount < 0 || idx == c.Count) return 0;
    var key = (amount, idx);
    if (memo.ContainsKey(key)) return memo[key];
    long ways = Dp(amount - (int)c[idx], idx, c)
              + Dp(amount, idx + 1, c);
    memo[key] = ways;
    return ways;
}

static long GetWays(int n, List<long> c) {
    memo.Clear();
    return Dp(n, 0, c);
}

static Map<String, Long> memo = new HashMap<>();

static long dp(int amount, int idx, long[] c) {
    if (amount == 0) return 1;
    if (amount < 0 || idx == c.length) return 0;
    String key = amount + "," + idx;
    if (memo.containsKey(key)) return memo.get(key);
    long ways = dp(amount - (int)c[idx], idx, c)
              + dp(amount, idx + 1, c);
    memo.put(key, ways);
    return ways;
}

static long getWays(int n, long[] c) {
    memo.clear();
    return dp(n, 0, c);
}

MODULE WEEK 8