L14. Remove K Digits | Stack and Queue Playlist

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ • 60

  • @brokegod5871
    @brokegod5871 5 місяців тому +40

    While pushing the st.top() to the res, use res.push_back(st.top()) instead of res = res + st.top() for leetcode, otherwise you'll get a memory limit exceeded error. If I have to guess, it's because string append (+) has a O(string size) where a new string is created and then appended whereas push_back is only O(1)

    • @KartikeyTT
      @KartikeyTT 5 місяців тому +1

      my code worked fine even after using res + st.top()
      //here is the code
      class Solution {
      public:
      string removeKdigits(string nums, int k) {
      stack st;
      for(int i=0; i

    • @pranavmisra5870
      @pranavmisra5870 4 місяці тому +1

      @@KartikeyTT it would work but using push-back gives better space complexity.

    • @KartikeyTT
      @KartikeyTT 4 місяці тому

      @@pranavmisra5870 bro space complexity does not depend on that

    • @glyoxal1933
      @glyoxal1933 3 місяці тому +1

      thanks

    • @sukhii0220
      @sukhii0220 3 місяці тому +1

      thanks brother

  • @manishnaidu30
    @manishnaidu30 4 місяці тому +8

    Hey striver, learning so much from this series, thank you first of all, and another issue I wanted to tell is that there are no articles and linked youtube videos in the website, Hope they are done soon as you are doing this series so that it is helpful for people who haven't checked this playlist on youtube yet.

  • @206-tusharkantimukherjee3
    @206-tusharkantimukherjee3 Місяць тому +5

    This question is king of edge cases

  • @Roshan__3006
    @Roshan__3006 5 місяців тому +5

    Great sir, I just started downloading and you just uploading these videos which Faster than BSNL

  • @ShahNawaz-cx3pi
    @ShahNawaz-cx3pi 4 місяці тому +10

    In some problems , brute force solution is more difficult that optimal solution in terms of implementation.
    BTW------
    Brute force solution: To remove k digits from the number, we can explore all possible combinations and choose the smallest number. This involves generating all subsequences of length n - k and selecting the smallest one
    For Generating all the subsequences you can watch the striver's recursion playlist (There he has taught pick & non-pick method , after learning that method, recursion on arrays will become cakewalk).

  • @trashcan-md7cw
    @trashcan-md7cw 3 місяці тому +4

    Instead of using a stack of characters, It is better to use a String as a stack like we used a list as a stack in asteroid collision...
    So we need not reverse the stack just remove the leading zeros and return it :) Happy Coding:)
    CODE
    string removeKdigits(string num, int k) {
    string st = ""; // Use a string as the stack
    int n = num.length();
    // Traverse each digit in the string
    for (int i = 0; i < n; ++i) {
    // Pop digits from the stack if they are greater than the current digit
    // and we still have digits to remove (k > 0)
    while (!st.empty() && st.back() > num[i] && k > 0) {
    st.pop_back();
    k--;
    }
    // Push the current digit to the stack
    st.push_back(num[i]);
    }
    // If k digits were not removed, remove from the end of the stack
    while (k > 0) {
    st.pop_back();
    k--;
    }
    // Remove leading zeros
    int start = 0;
    while (start < st.size() && st[start] == '0') {
    start++;
    }
    // Get the resulting number without leading zeros
    string result = st.substr(start);
    // If the result is empty, return "0"
    return result.empty() ? "0" : result;
    }

  • @NetajiSaiSuru
    @NetajiSaiSuru 4 місяці тому +3

    Exploring those Edge Cases and handling them is not everyone's cup of tea ❤‍🔥@Striver Kudoos!!

  • @darkwarrior6767
    @darkwarrior6767 3 місяці тому

    Instead of using stack to store answer you can directly use string and do operations on it using push_back and pop_back and back

  • @radhepatel6876
    @radhepatel6876 3 місяці тому +4

    Java Code: BTW This question is hard not medium
    class Solution {
    public String removeKdigits(String num, int k) {
    Stack st = new Stack();
    String result = "";
    for(int i=0;i0 && (num.charAt(i)-'0')0){
    st.pop();
    k-=1;
    }
    if(st.isEmpty()){
    return "0";
    }
    while(!st.isEmpty()){
    result+=st.pop();
    }
    String res = "";
    int index;
    for(index=result.length()-1;index>0;index--){
    if(result.charAt(index)!='0'){
    break;
    }
    }
    for(int i=index;i>=0;i--){
    res+=result.charAt(i);
    }
    return res;
    }
    }

  • @apmotivationakashparmar722
    @apmotivationakashparmar722 3 місяці тому

    Understood everything striver 😀😀

  • @shamanthhegde2820
    @shamanthhegde2820 3 місяці тому +1

    Hey Striver, I was able to solve this on my own thank you for that. to make it more simpler i removed the leading zero while inserting the numbers...
    the logic is in case the stack is empty and i am going to insert a zero that doesn't make sense because that number is going to turn out to be leading zero that's all
    public String removeKdigits(String num, int k) {
    Stack st = new Stack();
    int charPopped = 0;
    String ans = "";
    for(char ch:num.toCharArray()) {
    while(!st.isEmpty() && st.peek() > ch && charPopped < k) {
    st.pop();
    charPopped++;
    }
    if(st.isEmpty() && ch == '0') continue;
    st.push(ch);
    }
    while(!st.isEmpty() && charPopped < k) {
    st.pop();
    charPopped++;
    }
    if(st.isEmpty()) return "0";
    int n = st.size();
    for(int i=0; i

  • @TOI-700
    @TOI-700 2 місяці тому

    JAI HIND veere | darna nhi h | ek call kar kabhi bhi available 24/7 for you veere

  • @PawanKumar-hq6dy
    @PawanKumar-hq6dy Місяць тому

    last reversal we can avoid if we use deque where we can add and remove from first and last

  • @saumay-z1
    @saumay-z1 5 місяців тому +9

    So many edge cases.........Uffffff

  • @killerboy2387
    @killerboy2387 5 місяців тому +3

    Hey,striver we wants Heap playlist.please....

  • @oyeshxrme
    @oyeshxrme 2 місяці тому

    thanks bhaiya

  • @amitpandey8382
    @amitpandey8382 4 місяці тому +2

    I think time complexity will be O(4N)+O(K) .Inner while loop is also contributing o(N) time

  • @yoddha621
    @yoddha621 2 місяці тому

    Mast maza agaya

  • @tamoghnasaha2667
    @tamoghnasaha2667 3 місяці тому +2

    The smallest number should be 1122 instead of 1219?

    • @ayushaggarwal906
      @ayushaggarwal906 2 місяці тому +3

      you cannot change the order

    • @manas4656
      @manas4656 2 місяці тому +1

      here order should be maintained, we cannot change the position

  • @DeadPoolx1712
    @DeadPoolx1712 2 місяці тому

    UNDERSTOOD;

  • @KartikeyTT
    @KartikeyTT 5 місяців тому

    tysm sir

  • @shreyxnsh.14
    @shreyxnsh.14 3 місяці тому +1

    Thanks, was able to do this by myself, here is the C++ code:
    class Solution {
    public:
    string removeKdigits(string num, int k) {
    stack st;
    for(const char& c: num){
    while(!st.empty() && c0){
    st.pop();
    k--;
    }
    st.push(c);
    }
    while(k>0){
    st.pop();
    k--;
    }

    string res = "";
    while(!st.empty()){
    res.push_back(st.top());
    st.pop();
    }
    reverse(res.begin(), res.end());

    int i = 0;
    while(res[i] == '0'){
    i++;
    }
    res = res.substr(i);
    if(res == "")
    return "0";
    return res;
    }
    };

  • @subee128
    @subee128 4 місяці тому

    Thanks

  • @SibiRanganathL
    @SibiRanganathL 4 місяці тому

    Understood

  • @Shivi32590
    @Shivi32590 4 місяці тому

    understood

  • @Messi23485
    @Messi23485 4 місяці тому

    Can anyone please explain why he minus 0 in while condition during comparison of stack top with current character of string

  • @charuprabha8714
    @charuprabha8714 4 місяці тому

    Hi but how to think that we have to use stack to solve this problem🙂

    • @shreyxnsh.14
      @shreyxnsh.14 3 місяці тому

      you dont need to, you can do this by creating a new string and operating on it

  • @BeAcoder1011
    @BeAcoder1011 5 місяців тому +2

  • @navinvenkat3404
    @navinvenkat3404 2 місяці тому +1

    C++ sol =>
    class Solution {
    public:
    string removeKdigits(string num, int k) {
    stack st;
    int n = num.size();
    for(int i=0;i0 && (st.top() - '0') > (num[i] - '0')){
    st.pop();
    k--;
    }
    st.push(num[i]);
    }
    while(k>0 && !st.empty()){
    st.pop();
    k--;
    }
    string result = "";
    while(!st.empty()){
    result += st.top();
    st.pop();
    }
    reverse(result.begin() , result.end());
    int start = 0;
    while(start < result.size() && result[start] == '0'){
    start++;
    }
    result = result.substr(start);
    return result.empty() ? "0" : result;
    }
    };

  • @shreyxnsh.14
    @shreyxnsh.14 3 місяці тому

    Solution without stack:
    class Solution {
    public:
    string removeKdigits(string num, int k) {
    string newstr = "";
    for(const char& c: num){
    while(!newstr.empty() && c0){
    newstr.pop_back();
    k--;
    }
    newstr.push_back(c);
    }
    while(k>0){
    newstr.pop_back();
    k--;
    }

    int i = 0;
    while(newstr[i] == '0'){
    i++;
    }
    newstr = newstr.substr(i);
    if(newstr == "")
    return "0";
    return newstr;
    }
    };

  • @KalingaAbhisek
    @KalingaAbhisek 3 місяці тому

    Java Code
    class Solution {
    public String removeKdigits(String num, int k) {
    Stack st = new Stack();
    for(int i=0;inum.charAt(i)-'0' && k>0){
    st.pop();
    k--;
    }
    st.push(num.charAt(i)-'0');
    }
    while(k>0 && !st.isEmpty()) {
    st.pop();
    k--;
    }
    String res="";
    while(!st.isEmpty()){
    res+=st.pop();
    }
    StringBuilder sb = new StringBuilder(res).reverse();
    while(sb.length()>0 && sb.charAt(0)=='0'){
    sb.deleteCharAt(0);
    }
    return sb.length()>0?sb.toString():"0";
    }
    }

  • @arunraj4383
    @arunraj4383 2 місяці тому

  • @irfanmohammad2132
    @irfanmohammad2132 4 місяці тому

    Memory Limit Exceeded

  • @MJBZG
    @MJBZG 4 місяці тому +1

    your new lectures are becoming difficult to understand

    • @satyen4659
      @satyen4659 4 місяці тому +2

      but topics are also complex

    • @shreyxnsh.14
      @shreyxnsh.14 3 місяці тому +1

      this should have been easy if you've been following his playlist

    • @sanatgupta1562
      @sanatgupta1562 3 місяці тому

      Nobody asked for your opinion ​@@shreyxnsh.14

    • @sanatgupta1562
      @sanatgupta1562 3 місяці тому

      Nobody asked for ur opinion ​@@shreyxnsh.14

  • @valendradangi1822
    @valendradangi1822 4 місяці тому

    #include
    using namespace std;
    class Solution
    {
    public:
    string removeKdigits(string num, int k)
    {
    // char imp
    stack st;
    int n = num.size();
    int removed = 0;
    for (int i = 0; i < n; i++)
    {
    while (!st.empty() && removed < k && st.top() > num[i]) // Don't do >= Dry Run 1,2,2,2,2,5
    // k > 0 && st.top() - '0' > num[i] > '0'
    {
    removed++;
    st.pop();
    }
    st.push(num[i]);
    }
    while (removed < k)
    {
    st.pop();
    removed++;
    }
    if(st.empty())return "0"; // Makes code faster anyways
    // second last if can handle it
    int idx = st.size();
    string ans(idx, '%'); // Prevents reversing the string
    while (!st.empty())
    {
    ans[--idx] = st.top();
    st.pop();
    }
    int i = 0;
    while (i < ans.size() && ans[i] == '0')
    i++;
    // The erase function removes i characters
    // from given index (0 here)
    ans.erase(0, i);
    // If are using reversal
    // while(ans.size() > 0 && ans.back() == '0')
    // ans.pop_back();
    if (ans.empty())
    return "0";
    return ans;
    }
    };
    // This is a good question to study edge cases.
    // 1) k char may not be removed
    // 2) ans may contain leading zeroes
    // 3)
    // TC => O(N) + O(K) + O(N) + O(N)
    // SC => O(N) + O(N)
    int main(){
    return 0;
    }

  • @KartikeyTT
    @KartikeyTT 5 місяців тому

    tysm sir

  • @rutujashelke4208
    @rutujashelke4208 3 місяці тому

    Understood

  • @aryankumar3018
    @aryankumar3018 4 місяці тому

    understood

  • @abhinavabhi3568
    @abhinavabhi3568 8 днів тому

    Understood