Katkat
Back

Find kth smallest and count stair-climbing ways

NioSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement an efficient selection algorithm for order statistics and a dynamic programming approach to solve a classic combinatorial staircase problem.

Part 1: Kth Smallest Element

Given an unsorted array of integers nums and an integer k, return the kth smallest element in the array. You must implement a solution with an average time complexity of O(n).

Example

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 2
Explanation: The sorted array is [1, 2, 3, 4, 5, 6]. The 2nd smallest is 2.

Part 2: Stair Climbing

You are climbing a staircase that has n steps. Each time you can either climb 1 or 2 steps. In addition, there are certain steps that are 'broken' and cannot be stepped on. You are given an array broken_steps containing the indices of these steps (1-indexed).

Write a function to return the number of distinct ways you can reach the top (step n). If the top step is broken, the number of ways is 0.

Example

Input: n = 4, broken_steps = [2]
Output: 1
Explanation: 
Possible paths to 4 steps:
1. 1 -> 3 -> 4 (Valid)
2. 1 -> 2 -> 4 (Invalid, 2 is broken)
3. 1 -> 3 -> 4 (Valid, but 1-2-4 is blocked)
Result is 1: (1 -> 3 -> 4 is the only valid sequence).

Constraints

  • `1 int: pass

def count_ways(n: int, broken_steps: list[int]) -> int: pass

Hints

Hint 1

For Part 1, consider using the QuickSelect algorithm which partitions the array around a pivot to narrow down the search space.

Hint 2

For Part 2, define `dp[i]` as the number of ways to reach step `i`, noting that `dp[i] = 0` if step `i` is broken.

Hint 3

The recurrence relation for Part 2 is `dp[i] = dp[i-1] + dp[i-2]` for valid steps, with base cases `dp[0] = 1` and `dp[1] = 1` (if not broken).

Follow-up questions

  • How does the worst-case time complexity of QuickSelect compare to using a Min-Heap, and when would you prefer one over the other?
  • How would you modify the stair-climbing problem if you were allowed to take 1, 2, or 3 steps at a time?
  • How can you optimize the space complexity of the stair-climbing solution to O(1)?