We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Smallest Instructions

Difficulty: Hard

Problem Description

Bob is standing at cell (0, 0), and he wants to reach the destination: (row, column). He can only travel right and down. You are going to help Bob by providing instructions for him to reach the destination. The instructions are represented as a string, where each character is either 'H' (move right) or 'V' (move down). Bob wants the k-th lexicographically smallest instructions that will take him to the destination.

Key Insights

  • Bob can make a total of row + column moves to reach the destination.
  • The moves consist of row downward moves ('V') and column rightward moves ('H').
  • The total number of unique instructions can be calculated using combinations: nCr(row + column, row).
  • The problem requires generating the k-th smallest sequence of instructions in lexicographic order.

Space and Time Complexity

Time Complexity: O(row + column)
Space Complexity: O(1)

Solution

To find the k-th lexicographically smallest instruction sequence, we can use a combinatorial approach. The key steps are:

  1. Calculate the total combinations of instruction sequences that can be formed with the remaining moves.
  2. At each step, decide whether to place an 'H' or a 'V' in the sequence based on the value of k.
  3. If placing 'H' allows for enough combinations to still reach k, we place 'H' and decrement the horizontal moves.
  4. If not, we place 'V' and adjust k accordingly, as we skip over the combinations that start with 'H'.

This approach efficiently narrows down to the k-th sequence without generating all possible combinations.

Code Solutions

def kthSmallestInstructions(destination, k):
    row, column = destination
    res = []
    
    # Function to calculate nCr
    def nCr(n, r):
        if r > n:
            return 0
        if r == 0 or r == n:
            return 1
        r = min(r, n - r)  # Take advantage of symmetry
        numer = denom = 1
        for i in range(r):
            numer *= (n - i)
            denom *= (i + 1)
        return numer // denom

    while row > 0 and column > 0:
        # Calculate the number of combinations if we start with 'H'
        count = nCr(row + column - 1, row - 1)
        if k <= count:
            res.append('H')  # Place 'H'
            column -= 1
        else:
            res.append('V')  # Place 'V'
            k -= count  # Skip the count combinations starting with 'H'
            row -= 1
    
    # If any 'H's left
    res.extend(['H'] * column)
    # If any 'V's left
    res.extend(['V'] * row)

    return ''.join(res)
← Back to All Questions