# Kth Smallest Instructions

This page explains Java solution to problem `Kth Smallest Instructions` using `Dynamic Programming` algorithm.

## Problem Statement

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.

Example 1:

Input: destination = [2,3], k = 1
Output: "HHHVV"
Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows:
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].

Example 2:

Input: destination = [2,3], k = 2
Output: "HHVHV"

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class KthSmallestInstruction {
public String kthSmallestPath(int[] destination, int k) {
int rowTarget = destination;
int colTarget = destination;

int[][] matrix = new int[rowTarget + 1][colTarget + 1];
for(int row = rowTarget; row >= 0; row--) {
for(int col = colTarget; col >= 0; col--) {
if(row == rowTarget && col == colTarget) {
matrix[row][col] = 1;
}
else if(row == rowTarget) {
matrix[row][col] = matrix[row][col + 1];
}
else if(col == colTarget) {
matrix[row][col] = matrix[row + 1][col];
}
else {
matrix[row][col] = matrix[row + 1][col] + matrix[row][col + 1];
}
}
}

return helper(matrix, 0, 0, k);
}

private String helper(int[][] matrix, int row, int col, int k) {
if(row + 1 == matrix.length && col + 1 == matrix.length) {
return "";
}
else if(row + 1 == matrix.length) {
StringBuilder sb = new StringBuilder();
while(++col < matrix.length) sb.append("H");
return sb.toString();
}
else if(col + 1 == matrix.length) {
StringBuilder sb = new StringBuilder();
while(++row < matrix.length) sb.append("V");
return sb.toString();
}
else {
if(matrix[row][col + 1] >= k) {
return "H" + helper(matrix, row, col + 1, k);
}
else {
return "V" + helper(matrix, row + 1, col, k - matrix[row][col + 1]);
}
}
}
}

``````

## Time Complexity

O(X * Y) Where
X is destination in horizontal direction
Y is destination in vertical direction

## Space Complexity

O(X * Y) Where
X is destination in horizontal direction
Y is destination in vertical direction