Kth Smallest Instructions solution and explanation

from math import comb

def kthSmallestPath(destination, k):
    row, column = destination
    path = []
    for _ in range(row + column):
        if column > 0:  # Consider an 'H'
            count = comb(row + column - 1, row)
            if k > count:
                path.append('V')
                k -= count
                row -= 1
            else:
                path.append('H')
                column -= 1
        else:  # Only 'V' can be appended
            path.append('V')
            row -= 1
    return ''.join(path)

# Example Usage
print(kthSmallestPath([2, 3], 1))

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int binomialCoeff(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    int res = 1;
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

string kthSmallestPath(vector<int>& destination, int k) {
    int row = destination[0], column = destination[1];
    string result;
    for (int step = 0; step < row + column; ++step) {
        if (column > 0) {
            int count = binomialCoeff(row + column - 1, column - 1);
            if (k > count) {
                result += 'V';
                k -= count;
                --row;
            } else {
                result += 'H';
                --column;
            }
        } else {
            result += 'V';
            --row;
        }
    }
    return result;
}

int main() {
    vector<int> destination = {2, 3};
    int k = 1;
    cout << kthSmallestPath(destination, k) << endl;
    return 0;
}

import java.util.Arrays;

public class KthSmallestInstructions {
    
    public String kthSmallestPath(int[] destination, int k) {
        int row = destination[0], column = destination[1];
        StringBuilder result = new StringBuilder();
        int[][] dp = new int[row + 1][column + 1];
        for (int r = 0; r <= row; ++r) dp[r][0] = 1;
        for (int c = 0; c <= column; ++c) dp[0][c] = 1;
        for (int r = 1; r <= row; r++) {
            for (int c = 1; c <= column; c++) {
                dp[r][c] = dp[r-1][c] + dp[r][c-1];
            }
        }

        for (int step = 0; step < row + column; ++step) {
            if (column > 0) {
                if (k <= dp[row][column - 1]) {
                    result.append('H');
                    column -= 1;
                } else {
                    result.append('V');
                    k -= dp[row][column - 1];
                    row -= 1;
                }
            } else {
                result.append('V');
                row -= 1;
            }
        }
        return result.toString();
    }
    
    public static void main(String[] args) {
        KthSmallestInstructions solution = new KthSmallestInstructions();
        System.out.println(solution.kthSmallestPath(new int[]{2, 3}, 1));
    }
}

function kthSmallestPath(destination, k) {
    const [row, column] = destination;
    let dp = Array.from({ length: row + 1 }, () => Array(column + 1).fill(0));

    for (let r = 0; r <= row; ++r) dp[r][0] = 1;
    for (let c = 0; c <= column; ++c) dp[0][c] = 1;
    for (let r = 1; r <= row; ++r) {
        for (let c = 1; c <= column; ++c) {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }

    let res = '';
    let r = row, c = column;
    while (r > 0 && c > 0) {
        if (k <= dp[r][c - 1]) {
            res += 'H';
            c -= 1;
        } else {
            res += 'V';
            k -= dp[r][c - 1];
            r -= 1;
        }
    }
    while (c-- > 0) res += 'H';
    while (r-- > 0) res += 'V';

    return res;
}

console.log(kthSmallestPath([2, 3], 1));

func kthSmallestPath(destination []int, k int) string {
	v, h := destination[0], destination[1]
	n := v + h
	c := make([][]int, n+1)
	for i := range c {
		c[i] = make([]int, h+1)
		c[i][0] = 1
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= h; j++ {
			c[i][j] = c[i-1][j] + c[i-1][j-1]
		}
	}
	ans := []byte{}
	for i := 0; i < n; i++ {
		if h == 0 {
			ans = append(ans, 'V')
		} else {
			x := c[v+h-1][h-1]
			if k > x {
				ans = append(ans, 'V')
				k -= x
				v--
			} else {
				ans = append(ans, 'H')
				h--
			}
		}
	}
	return string(ans)
}