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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Kth Smallest Instructions

Number: 489

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a destination specified by (row, column) and knowing that Bob starts at (0, 0) and can only move right (represented by 'H') and down (represented by 'V'), return the kth lexicographically smallest valid instruction string (1-indexed) that leads Bob to the destination. Lexicographic order follows that 'H' is considered smaller than 'V' (i.e. “HHHVV” comes before “HHVHV”).

Key Insights

  • The task is equivalent to selecting positions for 'H' moves among a total of (row + column) moves.
  • The number of valid instruction strings is given by the combination C(totalMoves, countH).
  • Use combinatorics to decide each character: if placing 'H' first yields a sufficient number of sequences to cover kth smallest, then the first character is 'H', otherwise it is 'V' and we update k accordingly.
  • Precompute binomial coefficients (or compute on the fly) for combinations to avoid repetitive calculations since moves are at most around 30.
  • The solution builds the instruction string one character at a time based on remaining counts of H's and V's.

Space and Time Complexity

Time Complexity: O((row + column)^2) due to the combination calculations for each position. Space Complexity: O(row + column) for the output string; additional space for combination table is O((row + column)^2), which is acceptable with given constraints.

Solution

We maintain two counters: one for the number of horizontal moves (H) and one for vertical moves (V). For each move in the resulting string, we decide if the current position should be an 'H' or a 'V' by checking the count of sequences that would start with 'H'. This count is computed by the binomial coefficient C(remainingMoves-1, remainingH-1) (if we choose 'H'). If k is less than or equal to this count, we pick 'H'; otherwise, we pick 'V' and subtract this count from k. We repeat this process until the instruction string is complete.

We use a helper function to compute the binomial coefficient (combinations) either recursively or with a precomputed table.

Code Solutions

def kthSmallestPath(destination, k):
    # Number of vertical and horizontal moves needed
    V = destination[0]
    H = destination[1]
    
    # Precompute combination values using a table (up to V+H+1 by V+H+1)
    n = V + H
    comb = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        comb[i][0] = 1
        comb[i][i] = 1
        for j in range(1, i):
            comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
    
    result = []
    while H + V:
        # If no more horizontal moves, the rest must be vertical
        if H == 0:
            result.append('V')
            V -= 1
        # If no more vertical moves, the rest must be horizontal
        elif V == 0:
            result.append('H')
            H -= 1
        else:
            # Count sequences if 'H' is chosen next:
            count = comb[H + V - 1][H - 1]
            if k <= count:
                result.append('H')
                H -= 1
            else:
                result.append('V')
                k -= count
                V -= 1
    return ''.join(result)

# Example usage:
print(kthSmallestPath([2,3], 1))  # Expected "HHHVV"
print(kthSmallestPath([2,3], 2))  # Expected "HHVHV"
print(kthSmallestPath([2,3], 3))  # Expected "HHVVH"
← Back to All Questions