LeetCode Daily Problem 2487: May 6, 2024

Again, an Easy level problem. The intuition can be built in the way of visualizing values in a plot and traversing nodes from the end and removing the nodes that break the increasing trend. The point where discontinuity occurs i.e. decrease tend starts, remove the node. So, the brute force solution is straightforward:

1. Given LL = [5, 2, 13, 8, 26, 2, 1]
2. reverse the linked list e.g. [1, 2, 26, 8, 13, 2, 5]
3. keep a maxi = value of the first node i.e. maxi = 1
4. run a loop to check which node->val < maxi and remove these nodes & keep updating maxi value.
5. reverse the final linked list.

T.C. = O(3n)
S.C. = O(1)

e.g. [5, 2, 13, 8, 26, 2, 1] → reverse [1, 2, 26, 8, 13, 2, 5] → remove (8 as 8 < 26) → remove [13, 2, 5] as they all are also < 26 → final LL = [1, 2, 26] → reverse [26, 2, 1]

class Solution {
    ListNode* reverseLL(ListNode *root) {
        ListNode *curr = root, *prev = NULL;
        while(curr) {
            ListNode* temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }

public:
    // T.C. = O(3n), S.C. = O(1)
    ListNode* removeNodes(ListNode* head) {
        ListNode *rev1 = reverseLL(head);
        ListNode *itr = rev1;
        int maxi = rev1->val;

        while(rev1 && rev1->next) {
            if(rev1->next->val < maxi) {
                rev1->next = rev1->next->next; // removing the node
                continue;
            }
            if(rev1->next) maxi = max(maxi, rev1->next->val);
            rev1 = rev1->next;
        }
        return reverseLL(itr);
    }
};

Although, above solution looks great but to escape 3 loops & code complexity, the most easiest and convenient approach is implemented using recursion. Algorithm:

1. reach the end of the LL
2. check if currNode->val < currNode->next->val i.e. if it’s [5, 8] and we are at 5, we’ll check if 5 < 8.
   Yes, 5 < 8, so instead of returning 5, return 8 i.e. currNode->next;
3. Else return head;

T.C. = O(n)
S.C. = O(n) // recursion stack space

class Solution {
public:
    // using recursion T.C. = O(n), S.C. = O(n)
    ListNode* removeNodes(ListNode* head) {
        if(!head) return NULL;
        head->next = removeNodes(head->next);
        if(head->next && head->val < head->next->val) return head->next;
        return head;
    }
};

Keep grinding, folks!

sakiV