LeetCode 1643 - Kth Smallest Instructions

This problem asks us to generate a specific path for Bob from the top-left corner (0, 0) to a destination (row, column)

leetcodehardarraymathdynamic-programmingcombinatorics

LeetCode Problem 1643

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Combinatorics

Solution

Problem Understanding

This problem asks us to generate a specific path for Bob from the top-left corner (0, 0) to a destination (row, column) on a grid. Bob can only move right ('H') or down ('V'). Any sequence of moves that respects these directions and reaches the destination is a valid instruction. The challenge is to find the kth lexicographically smallest sequence. Lexicographic order here is the same as dictionary order, meaning 'H' comes before 'V'.

The inputs are a destination array [row, column] and an integer k. The output is a string of length row + column consisting of exactly row 'V' moves and column 'H' moves that represents the k-th sequence in lexicographic order.

Constraints ensure the grid is small (1 <= row, column <= 15), making combinatorial methods feasible, and k is always valid (1 <= k <= nCr(row + column, row)), meaning there is no need to check bounds for k. Edge cases include the smallest grid 1x1, grids with only one row or column, and k equal to 1 or the maximum number of sequences.

The main challenge is that generating all sequences and sorting them is not efficient enough. Instead, we can leverage combinatorics to skip entire branches of sequences and directly construct the k-th path.

Approaches

The brute-force approach generates all valid sequences using backtracking, stores them in a list, sorts the list, and returns the k-th sequence. While correct, this approach is too slow for large grids because the number of sequences grows combinatorially as nCr(row + column, row). For a 15x15 grid, there are 155117520 sequences, which is infeasible to generate.

The optimal approach uses combinatorics to guide the construction of the k-th sequence. At each step, we decide whether to place 'H' or 'V' by calculating how many sequences start with 'H' using the binomial coefficient. If k is smaller than or equal to the number of sequences starting with 'H', we choose 'H'; otherwise, we choose 'V' and adjust k by subtracting the skipped sequences. This approach constructs the answer in linear time with respect to the path length, without generating all sequences.

Approach Time Complexity Space Complexity Notes
Brute Force O(nCr(row+column, row) * (row+column)) O(nCr(row+column, row) * (row+column)) Generates all sequences and sorts them
Optimal O(row + column) O(1) Constructs sequence directly using combinatorics

Algorithm Walkthrough

  1. Compute the total number of horizontal moves (H_count = column) and vertical moves (V_count = row). The total length of the path is H_count + V_count.
  2. Initialize an empty string result to build the sequence.
  3. While there are remaining moves (H_count + V_count > 0):

a. If there are horizontal moves left, calculate the number of sequences that start with 'H' using the formula comb(H_count + V_count - 1, V_count).

b. Compare k with this number. If k is less than or equal, append 'H' to result and decrement H_count.

c. Otherwise, append 'V' to result, decrement V_count, and subtract the number of sequences starting with 'H' from k. 4. Repeat until all moves are used. Return the constructed string.

Why it works: At each step, the algorithm considers the lexicographic order. Using combinatorial counts allows skipping all sequences starting with 'H' when k is larger than this count, ensuring the sequence constructed is exactly the k-th in lexicographic order.

Python Solution

from math import comb
from typing import List

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        row, column = destination
        result = []
        H_count, V_count = column, row
        
        while H_count > 0 or V_count > 0:
            if H_count > 0:
                # Number of sequences starting with 'H'
                count_H_first = comb(H_count + V_count - 1, V_count)
                if k <= count_H_first:
                    result.append('H')
                    H_count -= 1
                else:
                    result.append('V')
                    V_count -= 1
                    k -= count_H_first
            else:
                result.append('V')
                V_count -= 1
        return ''.join(result)

The code begins by unpacking the destination coordinates. It initializes counters for horizontal and vertical moves and iteratively chooses the next move. At each step, it calculates how many sequences would start with 'H'. If k is within this range, 'H' is chosen. Otherwise, 'V' is chosen, and k is updated by removing the skipped sequences. This continues until the path is fully constructed.

Go Solution

package main

import "math/big"

func comb(n, k int) int {
    result := big.NewInt(1)
    for i := 0; i < k; i++ {
        result.Mul(result, big.NewInt(int64(n-i)))
        result.Div(result, big.NewInt(int64(i+1)))
    }
    return int(result.Int64())
}

func kthSmallestPath(destination []int, k int) string {
    row, column := destination[0], destination[1]
    H_count, V_count := column, row
    result := make([]byte, 0, H_count+V_count)
    
    for H_count > 0 || V_count > 0 {
        if H_count > 0 {
            count_H_first := comb(H_count+V_count-1, V_count)
            if k <= count_H_first {
                result = append(result, 'H')
                H_count--
            } else {
                result = append(result, 'V')
                V_count--
                k -= count_H_first
            }
        } else {
            result = append(result, 'V')
            V_count--
        }
    }
    return string(result)
}

In Go, the solution mirrors the Python approach. big.Int is used to safely compute combinatorial numbers to avoid integer overflow, although for the given constraints it is not strictly necessary. Slices are used to build the result efficiently.

Worked Examples

Example 1: destination = [2,3], k = 1

Step H_count V_count count_H_first k Choice Result
1 3 2 6 1 H H
2 2 2 3 1 H HH
3 1 2 2 1 H HHH
4 0 2 1 1 V HHHV
5 0 1 - 1 V HHHVV

Result is "HHHVV".

Example 2: destination = [2,3], k = 3

Step H_count V_count count_H_first k Choice Result
1 3 2 6 3 H H
2 2 2 3 3 H HH
3 1 2 2 3 V HHV
4 1 1 1 1 H HHVH
5 0 1 - 1 V HHVVH

Result is "HHVVH".

Complexity Analysis

Measure Complexity Explanation
Time O(row + column) We construct the path one character at a time, computing a combinatorial number at each step
Space O(row + column) The result string has length row + column

The combinatorial calculation uses simple factorial formulas and is fast for small inputs (max 15). No recursion or backtracking is required.

Test Cases

# Provided examples
assert Solution().kthSmallestPath([2,3], 1) == "HHHVV"  # first sequence
assert Solution().kthSmallestPath([2,3], 2) == "HHVHV"  # second sequence
assert Solution().kthSmallestPath([2,3], 3) == "HHVVH"  # third sequence

# Edge cases
assert Solution().kthSmallestPath([1,1], 1) == "HV"       # minimal grid
assert Solution().kthSmallestPath([1,1], 2) == "VH"       # minimal grid, second sequence
assert Solution().kthSmallestPath([15,1], 1) == "V"*15 + "H"  # single column, all V then H
assert Solution().k