Kth Smallest Instructions - Practice Coding Problems

Kth Smallest Instructions - Problem

Bob is standing at cell (0, 0), and he wants to reach destination: (row, column). He can only travel right and down. You are going to help Bob by providing instructions for him to reach destination.

The instructions are represented as a string, where each character is either:

'H', meaning move horizontally (go right), or
'V', meaning move vertically (go down).

Multiple instructions will lead Bob to destination. For example, if destination is (2, 3), both "HHHVV" and "HVHVH" are valid instructions.

However, Bob is very picky. Bob has a lucky number k, and he wants the kth lexicographically smallest instructions that will lead him to destination. k is 1-indexed.

Given an integer array destination and an integer k, return the kth lexicographically smallest instructions that will take Bob to destination.

Input & Output

Example 1 — Basic Case

$ Input: destination = [1,2], k = 1

› Output: HHV

💡 Note: Need 2 horizontal moves and 1 vertical move. All valid paths sorted: ["HHV", "HVH", "VHH"]. The 1st lexicographically smallest is "HHV".

Example 2 — Middle Element

$ Input: destination = [1,2], k = 2

› Output: HVH

💡 Note: All valid paths sorted: ["HHV", "HVH", "VHH"]. The 2nd lexicographically smallest is "HVH".

Example 3 — Last Element

$ Input: destination = [1,2], k = 3

› Output: VHH

💡 Note: All valid paths sorted: ["HHV", "HVH", "VHH"]. The 3rd lexicographically smallest is "VHH".

Constraints

1 ≤ destination[0], destination[1] ≤ 15
1 ≤ k ≤ C(destination[0] + destination[1], destination[0])

Visualization

Tap to expand

Understanding the Visualization

Input

destination = [1,2], k = 2 (need 2H, 1V moves)

Process

Use combinatorics to build path character by character

Output

Return the kth smallest instruction sequence

Key Takeaway

🎯 Key Insight: Use combinatorics to count paths starting with each character, allowing direct construction of the kth path without generating all possibilities

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is using combinatorics to count paths without generating them all. At each step, calculate how many valid paths start with 'H' using C(remaining-1, H-1). Choose 'H' if k falls within that range, otherwise choose 'V' and adjust k. Best approach is combinatorial with Time: O(h+v), Space: O(h+v).

Common Approaches

Approach	Time	Space	Notes
✓ Combinatorial Approach	O(h + v)	O(h + v)	Use combinatorics to count paths and build the kth path character by character
Generate All Paths	O(C(h+v,h) * (h+v) * log(C(h+v,h)))	O(C(h+v,h) * (h+v))	Generate all valid instruction sequences, sort them, and return the kth one

Combinatorial Approach — Algorithm Steps

Calculate total H and V moves needed
At each step, count paths starting with H using C(remaining-1, H-1)
Choose H or V based on where k falls, update k if choosing V
Continue until path is complete

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Paths with H

Count how many valid paths start with H using combinations

Choose Character

If k ≤ paths with H, choose H; otherwise choose V and update k

Continue Building

Repeat until all characters are determined

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int combinations(int n, int r) {
    if (r > n || r < 0) return 0;
    if (r == 0 || r == n) return 1;
    
    int dp[n + 1][r + 1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= (i < r ? i : r); j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    return dp[n][r];
}

char* solution(int* destination, int k) {
    int row = destination[0];
    int col = destination[1];
    int h = col;
    int v = row;
    
    char* result = malloc(100);
    int pos = 0;
    int remainingH = h;
    int remainingV = v;
    k--; // Convert to 0-indexed
    
    while (remainingH > 0 && remainingV > 0) {
        int pathsWithH = combinations(remainingH + remainingV - 1, remainingH - 1);
        
        if (k < pathsWithH) {
            result[pos++] = 'H';
            remainingH--;
        } else {
            result[pos++] = 'V';
            k -= pathsWithH;
            remainingV--;
        }
    }
    
    for (int i = 0; i < remainingH; i++) {
        result[pos++] = 'H';
    }
    for (int i = 0; i < remainingV; i++) {
        result[pos++] = 'V';
    }
    
    result[pos] = '\0';
    return result;
}

int main() {
    int destination[2];
    scanf("[%d,%d]", &destination[0], &destination[1]);
    int k;
    scanf("%d", &k);
    
    char* result = solution(destination, k);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(h + v)

Build path character by character, each step takes O(1) with precomputed combinations

✓ Linear Growth

Space Complexity

O(h + v)

Store the result string and combination values

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Combinatorial Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler