Ranked Flight Withdrawal Ledger
Kth smallest subset sum of an integer array, counting duplicates
An airport is reviewing which flights to withdraw from a schedule. Withdrawing flight i changes the airport's ledger by changes[i]: a positive value is an expense, and a negative value is a saving.
A withdrawal plan is any subset of the flights, including the empty subset. Its ledger change is the sum of changes[i] over the withdrawn flights. Every subset is permitted; there are no dependencies between flights.
Order all withdrawal plans by their ledger change, from smallest to largest. Different subsets count as different plans, even when their ledger changes are equal. Thus, repeated values remain repeated in the ordered sequence.
Given changes and a one-based rank k, return the ledger change at position k. You do not need to return the plan itself.
Examples
Example 1
Input: changes = [4,-7,2], k = 4 Output: -1
Withdrawing the flight with a negative change creates a saving. Consider all eight subsets of the three flights, sort their ledger changes, and select the fourth entry.
Example 2
Input: changes = [2,2], k = 3 Output: 2
The two single-flight withdrawal plans are different plans with equal ledger changes. Both occupy positions in the ranking; they must not be merged into one entry.
Example 3
Input: changes = [], k = 1 Output: 0
With no flights, the empty withdrawal plan is the only plan.
Constraints
- 0 <= changes.length <= 5000
- -1000000 <= changes[i] <= 1000000
- 1 <= k <= 10000
- k <= 2^(changes.length)
- k is one-based, and equal ledger changes are counted with multiplicity.
The intended solution takes O(n log n + k log k) time and O(n + k) space. Heap entries must not be deduplicated: equal entries can represent different withdrawal plans. Ledger changes can exceed the signed 32-bit integer range, but remain exactly representable by JavaScript numbers.
Hints
Show hint 1Hint 1
The minimum-change plan withdraws every flight with a negative change and no flight with a positive change. Relative to that plan, toggling any flight increases the ledger change by the absolute value of its change.
Show hint 2Hint 2
Sort these nonnegative increases. For a nonempty subset whose largest index is i, generate two successors using index i + 1: add that index, or replace index i with it. Use a min-heap to visit subset sums in increasing order.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return a withdrawal plan at rank k if ties were ordered lexicographically by the increasing list of withdrawn flight indices?
- If several ranks are requested for the same schedule, how can you reuse the heap traversal rather than solve each request separately?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem