Remove K Digits (Smallest Number)

🎯

Remove K Digits (Smallest Number)

mediumGREEDYAmazonGoogleFacebook

Imagine you have a large number displayed on a screen, but you want to make it as small as possible by removing exactly k digits. How do you do it efficiently?

💡 This problem is about greedily removing digits to minimize the resulting number. Beginners often struggle because the naive approach tries all removals, which is inefficient, and they miss the insight that a stack can help maintain a monotonic sequence to decide removals.

📋

Problem Statement

Given a non-negative integer num represented as a string and an integer k, remove k digits from the number so that the new number is the smallest possible. Return the new number as a string. If the new number is empty, return "0".

1 ≤ num.length ≤ 10^5num consists of only digits '0' through '9'0 ≤ k ≤ num.length

💡

Example

Input"num = \"1432219\", k = 3"

Output"1219"

Remove digits '4', '3', and '2' to get the smallest number '1219'.

Input"num = \"10200\", k = 1"

Output"200"

Remove the leading '1' to get '0200', which is '200' after removing leading zeros.

Input"num = \"10\", k = 2"

Output"0"

Removing both digits results in an empty string, so return '0'.

• k equals length of num → output '0'
• num consists of all identical digits → remove k digits from the end
• num has leading zeros after removal → remove leading zeros in output
• k is zero → output is original number

⚠️

Common Mistakes

Not removing leading zeros in the final result

Output may have leading zeros, which is incorrect

✅ Strip leading zeros before returning the result

Removing digits from the front instead of using a stack

Leads to incorrect smallest number

✅ Use a stack to remove larger digits before smaller ones

Not removing remaining digits if k > 0 after iteration

Resulting number is larger than possible

✅ Remove last k digits from stack after iteration

Using integer conversions for large inputs

Integer overflow or runtime errors

✅ Operate on strings and avoid integer conversions

🧠

Brute Force (Try All Combinations)

💡 This approach exists to understand the problem's search space and why naive solutions are impractical. It helps beginners grasp the problem's complexity before optimizing.

Intuition

Try removing every possible combination of k digits and pick the smallest resulting number. This brute force method explores all subsets of digits to remove.

Algorithm

1. Generate all combinations of indices of length k to remove.
2. For each combination, remove those digits from num.
3. Convert the remaining digits to a number, removing leading zeros.
4. Return the smallest number found.

💡 This algorithm is conceptually simple but hard to implement efficiently due to the huge number of combinations.

</>

Code

from itertools import combinations

def removeKdigits(num: str, k: int) -> str:
    if k == 0:
        return str(int(num))  # remove leading zeros
    if k == len(num):
        return "0"
    min_num = None
    indices = range(len(num))
    for remove_indices in combinations(indices, k):
        remove_set = set(remove_indices)
        candidate = ''.join(num[i] for i in range(len(num)) if i not in remove_set)
        candidate = candidate.lstrip('0') or '0'
        if min_num is None or int(candidate) < int(min_num):
            min_num = candidate
    return min_num

# Driver code
if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # Expected: 1219
    print(removeKdigits("10200", 1))   # Expected: 200
    print(removeKdigits("10", 2))      # Expected: 0

Line Notes

from itertools import combinationsImport combinations to generate all removal sets

if k == 0:If no digits to remove, just return number without leading zeros

if k == len(num):If removing all digits, result is zero

for remove_indices in combinations(indices, k):Try every combination of k indices to remove

candidate = ''.join(num[i] for i in range(len(num)) if i not in remove_set)Build candidate number after removals

candidate = candidate.lstrip('0') or '0'Remove leading zeros or set to '0' if empty

if min_num is None or int(candidate) < int(min_num):Update minimum number found

import java.util.*;

public class RemoveKDigitsBrute {
    public static String removeKdigits(String num, int k) {
        if (k == 0) return removeLeadingZeros(num);
        if (k == num.length()) return "0";
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < num.length(); i++) indices.add(i);
        String minNum = null;
        List<List<Integer>> combos = combinations(indices, k);
        for (List<Integer> removeIndices : combos) {
            Set<Integer> removeSet = new HashSet<>(removeIndices);
            StringBuilder candidate = new StringBuilder();
            for (int i = 0; i < num.length(); i++) {
                if (!removeSet.contains(i)) candidate.append(num.charAt(i));
            }
            String candStr = removeLeadingZeros(candidate.toString());
            if (minNum == null || compareNumbers(candStr, minNum) < 0) minNum = candStr;
        }
        return minNum;
    }

    private static String removeLeadingZeros(String s) {
        int i = 0;
        while (i < s.length() && s.charAt(i) == '0') i++;
        return i == s.length() ? "0" : s.substring(i);
    }

    private static int compareNumbers(String a, String b) {
        if (a.length() != b.length()) return a.length() - b.length();
        return a.compareTo(b);
    }

    private static List<List<Integer>> combinations(List<Integer> arr, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(arr, k, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(List<Integer> arr, int k, int start, List<Integer> temp, List<List<Integer>> result) {
        if (temp.size() == k) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < arr.size(); i++) {
            temp.add(arr.get(i));
            backtrack(arr, k, i + 1, temp, result);
            temp.remove(temp.size() - 1);
        }
    }

    // Driver
    public static void main(String[] args) {
        System.out.println(removeKdigits("1432219", 3)); // 1219
        System.out.println(removeKdigits("10200", 1));  // 200
        System.out.println(removeKdigits("10", 2));     // 0
    }
}

Line Notes

if (k == 0) return removeLeadingZeros(num);Return original number if no removals

if (k == num.length()) return "0";If removing all digits, return zero

for (List<Integer> removeIndices : combos)Try all combinations of indices to remove

StringBuilder candidate = new StringBuilder();Build candidate number after removals

String candStr = removeLeadingZeros(candidate.toString());Remove leading zeros from candidate

if (minNum == null || compareNumbers(candStr, minNum) < 0)Update minimum number found

private static void backtrack(...)Generate all combinations recursively

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void backtrack(const vector<int>& arr, int k, int start, vector<int>& temp, vector<vector<int>>& result) {
    if ((int)temp.size() == k) {
        result.push_back(temp);
        return;
    }
    for (int i = start; i < (int)arr.size(); i++) {
        temp.push_back(arr[i]);
        backtrack(arr, k, i + 1, temp, result);
        temp.pop_back();
    }
}

vector<vector<int>> combinations(const vector<int>& arr, int k) {
    vector<vector<int>> result;
    vector<int> temp;
    backtrack(arr, k, 0, temp, result);
    return result;
}

string removeLeadingZeros(const string& s) {
    int i = 0;
    while (i < (int)s.size() && s[i] == '0') i++;
    if (i == (int)s.size()) return "0";
    return s.substr(i);
}

int compareNumbers(const string& a, const string& b) {
    if ((int)a.size() != (int)b.size()) return (int)a.size() - (int)b.size();
    return a.compare(b);
}

string removeKdigits(string num, int k) {
    if (k == 0) return removeLeadingZeros(num);
    if (k == (int)num.size()) return "0";
    vector<int> indices(num.size());
    for (int i = 0; i < (int)num.size(); i++) indices[i] = i;
    vector<vector<int>> combos = combinations(indices, k);
    string minNum = "";
    for (auto& removeIndices : combos) {
        set<int> removeSet(removeIndices.begin(), removeIndices.end());
        string candidate = "";
        for (int i = 0; i < (int)num.size(); i++) {
            if (removeSet.find(i) == removeSet.end()) candidate += num[i];
        }
        candidate = removeLeadingZeros(candidate);
        if (minNum == "" || compareNumbers(candidate, minNum) < 0) minNum = candidate;
    }
    return minNum;
}

int main() {
    cout << removeKdigits("1432219", 3) << "\n"; // 1219
    cout << removeKdigits("10200", 1) << "\n";  // 200
    cout << removeKdigits("10", 2) << "\n";     // 0
    return 0;
}

Line Notes

if (k == 0) return removeLeadingZeros(num);Return original number if no removals

if (k == (int)num.size()) return "0";If removing all digits, return zero

vector<vector<int>> combos = combinations(indices, k);Generate all combinations of indices to remove

string candidate = "";Build candidate number after removals

candidate = removeLeadingZeros(candidate);Remove leading zeros from candidate

if (minNum == "" || compareNumbers(candidate, minNum) < 0)Update minimum number found

void backtrack(...)Recursive helper to generate combinations

function removeKdigits(num, k) {
    if (k === 0) return String(Number(num));
    if (k === num.length) return "0";
    const indices = [...Array(num.length).keys()];
    const combos = [];
    function backtrack(start, temp) {
        if (temp.length === k) {
            combos.push([...temp]);
            return;
        }
        for (let i = start; i < indices.length; i++) {
            temp.push(indices[i]);
            backtrack(i + 1, temp);
            temp.pop();
        }
    }
    backtrack(0, []);
    let minNum = null;
    for (const removeIndices of combos) {
        const removeSet = new Set(removeIndices);
        let candidate = '';
        for (let i = 0; i < num.length; i++) {
            if (!removeSet.has(i)) candidate += num[i];
        }
        candidate = candidate.replace(/^0+/, '') || '0';
        if (minNum === null || BigInt(candidate) < BigInt(minNum)) minNum = candidate;
    }
    return minNum;
}

// Driver
console.log(removeKdigits("1432219", 3)); // 1219
console.log(removeKdigits("10200", 1));  // 200
console.log(removeKdigits("10", 2));     // 0

Line Notes

if (k === 0) return String(Number(num));Return original number if no removals

if (k === num.length) return "0";If removing all digits, return zero

function backtrack(start, temp)Generate all combinations recursively

let candidate = '';Build candidate number after removals

candidate = candidate.replace(/^0+/, '') || '0';Remove leading zeros or set to '0'

if (minNum === null || BigInt(candidate) < BigInt(minNum))Update minimum number found

⏱

Complexity

TimeO(n choose k * n)

SpaceO(n choose k * n)

We generate all combinations of k indices from n digits (n choose k), and for each, build a candidate string of length up to n.

💡 For n=10 and k=3, this means thousands of combinations; for n=100, it's astronomically large and impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem's complexity and why optimization is needed.

🧠

Greedy with Stack (Monotonic Stack)

💡 This approach uses a stack to greedily remove digits that are larger than the next digit, ensuring the smallest number. Beginners often miss the stack insight and try complicated logic.

Intuition

We want to remove digits that make the number larger when a smaller digit follows. Using a stack, we pop larger digits before pushing the current digit, removing up to k digits.

Algorithm

1. Initialize an empty stack.
2. Iterate over each digit in num:
3. While k > 0 and stack top is greater than current digit, pop from stack and decrement k.
4. Push current digit onto stack.
5. If k > 0 after iteration, remove last k digits from stack.
6. Build the number from stack and remove leading zeros.
7. Return '0' if result is empty.

💡 The tricky part is understanding why popping larger digits before smaller ones leads to the smallest number.

</>

Code

def removeKdigits(num: str, k: int) -> str:
    stack = []
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # If k still remains, remove from the end
    while k > 0:
        stack.pop()
        k -= 1
    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

# Driver code
if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # Expected: 1219
    print(removeKdigits("10200", 1))   # Expected: 200
    print(removeKdigits("10", 2))      # Expected: 0

Line Notes

stack = []Initialize stack to store digits

while k > 0 and stack and stack[-1] > digit:Pop larger digits to make number smaller

stack.pop()Remove one digit from stack

k -= 1Decrement removal count

stack.append(digit)Add current digit to stack

while k > 0:If removals remain, remove from end

result = ''.join(stack).lstrip('0')Build final number and remove leading zeros

return result if result else '0'Return '0' if empty

import java.util.*;

public class RemoveKDigitsGreedy {
    public static String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char digit : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && stack.peekLast() > digit) {
                stack.pollLast();
                k--;
            }
            stack.offerLast(digit);
        }
        while (k > 0) {
            stack.pollLast();
            k--;
        }
        StringBuilder sb = new StringBuilder();
        boolean leadingZero = true;
        for (char c : stack) {
            if (leadingZero && c == '0') continue;
            leadingZero = false;
            sb.append(c);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }

    // Driver
    public static void main(String[] args) {
        System.out.println(removeKdigits("1432219", 3)); // 1219
        System.out.println(removeKdigits("10200", 1));  // 200
        System.out.println(removeKdigits("10", 2));     // 0
    }
}

Line Notes

Deque<Character> stack = new ArrayDeque<>();Stack to store digits

while (k > 0 && !stack.isEmpty() && stack.peekLast() > digit)Pop larger digits to minimize number

stack.pollLast();Remove digit from stack

k--;Decrement removal count

stack.offerLast(digit);Add current digit

while (k > 0)Remove remaining digits from end if needed

if (leadingZero && c == '0') continue;Skip leading zeros

return sb.length() == 0 ? "0" : sb.toString();Return '0' if empty

#include <iostream>
#include <string>
#include <deque>

using namespace std;

string removeKdigits(string num, int k) {
    deque<char> stack;
    for (char digit : num) {
        while (k > 0 && !stack.empty() && stack.back() > digit) {
            stack.pop_back();
            k--;
        }
        stack.push_back(digit);
    }
    while (k > 0 && !stack.empty()) {
        stack.pop_back();
        k--;
    }
    string result;
    bool leadingZero = true;
    for (char c : stack) {
        if (leadingZero && c == '0') continue;
        leadingZero = false;
        result.push_back(c);
    }
    return result.empty() ? "0" : result;
}

int main() {
    cout << removeKdigits("1432219", 3) << "\n"; // 1219
    cout << removeKdigits("10200", 1) << "\n";  // 200
    cout << removeKdigits("10", 2) << "\n";     // 0
    return 0;
}

Line Notes

deque<char> stack;Stack to hold digits

while (k > 0 && !stack.empty() && stack.back() > digit)Pop larger digits to minimize number

stack.pop_back();Remove digit from stack

k--;Decrement removal count

stack.push_back(digit);Add current digit

while (k > 0 && !stack.empty())Remove remaining digits from end

if (leadingZero && c == '0') continue;Skip leading zeros

return result.empty() ? "0" : result;Return '0' if empty

function removeKdigits(num, k) {
    const stack = [];
    for (const digit of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    while (k > 0) {
        stack.pop();
        k--;
    }
    let result = stack.join('').replace(/^0+/, '');
    return result === '' ? '0' : result;
}

// Driver
console.log(removeKdigits("1432219", 3)); // 1219
console.log(removeKdigits("10200", 1));  // 200
console.log(removeKdigits("10", 2));     // 0

Line Notes

const stack = [];Stack to hold digits

while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit)Pop larger digits to minimize number

stack.pop();Remove digit from stack

k--;Decrement removal count

stack.push(digit);Add current digit

while (k > 0)Remove remaining digits from end

stack.join('').replace(/^0+/, '')Build result and remove leading zeros

return result === '' ? '0' : result;Return '0' if empty

⏱

Complexity

TimeO(n)

SpaceO(n)

Each digit is pushed and popped at most once from the stack, so linear time and space.

💡 For n=100000, this means about 200000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the optimal and accepted approach for this problem in interviews.

🧠

Greedy with StringBuilder and Two Pointers

💡 This approach is a variation of the stack method but uses a string builder and two pointers to simulate the stack behavior, which some languages or candidates prefer.

Intuition

We build the smallest number by iterating through digits and removing previous digits that are larger than the current digit, using pointers to track the current build.

Algorithm

1. Initialize an empty string builder and a pointer for the current length.
2. Iterate over each digit in num:
3. While k > 0 and the last digit in builder is greater than current digit, remove last digit and decrement k.
4. Append current digit to builder.
5. If k > 0 after iteration, remove last k digits from builder.
6. Remove leading zeros from builder.
7. Return '0' if builder is empty.

💡 This approach is similar to the stack but uses string manipulation, which can be more intuitive in some languages.

</>

Code

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    while k > 0:
        builder.pop()
        k -= 1
    result = ''.join(builder).lstrip('0')
    return result if result else '0'

# Driver
if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # 1219
    print(removeKdigits("10200", 1))   # 200
    print(removeKdigits("10", 2))      # 0

Line Notes

builder = []Use list as string builder

while k > 0 and builder and builder[-1] > digit:Remove larger previous digits

builder.pop()Remove last digit

k -= 1Decrement removal count

builder.append(digit)Add current digit

while k > 0:Remove remaining digits from end

result = ''.join(builder).lstrip('0')Build final number and remove leading zeros

return result if result else '0'Return '0' if empty

public class RemoveKDigitsTwoPointers {
    public static String removeKdigits(String num, int k) {
        StringBuilder builder = new StringBuilder();
        for (char digit : num.toCharArray()) {
            while (k > 0 && builder.length() > 0 && builder.charAt(builder.length() - 1) > digit) {
                builder.deleteCharAt(builder.length() - 1);
                k--;
            }
            builder.append(digit);
        }
        while (k > 0 && builder.length() > 0) {
            builder.deleteCharAt(builder.length() - 1);
            k--;
        }
        // Remove leading zeros
        int i = 0;
        while (i < builder.length() && builder.charAt(i) == '0') i++;
        String result = builder.substring(i);
        return result.isEmpty() ? "0" : result;
    }

    // Driver
    public static void main(String[] args) {
        System.out.println(removeKdigits("1432219", 3)); // 1219
        System.out.println(removeKdigits("10200", 1));  // 200
        System.out.println(removeKdigits("10", 2));     // 0
    }
}

Line Notes

StringBuilder builder = new StringBuilder();Use StringBuilder to build result

while (k > 0 && builder.length() > 0 && builder.charAt(builder.length() - 1) > digit)Remove larger previous digits

builder.deleteCharAt(builder.length() - 1);Remove last digit

k--;Decrement removal count

builder.append(digit);Add current digit

while (k > 0 && builder.length() > 0)Remove remaining digits from end

while (i < builder.length() && builder.charAt(i) == '0') i++;Skip leading zeros

return result.isEmpty() ? "0" : result;Return '0' if empty

#include <iostream>
#include <string>

using namespace std;

string removeKdigits(string num, int k) {
    string builder;
    for (char digit : num) {
        while (k > 0 && !builder.empty() && builder.back() > digit) {
            builder.pop_back();
            k--;
        }
        builder.push_back(digit);
    }
    while (k > 0 && !builder.empty()) {
        builder.pop_back();
        k--;
    }
    int i = 0;
    while (i < (int)builder.size() && builder[i] == '0') i++;
    string result = builder.substr(i);
    return result.empty() ? "0" : result;
}

int main() {
    cout << removeKdigits("1432219", 3) << "\n"; // 1219
    cout << removeKdigits("10200", 1) << "\n";  // 200
    cout << removeKdigits("10", 2) << "\n";     // 0
    return 0;
}

Line Notes

string builder;Use string as builder

while (k > 0 && !builder.empty() && builder.back() > digit)Remove larger previous digits

builder.pop_back();Remove last digit

k--;Decrement removal count

builder.push_back(digit);Add current digit

while (k > 0 && !builder.empty())Remove remaining digits from end

while (i < (int)builder.size() && builder[i] == '0') i++;Skip leading zeros

return result.empty() ? "0" : result;Return '0' if empty

function removeKdigits(num, k) {
    let builder = '';
    for (const digit of num) {
        while (k > 0 && builder.length > 0 && builder[builder.length - 1] > digit) {
            builder = builder.slice(0, -1);
            k--;
        }
        builder += digit;
    }
    while (k > 0) {
        builder = builder.slice(0, -1);
        k--;
    }
    builder = builder.replace(/^0+/, '');
    return builder === '' ? '0' : builder;
}

// Driver
console.log(removeKdigits("1432219", 3)); // 1219
console.log(removeKdigits("10200", 1));  // 200
console.log(removeKdigits("10", 2));     // 0

Line Notes

let builder = '';Use string as builder

while (k > 0 && builder.length > 0 && builder[builder.length - 1] > digit)Remove larger previous digits

builder = builder.slice(0, -1);Remove last digit

k--;Decrement removal count

builder += digit;Add current digit

while (k > 0)Remove remaining digits from end

builder = builder.replace(/^0+/, '');Remove leading zeros

return builder === '' ? '0' : builder;Return '0' if empty

⏱

Complexity

TimeO(n)

SpaceO(n)

Each digit is appended and possibly removed once, so linear time and space.

💡 This approach is as efficient as the stack method but uses string manipulation.

Interview Verdict: Accepted

This approach is optimal and accepted, offering an alternative implementation style.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the greedy stack approach for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n choose k * n)	O(n choose k * n)	Yes (deep recursion in combinations)	Yes	Mention only - never code
2. Greedy with Stack	O(n)	O(n)	No	Yes	Code this approach
3. Greedy with StringBuilder	O(n)	O(n)	No	Yes	Alternative to stack, also acceptable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain why brute force is inefficient.Step 4: Introduce the greedy stack approach and explain intuition.Step 5: Write clean code and test with examples.Step 6: Discuss edge cases and possible follow-ups.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to greedy, and coding correctness with edge cases.

Common Follow-ups

• What if k is zero? → Return original number without leading zeros.
• How to handle leading zeros in the result? → Remove them before returning.
• Can you do this in O(n) time? → Yes, using the greedy stack approach.
• What if the input is very large? → The greedy approach still works efficiently.

💡 These follow-ups test your edge case handling and understanding of the optimal solution.

🔍

Pattern Recognition

When to Use

1) Asked to remove k elements to minimize/maximize a number or sequence; 2) Order matters; 3) Greedy removal of larger elements before smaller ones helps; 4) Monotonic stack or similar data structure fits.

Signature Phrases

remove k digitssmallest possible numbergreedy algorithmmonotonic stack

NOT This Pattern When

Sorting problems or DP problems that require subsequence counting are different.

Similar Problems

Create Maximum Number - similar removal to maximize numberLargest Number - ordering digits greedilyRemove Duplicate Letters - monotonic stack to maintain order

Practice

1. You have a list of children each with a greed factor and a list of cookies each with a size. You want to assign cookies to children so that each child gets at most one cookie and the cookie size is at least the child's greed factor. Which algorithmic approach guarantees the maximum number of content children?

easy

A. Greedy algorithm by sorting greed factors and cookie sizes, then assigning smallest sufficient cookie to each child

B. Dynamic Programming to try all possible assignments and pick the best

C. Brute force nested loops checking every cookie for every child without sorting

D. Divide and Conquer by splitting children and cookies and merging results

Solution

1. Step 1: Understand problem constraints

   Each child can get at most one cookie, and the cookie must satisfy the child's greed factor.

2. Step 2: Identify optimal approach

   Sorting both greed and cookie arrays allows a greedy assignment from smallest greed to smallest sufficient cookie, ensuring maximum matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy sorting approach is classic for assignment problems [OK]

Hint: Sort both arrays and assign greedily [OK]

Common Mistakes:

• Thinking brute force is needed for optimality
• Assuming DP is required
• Ignoring sorting leads to suboptimal matches

2. The following code attempts to compute the minimum number of platforms needed. Identify the line containing the subtle bug that can cause incorrect platform count when a train arrives exactly at the departure time of another train.

medium

A. Line with 'while heap and heap[0] < arrival:'

B. Line with 'trains = sorted(zip(arrivals, departures), key=lambda x: x[0])'

C. Line with 'heapq.heappush(heap, departure)'

D. Line with 'max_platforms = max(max_platforms, len(heap))'

Solution

1. Step 1: Understand the bug

   The condition 'heap[0] < arrival' pops platforms only if departure is strictly less than arrival, missing the case when departure == arrival.

2. Step 2: Correct condition

   Changing condition to 'heap[0] <= arrival' correctly frees platforms when a train arrives exactly at departure time, avoiding overcounting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Condition must include equality to avoid platform overcount [OK]

Hint: Use <= to free platform when arrival equals departure [OK]

Common Mistakes:

• Using < instead of <= in heap pop condition
• Not sorting trains by arrival time
• Forgetting to update max_platforms

3. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., unlimited transactions including multiple buys and sells per day). Which of the following algorithmic changes correctly adapts the solution?

hard

A. Add all positive differences between consecutive prices and also consider zero differences as profitable

B. Sum all positive differences between consecutive days as before, no change needed

C. Use a dynamic programming approach to consider multiple transactions per day explicitly

D. Modify the code to add all positive differences between consecutive prices including zero differences

Solution

1. Step 1: Understand the new constraint

   Allowing multiple transactions per day does not change the fact that profit comes from positive price differences.

2. Step 2: Check if algorithm needs change

   Summing all positive consecutive differences already accounts for all profitable transactions, including multiple per day.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Algorithm already sums all positive increments, no modification needed [OK]

Hint: Unlimited transactions per day still sum positive differences [OK]

Common Mistakes:

• Adding zero or negative differences incorrectly
• Overcomplicating with DP when greedy suffices
• Thinking multiple transactions per day require new logic

4. Suppose the problem is modified so that dominoes can be rotated multiple times (reused) to achieve uniformity, or the arrays can contain values outside 1-6. Which approach correctly adapts the solution?

hard

A. Check all unique values appearing in either array as candidates with early exit

B. Continue checking only the first domino's two values as candidates, ignoring others

C. Use dynamic programming to track rotations for all possible values 1 to 6 only

D. Sort arrays and greedily pick the most frequent value to minimize rotations

Solution

1. Step 1: Identify candidate values

   With values outside 1-6 and reuse allowed, candidates are all unique values in A and B, not just first domino.

2. Step 2: Check feasibility for each candidate

   For each candidate, verify if all dominoes can be rotated to match it, counting minimal rotations.

3. Step 3: Early exit optimization

   Stop checking candidates as soon as a valid minimal rotation count is found.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Checking all unique values covers extended domain and reuse [OK]

Hint: Check all unique values when domain expands [OK]

Common Mistakes:

• Checking only first domino candidates
• Limiting candidates to 1-6 values only

5. Suppose trains can arrive and depart multiple times (reusing platforms), or the station allows fractional arrival/departure times. Which modification to the min-heap approach correctly handles these cases?

hard

A. Use brute force nested loops to check all overlaps since fractional times break heap ordering

B. Sort arrivals and departures separately and use two pointers to count overlaps

C. Keep the min-heap but change the comparison to strictly less than (<) to handle fractional times

D. Use a balanced BST instead of a min-heap to handle fractional times and reuse efficiently

Solution

1. Step 1: Identify challenges with fractional and multiple reuse

   Fractional times and multiple reuse require precise ordering and efficient insertion/removal of intervals.

2. Step 2: Choose data structure

   A balanced BST supports ordered insertions, deletions, and queries with fractional keys better than a min-heap, which assumes discrete ordering.

3. Step 3: Why other options fail

   Two pointers fail with fractional times due to equality checks; changing comparison in heap breaks correctness; brute force is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Balanced BST handles fractional and reuse efficiently [OK]

Hint: Balanced BST supports fractional keys and dynamic reuse [OK]

Common Mistakes:

• Assuming min-heap works unchanged with fractional times
• Using two pointers without handling fractional equality
• Resorting to brute force for efficiency