What is the time complexity of Remove K Digits?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Remove K Digits?

This problem uses String, Stack, Greedy, Monotonic Stack. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Remove K Digits?

Insight 1: The greedy approach of iteratively removing larger digits from left to right is optimal for minimizing the resulting number. Insight 2: A stack data structure is suitable for maintaining a monotonically increasing (or non-decreasing) sequence of digits.

Which companies ask LeetCode 402. Remove K Digits in interviews?

This problem is frequently asked at Cisco, Coupang, DE Shaw, PhonePe, Samsung and 5 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Remove K Digits - LeetCode 402 Solution

Remove K Digits - Complete Solution Guide

Remove K Digits is LeetCode problem 402, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given string num representing a non-negative integer num , and an integer k , return the smallest possible integer after removing k digits from num . Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3: Input: num = "10",

Detailed Explanation

The problem requires you to remove *k* digits from a given non-negative integer represented as a string *num*, such that the resulting number is the smallest possible. The output should also be a string and must not contain leading zeros, except for the number zero itself.

Solution Approach

The solution uses a greedy approach and a stack data structure. It iterates through the digits of the input number *num*. For each digit, it compares it with the top of the stack. If the current digit is smaller than the top of the stack, and we still have removals (*k* > 0) allowed, we pop the stack. This process continues until either the stack is empty, *k* becomes 0, or the top of the stack is no longer greater than the current digit. Then, the current digit is pushed onto the stack. After processing all digits, if *k* is still greater than 0, it means the remaining digits in the stack are in non-decreasing order, so we remove the last *k* digits. Finally, we convert the stack to a string, remove any leading zeros, and return the result. If the result is empty, we return "0".

Step-by-Step Algorithm

Step 1: Initialize an empty stack to store digits.
Step 2: Iterate through each digit in the input string *num*.
Step 3: While the stack is not empty, *k* > 0, and the top of the stack is greater than the current digit, pop the top element from the stack and decrement *k*.
Step 4: Push the current digit onto the stack.
Step 5: After iterating through all digits, if *k* is still greater than 0, remove the last *k* digits from the stack.
Step 6: Convert the stack to a string.
Step 7: Remove any leading zeros from the resulting string.
Step 8: If the resulting string is empty, return "0"; otherwise, return the string.

Key Insights

Insight 1: The greedy approach of iteratively removing larger digits from left to right is optimal for minimizing the resulting number.
Insight 2: A stack data structure is suitable for maintaining a monotonically increasing (or non-decreasing) sequence of digits.
Insight 3: Handling edge cases such as leading zeros and situations where *k* is greater than or equal to the length of *num* is critical.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: String, Stack, Greedy, Monotonic Stack.

Companies

Asked at: Cisco, Coupang, DE Shaw, PhonePe, Samsung, Snap, Snowflake, Zoho, Zopsmart, josh technology.

Remove K Digits | LeetCode 402

Medium

String Stack Greedy Monotonic Stack

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.Stack;

class Solution {
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();

        for (char digit : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }

        // If k > 0, it means the remaining digits are in a non-decreasing order.
        // To get the smallest number, we must remove the largest digits from the end.
        // e.g., num = "12345", k = 2 -> stack will be ['1','2','3','4','5'], k=2
        // we need to remove '4' and '5'.
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        if (stack.isEmpty()) {
            return "0";
        }

        // Join the stack to form the result string and remove leading zeros.
        StringBuilder result = new StringBuilder();
        for (char digit : stack) {
            result.append(digit);
        }

        while (result.length() > 1 && result.charAt(0) == '0') {
            result.deleteCharAt(0);
        }

        if (result.length() == 0) {
            return "0";
        }

        return result.toString();
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 402: Remove K Digits - Detailed explanation and solution approaches.

Topics

String Stack Greedy Monotonic Stack

Companies

CiscoCoupangDE ShawPhonePeSamsungSnapSnowflakeZoho

Stats

Difficulty:Medium

Languages:4

Companies:10

Problem #:402

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize an empty stack to store digits.
2
Step 2: Iterate through each digit in the input string *num*.
3
Step 3: While the stack is not empty, *k* > 0, and the top of the stack is greater than the current digit, pop the top element from the stack and decrement *k*.
4
Step 4: Push the current digit onto the stack.
5
Step 5: After iterating through all digits, if *k* is still greater than 0, remove the last *k* digits from the stack.
6
Step 6: Convert the stack to a string.
7
Step 7: Remove any leading zeros from the resulting string.
8
Step 8: If the resulting string is empty, return "0"; otherwise, return the string.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n) because the algorithm iterates through the input string once and performs constant-time operations within the loop. The stack operations (push and pop) take O(1) on average. The space complexity is O(n) because the stack can grow up to the size of the input string in the worst case.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible subsequences of length num.length() - k and find the minimum among them. This involves generating combinations, which is inefficient.

Time: O(C(n, k) * (n-k)), where C(n,k) is the binomial coefficient (n choose k) and n is num.length().Space: O(n-k), where n is num.length().

Trade-offs: This is highly inefficient and not practical for larger inputs. The main solution using Stack is much more efficient.

✨

Key Insights

1Insight 1: The greedy approach of iteratively removing larger digits from left to right is optimal for minimizing the resulting number.
2Insight 2: A stack data structure is suitable for maintaining a monotonically increasing (or non-decreasing) sequence of digits.
3Insight 3: Handling edge cases such as leading zeros and situations where *k* is greater than or equal to the length of *num* is critical.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Greedy Algorithm

Making the best choice at each step without looking ahead.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input string *num* consists of all identical digits and *k* is less than the length of num (e.g., num = "1111", k = 2). The algorithm correctly removes the last *k* digits from the stack.
Edge case 2: Input string *num* has leading zeros after removing digits (e.g., num = "10200", k = 1). The algorithm correctly removes the leading zero.
Edge case 3: *k* is equal to the length of *num* (e.g., num = "123", k = 3). The algorithm returns "0".
Edge case 4: Input number is already the smallest number (e.g., num = "12345", k = 0). The algorithm returns the same number
Edge case 5: Input number is a descending number (e.g. num = "54321", k = 2). The algorithm correctly removes the largest digits from the beginning.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling leading zeros in the resulting string.

✗Common mistake 2: Not considering the case where *k* is greater than or equal to the length of *num*, leading to an empty string result.

✗Common mistake 3: Using the wrong data structure (e.g., a queue instead of a stack) which could alter the optimal ordering.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Optimizing number representation in embedded systems where memory is constrained. Removing insignificant digits can save space.

🏦Real-world scenario 2: Data compression where minimizing the size of numerical data without losing crucial information is important. Could be useful for time series data compression if coupled with proper algorithms.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 13, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Remove K Digits"?

For this medium-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?