Kth Smallest Instructions

Hard
1438.

Kth Smallest Instructions

Kth Smallest Instructions is a hard coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.

A robot starts at cell (0, 0) and must reach destination = [row, column]. It can only move right, written 'H', or down, written 'V', so every route is a string of column letters 'H' and row letters 'V'.

Order all such strings lexicographically ('H' comes before 'V'). Given k, return the k-th string in that order (1-indexed).

Example 1

Input
destination = [2,2], k = 4
Output
VHHV
Explanation
The six routes in order are HHVV, HVHV, HVVH, VHHV, VHVH, VVHH.

Example 2

Input
destination = [1,3], k = 2
Output
HHVH

Example 3

Input
destination = [2,3], k = 1
Output
HHHVV

Constraints

  • destination.length == 2
  • 1 <= row, column <= 15
  • 1 <= k <= nCr(row + column, row)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} destination
 * @param {number} k
 * @return {string}
 */
var kthSmallestPath = function(destination, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Kth Smallest Instructions — Solution in Python, Java & C++

Kth Smallest Instructions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Kth Smallest Instructions is a hard coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.

Problem statement

A robot starts at cell (0, 0) and must reach destination = [row, column]. It can only move right, written 'H', or down, written 'V', so every route is a string of column letters 'H' and row letters 'V'.

Order all such strings lexicographically ('H' comes before 'V'). Given k, return the k-th string in that order (1-indexed).

Example 1

Input: destination = [2,2], k = 4
Output: VHHV
Explanation: The six routes in order are HHVV, HVHV, HVVH, VHHV, VHVH, VVHH.

Example 2

Input: destination = [1,3], k = 2
Output: HHVH

Example 3

Input: destination = [2,3], k = 1
Output: HHHVV

Constraints

  • destination.length == 2
  • 1 <= row, column <= 15
  • 1 <= k <= nCr(row + column, row)

Hints for Kth Smallest Instructions

  1. Hint 1

    Build the answer one letter at a time, deciding whether it starts with 'H' or 'V'.

  2. Hint 2

    If h moves right and v moves down remain, exactly C(h - 1 + v, v) of the remaining routes start with 'H'.

  3. Hint 3

    If k is at most that count, write 'H'; otherwise write 'V' and subtract the count from k.

How to solve Kth Smallest Instructions

Lexicographic ranking by counting: every route that starts with 'H' comes before every route that starts with 'V', and the number of routes beginning with 'H' is a binomial coefficient. So each letter is decided by comparing k with one count.

Approach

  1. Precompute Pascal's triangle up to 30 (C(30, 15) still fits in 32 bits).
  2. Let h = column, v = row. While letters remain: if h > 0, let c = C(h - 1 + v, v), the number of completions after an 'H'.
  3. If h > 0 and k <= c, append 'H' and decrement h. Otherwise append 'V', subtract c (0 when h == 0) from k, and decrement v.

Why it works

At each step the remaining routes split into a block starting with 'H' followed by a block starting with 'V'. If the k-th route lies in the first block (k <= c) its next letter is 'H' and its rank inside that block is still k; otherwise its next letter is 'V' and its rank inside the second block is k - c. The invariant "the answer is the k-th route of the remaining grid" holds to the end.

Complexity

  • Time — O(row + column)
  • Space — O(1) beyond the 31-row Pascal table

Pitfalls

  • 'H' (right) consumes the column count and sorts first; it is easy to swap the roles of row and column.
  • When h reaches 0 the rest of the answer is all 'V' — guard the binomial lookup so it does not read C(v - 1, v).
  • k is 1-indexed: the first route is k = 1.

Reference solution

Python

from typing import List
from math import comb

def kthSmallestPath(destination: List[int], k: int) -> str:
    v, h = destination
    out = []
    while h + v > 0:
        start_h = comb(h - 1 + v, v) if h > 0 else 0  # routes that begin with 'H'
        if h > 0 and k <= start_h:
            out.append('H')
            h -= 1
        else:
            out.append('V')
            k -= start_h
            v -= 1
    return ''.join(out)

Java

public static String kthSmallestPath(int[] destination, int k) {
    int[][] comb = new int[31][31];
    for (int i = 0; i <= 30; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
    }
    int v = destination[0], h = destination[1];
    StringBuilder out = new StringBuilder();
    while (h + v > 0) {
        int startH = h > 0 ? comb[h - 1 + v][v] : 0; // routes that begin with 'H'
        if (h > 0 && k <= startH) {
            out.append('H');
            h--;
        } else {
            out.append('V');
            k -= startH;
            v--;
        }
    }
    return out.toString();
}

C++

string kthSmallestPath(vector<int>& destination, int k) {
    vector<vector<int>> comb(31, vector<int>(31, 0));
    for (int i = 0; i <= 30; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
    }
    int v = destination[0], h = destination[1];
    string out;
    while (h + v > 0) {
        int startH = h > 0 ? comb[h - 1 + v][v] : 0; // routes that begin with 'H'
        if (h > 0 && k <= startH) {
            out += 'H';
            h--;
        } else {
            out += 'V';
            k -= startH;
            v--;
        }
    }
    return out;
}

JavaScript

var kthSmallestPath = function(destination, k) {
    var comb = [];
    for (var i = 0; i <= 30; i++) {
        comb.push([]);
        for (var j = 0; j <= i; j++) comb[i].push(j === 0 || j === i ? 1 : comb[i - 1][j - 1] + comb[i - 1][j]);
    }
    var v = destination[0], h = destination[1];
    var out = "";
    while (h + v > 0) {
        var startH = h > 0 ? comb[h - 1 + v][v] : 0; // routes that begin with 'H'
        if (h > 0 && k <= startH) {
            out += "H";
            h--;
        } else {
            out += "V";
            k -= startH;
            v--;
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming