Delete nodes which have a greater value on right side

The problem, simply

You get a singly linked list of numbers. Delete every box that has a strictly bigger number anywhere to its right. Keep the rest in their order and return the new head.

The boxes that stay are the leaders: each one is at least as big as everything after it. That means the answer always reads from big to small (or equal).

A story to remember it

Picture it

Examples

Way 1: the simple way

For each box, look at every box to its right. If one is bigger, cut the box out.

1. Use a dummy box in front of the head, so cutting the head is no different from cutting any other box. Put prev on the dummy.
2. For each box curr: scan everything after it for a bigger number.
3. If you find one, skip curr with prev.next = curr.next. If not, move prev to curr.

class Solution {
    Node compute(Node head) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node prev = dummy, curr = head;
        while (curr != null) {
            boolean blocked = false;
            for (Node r = curr.next; r != null; r = r.next) {
                if (r.data > curr.data) { blocked = true; break; }   // someone bigger later
            }
            if (blocked) prev.next = curr.next;   // cut curr out
            else prev = curr;                      // keep it
            curr = curr.next;
        }
        return dummy.next;
    }
}

How long it takes: each box may scan all boxes after it, O(n^2). Extra room: a few fingers, O(1).

Way 2: the clever way

The parade trick needs us to walk from the right end. A singly linked list only walks from the left, so flip it first.

1. Reverse the list. Now the old last box is the head.
2. The new head always stays. Set max to its value and put curr on it.
3. Look at curr.next. If it is smaller than max, a bigger box was to its right in the original, so skip it: curr.next = curr.next.next. Otherwise keep it: move curr there and set max to its value.
4. When curr.next is null, reverse the list back and return it.

class Solution {
    Node compute(Node head) {
        if (head == null) return null;
        head = reverse(head);                 // walk from the parade end
        Node curr = head;
        int max = head.data;                  // the tallest kid so far
        while (curr.next != null) {
            if (curr.next.data < max) {
                curr.next = curr.next.next;   // blocked, cut it out
            } else {
                curr = curr.next;             // can see, keep it
                max = curr.data;
            }
        }
        return reverse(head);                 // back to the original direction
    }

    private Node reverse(Node head) {
        Node prev = null, curr = head;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

How long it takes: two flips and one sweep, O(n). Extra room: a few fingers, O(1).

Watch out for

• Using <= instead of <. Equal values are not bigger, so they stay.
• Forgetting the second reverse. The answer would come out backwards: 3 6 11 15.
• Updating max before comparing. Compare first, then update only when you keep the box.
• In Way 1, cutting the head without a dummy box. The dummy makes the head just another box.

What interviewers ask next

• Can you do it without reversing? Yes, with recursion: clean up the rest of the list first, then compare the head with the new next box. If the head is smaller, drop it and return the next box. That is O(n) time but O(n) stack.
• Use a stack instead. Walk left to right, and while the top of the stack is smaller than the current box, pop it. Push the current box. The stack, bottom to top, is the answer. This is a monotonic stack, O(n) time and O(n) room.
• Do the same on an array: leaders in an array. Walk from the right with a running max. No reversal needed because arrays can walk backwards.
• Remove nodes that have a smaller value on the right instead. Same idea with a running min.

Remember this

Grown-up words: the kids who can see are leaders, the tallest so far is a running maximum, cutting a box out is unlinking a node, the dummy box is a sentinel node, and the stack version is a monotonic stack.