1643. Kth Smallest Instructions

HardArrayMathDynamic ProgrammingCombinatorics
Leetcode Link

Problem Description

Bob starts from cell (0, 0) and wants to reach the destination at (row, column). He can only go right, denoted with H, or down, denoted with V. We need to give Bob a set of instructions that not only gets him to destination but also ensures that this set of instructions is the kth lexicographically smallest sequence possible.

Bob is picky and wants only the kth lexicographically smallest instructions, where k is 1-indexed. This means that if all possible correct sequences of instructions are sorted lexicographically, Bob wants the k-th sequence in this sorted order.

The destination is given in the form of an integer array [v, h] where v represents the vertical moves Bob needs to make downwards, and h represents the horizontal moves Bob needs to make to the right. In the case that destination is (2, 3), he needs to go down twice (VV) and right three times (HHH). The combinations HHHVV, HVHVH, VHHHV, etc., are different ways to arrange these moves.

Intuition

The solution is based on understanding combinatorics and lexicographical ordering. We base our solution on the facts that:

  1. There are comb(h + v, h) ways to arrange h horizontal moves and v vertical moves, with h + v being the total number of moves made.

  2. A lexicographically smaller sequence starts with the smallest possible character, which is H in this case.

So the intuition behind the solution is as follows:

  • We initialize the moves by calculating the total possible combinations to reach the destination given the current number of horizontal h and vertical v moves remaining. This is done using the combinatorial function comb.
  • At every step, we decide whether to place an H or a V. If we place an H, we reduce the number of horizontal moves, and if we place a V, we reduce the vertical moves.
  • We check if the remaining combinations after placing an H are less than k. If they are, it means that adding an H would not reach the k-th sequence. In such a case, we must add a V, decrement v, and adjust k by subtracting the number of sequences that would've started with an H.
  • If the remaining combinations after placing an H are more or equal to k, it means an H can be added to the sequence without surpassing the k-th smallest requirement.
  • We repeat this process until we run out of either horizontal or vertical moves.
  • As H is lexicographically smaller than V, we aim to add H whenever possible, following the rules above to respect the k-th smallest condition.

By iterating through all moves and following this process, we construct the kth smallest lexicographical sequence that leads Bob to his destination.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Solution Approach

The implementation is straightforward given our understanding of the intuition behind the problem. Here's a step-by-step explanation of the approach:

  1. We begin by identifying the number of vertical and horizontal moves required to reach the destination, v and h respectively.

  2. Define a string list ans which will hold the sequence of moves.

  3. Iterate through the combined number of moves (h + v).

  4. If there are no horizontal moves left (h is 0), we can only move down. So we add V to ans and continue.

  5. Otherwise, calculate the current number of combinations with x = comb(h + v - 1, h - 1). This represents the number of ways to arrange remaining moves if the next move is horizontal.

  6. Compare x with k. If k is larger, it means that the k-th sequence is not in the group of sequences that start with an H followed by all possible combinations of the remaining moves. Therefore, add V to ans, decrement v, and subtract x from k to reflect that we skip all those combinations that start with H.

  7. If k is not larger than x, it means that the k-th sequence does start with an H followed by the remaining moves. In this case, add H to ans and decrement h.

  8. After the loop, ans will contain the k-th lexicographically smallest instruction set.

In terms of algorithms, data structures, and patterns, we are using:

  • String/List manipulation: We use a list ans to build the sequence incrementally. The list is then converted to a string at the end.

  • Combinatorics: By using the combinatorial function comb, we calculate the number of ways to arrange the remaining moves.

  • Decision-making under constraints: At each step, the decision to add H or V is made based on the number of combinations remaining and the value of k.

  • Greedy approach: At each step, we take the locally optimal choice (adding H if possible) to reach the global optimization (k-th smallest sequence) while iterating through the process.

The code given in the solution efficiently performs this approach and keeps track of the sequence to be returned.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's illustrate the solution approach with an example where Bob has to reach a destination at (2, 3) and wants the 3rd lexicographically smallest sequence of instructions. This means v = 2 for downwards moves and h = 3 for rightwards moves, and k = 3.

  1. Bob needs 2 V moves and 3 H moves. The possible sequences, sorted lexicographically, are:

    1. HHHVV
    2. HHVHV
    3. HHVVH
    4. HVHHV
    5. HVHVH
    6. HVVHH
    7. VHHHV
    8. VHHVH
    9. VHVHH
    10. VVHHH

  2. Given the above sequences, we can see that the 3rd sequence is HHVVH. We will achieve the same result following our solution approach.

  3. Begin with h = 3, v = 2, and k = 3. List ans is currently empty.

  4. At the starting point (h + v = 5 moves remaining), we calculate the combinations possible with the first move being H, which is comb(4,2) = 6. This number indicates the count of sequences beginning with H.

  5. Comparing x (6) with k (3), since k is less than x, we add H to ans and decrement h to 2 (h + v = 4 moves remaining).

  6. We again calculate x = comb(3, 2) = 3 for the possibility of the next move being H.

  7. k equals x, so adding an H is still valid. We add another H and decrement h to 1 (h + v = 3 moves remaining).

  8. Calculate x = comb(2, 1) = 2. Since x is less than k (which is still 3), we cannot add an H because we need to find the 3rd sequence, and there are only 2 sequences starting with HHH. We add V to ans, decrement v to 1, and update k to k - x = 1 (h + v = 2 moves remaining).

  9. Now, calculate x = comb(1, 1) = 1 for the possibility of the next move being H.

  10. Since k (1) equals x (1), we can add H. We add H to ans, decrement h to 0 (h + v = 1 move remaining).

  11. With only one move remaining and h being 0, we add the final V.

  12. Now ans holds HHVVH, which is the 3rd lexicographically smallest sequence of instructions for Bob to reach (2, 3).

By following each step of our solution approach, we've successfully assembled the 3rd lexicographically smallest set of instructions for Bob's journey to the destination.

Solution Implementation

1from math import comb
2from typing import List
3
4class Solution:
5    def kthSmallestPath(self, destination: List[int], k: int) -> str:
6        vertical, horizontal = destination
7        answer = []
8
9        # Loop through the total number of moves (sum of vertical and horizontal moves)
10        for _ in range(horizontal + vertical):
11            # If there are no more horizontal moves, all remaining moves are vertical
12            if horizontal == 0:
13                answer.append("V")
14            else:
15                # Calculate the number of combinations that start with a horizontal move
16                combinations_with_h = comb(horizontal + vertical - 1, horizontal - 1)
17              
18                # If the kth path is greater than the number of paths starting with 'H', 
19                # then the path must start with a 'V' move instead.
20                if k > combinations_with_h:
21                    answer.append("V")
22                    vertical -= 1
23                    k -= combinations_with_h
24                else:
25                    # Otherwise, the path starts with a 'H' move
26                    answer.append("H")
27                    horizontal -= 1
28      
29        # Join all moves into a single path string and return it
30        return "".join(answer)
31
1class Solution {
2    public String kthSmallestPath(int[] destination, int k) {
3        int verticalSteps = destination[0];
4        int horizontalSteps = destination[1];
5        int totalSteps = verticalSteps + horizontalSteps;
6      
7        // Create a combination lookup table where c[i][j] represents the number
8        // of combinations of i elements taken j at a time
9        int[][] combinations = new int[totalSteps + 1][horizontalSteps + 1];
10      
11        // Base case: there is 1 way to choose 0 items out of i
12        combinations[0][0] = 1;
13        for (int i = 1; i <= totalSteps; ++i) {
14            combinations[i][0] = 1;
15            for (int j = 1; j <= horizontalSteps; ++j) {
16                // Calculate the combination count using Pascal's triangle relationship
17                combinations[i][j] = combinations[i - 1][j] + combinations[i - 1][j - 1];
18            }
19        }
20      
21        // Build the path using the combination count to make decisions
22        StringBuilder path = new StringBuilder();
23        for (int i = totalSteps; i > 0; --i) {
24            // If no horizontal steps are left, we must take a vertical step
25            if (horizontalSteps == 0) {
26                path.append('V');
27            } else {
28                // Check how many combinations would there be if we took a horizontal step first;
29                // this helps determine if kth path starts with 'H' or 'V' given the remaining steps
30                int combinationsIfHFirst = combinations[verticalSteps + horizontalSteps - 1][horizontalSteps - 1];
31                if (k > combinationsIfHFirst) {
32                    // If 'k' is larger than the number of combinations with 'H' first,
33                    // the kth path must start with 'V'. We subtract the combinations and reduce the vertical step
34                    path.append('V');
35                    k -= combinationsIfHFirst;
36                    --verticalSteps;
37                } else {
38                    // Otherwise, we append 'H' to our path and reduce the horizontal step
39                    path.append('H');
40                    --horizontalSteps;
41                }
42            }
43        }
44      
45        // Return the constructed path as a string
46        return path.toString();
47    }
48}
49
1class Solution {
2public:
3    // Function to find the k-th smallest path in a grid given the destination.
4    string kthSmallestPath(vector<int>& destination, int k) {
5        int v = destination[0]; // Vertical moves required
6        int h = destination[1]; // Horizontal moves required
7        int n = v + h; // Total moves required
8      
9        // Initialize combinatorial lookup table to store the binomial coefficients
10        int comb[n + 1][h + 1];
11        memset(comb, 0, sizeof(comb)); // Fill the array with zeroes
12        comb[0][0] = 1;
13      
14        // Populate the table with binomial coefficients using Pascal's Triangle
15        for (int i = 1; i <= n; ++i) {
16            comb[i][0] = 1;
17            for (int j = 1; j <= h; ++j) {
18                comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
19            }
20        }
21      
22        string ans; // String to hold the result
23      
24        // Construct the lexicographically k-th smallest path
25        for (int i = 0; i < n; ++i) {
26            if (h == 0) { // If no more horizontal moves, then move vertical
27                ans.push_back('V');
28            } else {
29                // Find the number of sequences starting with 'H'
30                int countHStart = comb[v + h - 1][h - 1];
31              
32                // If k is greater than countHStart, then the current move must be 'V'
33                if (k > countHStart) {
34                    ans.push_back('V');
35                    --v; // One less vertical move needed
36                    k -= countHStart; // Reduce k by the number of sequences counted
37                } else {
38                    // If k is within the range, the current move is 'H'
39                    ans.push_back('H');
40                    --h; // One less horizontal move needed
41                }
42            }
43        }
44      
45        return ans; // Return the constructed path
46    }
47};
48
1function kthSmallestPath(destination: number[], k: number): string {
2    let verticalMoves = destination[0]; // Vertical moves required
3    let horizontalMoves = destination[1]; // Horizontal moves required
4    let totalMoves = verticalMoves + horizontalMoves; // Total moves required
5  
6    // Initialize combinatorial lookup table to store the binomial coefficients
7    let comb: number[][] = Array.from({ length: totalMoves + 1 }, () => Array(horizontalMoves + 1).fill(0));
8    comb[0][0] = 1;
9
10    // Populate the table with binomial coefficients using Pascal's Triangle
11    for (let i = 1; i <= totalMoves; ++i) {
12        comb[i][0] = 1;
13        for (let j = 1; j <= horizontalMoves; ++j) {
14            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
15        }
16    }
17
18    let path = ''; // String to hold the result
19
20    // Construct the lexicographically k-th smallest path
21    for (let i = 0; i < totalMoves; ++i) {
22        if (horizontalMoves === 0) { // If no more horizontal moves, then move vertically
23            path += 'V';
24            continue;
25        }
26      
27        // Find the number of sequences starting with 'H'
28        let countHStart = comb[verticalMoves + horizontalMoves - 1][horizontalMoves - 1];
29
30        // If k is greater than countHStart, then the current move must be 'V'
31        if (k > countHStart) {
32            path += 'V';
33            verticalMoves--; // One less vertical move is needed
34            k -= countHStart; // Reduce k by the number of sequences counted
35        } else {
36            // If k is within the range, the current move is 'H'
37            path += 'H';
38            horizontalMoves--; // One less horizontal move is needed
39        }
40    }
41  
42    return path; // Return the constructed path
43}
44
45// Test the function with a sample input
46let destinationSample = [2, 3];
47let kSample = 3;
48console.log(kthSmallestPath(destinationSample, kSample)); // Outputs the k-th smallest path in string format
49
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity

The main operation of this algorithm is conducted within a loop that iterates (h + v) times, where h and v are the numbers of horizontal and vertical steps to reach the destination, respectively.

Within this loop, the time-critical step is the computation of combinations using comb(h + v - 1, h - 1) to decide whether to add "H" or "V" to the path. The comb function's complexity can vary depending on the implementation, but generally, it is computed using factorials which can be intensive. However, since Python's comb function uses an efficient algorithm presumably based on Pascal's triangle or multiplicative formula, we can assume it runs in O(r) or O(n-r) time complexity, where n is the first argument and r is the second argument to comb.

In the worst-case scenario, we are looking at:

  • A time complexity of O(h * min(h, v)) for computing the combination when v >= h, because comb(h + v - 1, h - 1) simplifies to comb(h + v - 1, v) when v < h. Since the loop runs h + v times and the most time-consuming operation is O(min(h, v)), the overall time complexity would be O((h + v) * min(h, v)).

Space Complexity

The space complexity is determined by the storage used for the ans list. Since the ans list will contain at most (h + v) characters, the space complexity is O(h + v).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ