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.

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"].

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

Solution

package com.vc.hard;

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

        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[0].length) {
            return "";
        }
        else if(row + 1 == matrix.length) {
            StringBuilder sb = new StringBuilder();
            while(++col < matrix[0].length) sb.append("H");
            return sb.toString();
        }
        else if(col + 1 == matrix[0].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