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 are given an array where each element represents the maximum jump length from that position. You need to determine if you can reach the last index starting from the first index. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Dynamic Programming with bottom-up tabulation to check reachability for each index

B. Breadth-first search using a queue to explore reachable indices level by level

C. Depth-first search exploring all possible jump paths recursively without memoization

D. Greedy algorithm tracking the maximum reachable index while iterating through the array

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if the last index is reachable from the first index using jumps defined by array values.

2. Step 2: Identify optimal approach

   Greedy approach efficiently tracks the furthest reachable index in one pass, guaranteeing O(n) time complexity, unlike exhaustive search or DP which are slower.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy approach is linear and optimal for this problem [OK]

Hint: Greedy tracks max reachable index in one pass [OK]

Common Mistakes:

• Confusing DP with greedy, thinking recursion is needed

2. Consider the following code snippet for the Jump Game problem. What is the value of maxReach after the third iteration (i = 2) when the input is [2, 3, 1, 1, 4]?

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        if i > maxReach:
            return False
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Trace maxReach updates for each iteration

   i=0: maxReach = max(0, 0+2) = 2 i=1: maxReach = max(2, 1+3) = 4 i=2: maxReach = max(4, 2+1) = 4

2. Step 2: Identify maxReach after i=2

   After third iteration (i=2), maxReach remains 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   maxReach does not decrease; it stays at 4 after i=2 [OK]

Hint: maxReach never decreases, track max(i+jump) [OK]

Common Mistakes:

• Off-by-one in iteration count
• Confusing maxReach update with i only

3. You are given an array where each element represents the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps. Which algorithmic approach guarantees finding the minimum number of jumps efficiently?

easy

A. A simple greedy approach that always jumps to the farthest reachable index from the current position.

B. A breadth-first search (BFS) treating each index as a node and exploring all reachable indices level by level.

C. A dynamic programming approach that computes the minimum jumps for each index by checking all previous indices.

D. A depth-first search (DFS) exploring all possible jump sequences recursively and returning the minimum.

Solution

1. Step 1: Understand problem as shortest path in graph

   Each index can be seen as a node with edges to reachable indices. BFS explores nodes level by level, guaranteeing the shortest path (minimum jumps).

2. Step 2: Compare approaches

   Greedy alone can fail on some inputs by making locally optimal but globally suboptimal jumps. DP is correct but less efficient. DFS is exponential time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS ensures minimum jumps by level order traversal [OK]

Hint: Minimum jumps = shortest path -> BFS [OK]

Common Mistakes:

• Believing greedy always yields minimum jumps
• Confusing DP with BFS for this problem
• Assuming DFS is efficient here

4. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

5. The following code attempts to implement the optimal wiggle subsequence algorithm. Identify the line containing the subtle bug that causes incorrect results on inputs with consecutive equal elements.

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff < 0) or (diff < 0 and last_diff > 0):
            count += 1
            last_diff = diff
    return count

medium

A. Line 6: Using strict inequalities (last_diff < 0 and last_diff > 0) instead of inclusive (<= 0 and >= 0)

B. Line 3: Initializing count to 1 instead of 0

C. Line 7: Updating last_diff inside the if condition

D. Line 2: Returning 0 if nums is empty

Solution

1. Step 1: Understand the condition for counting wiggles

   The condition must allow last_diff to be zero or equal to zero to handle initial or equal consecutive elements correctly.

2. Step 2: Identify the bug

   Using strict inequalities excludes cases where last_diff is zero, causing the algorithm to skip valid wiggles after equal elements, leading to incorrect counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive inequalities fix counting on equal consecutive elements [OK]

Hint: Use <= 0 and >= 0 to handle zero last_diff correctly

Common Mistakes:

• Using strict inequalities causing missed wiggles
• Incorrect initialization of counters
• Updating last_diff outside condition