Posted on | In

Test cases

1
2
3
4
5
6
7
8
["MinStack","push","push","push","push","pop","getMin","pop","getMin","pop","getMin"]
[[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]]
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
["MinStack","push","push","push","getMin","pop","getMin"]
[[],[0],[1],[0],[],[],[]]
["MinStack","push","push","push","top","pop","getMin","pop","getMin","pop","push","top","getMin","push","top","getMin","pop","getMin"]
[[],[2147483646],[2147483646],[2147483647],[],[],[],[],[],[],[2147483647],[],[],[-2147483648],[],[],[],[]]

Solution 1: accepted 111ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MinStack {
    private Stack<Integer> master;    
    private Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        master = new Stack<>();    
        min = new Stack<>();
    }
    
    public void push(int x) {
        master.push(x);
        if (min.size() == 0 || min.peek() >= x) {  // >= rather than >, there could be multiple minimum values
            min.push(x);
        }
    }
    
    public void pop() {
        if (master.pop().equals(min.peek())) {  // Integer, use equals not ==
            min.pop();
        }
    }
    
    public int top() {
        return master.peek();   
    }
    
    public int getMin() {
        return min.peek();    
    }
}

Follow-up:

If the given numbers have a lot of duplicates, how to optimize the space use of the min stack?
We now maintain <number, the index of the number when it's added> in the min stack and we only pop it when the current index is equal or smaller than the index of the top element in the min stack. As a result, we also need a int count to track the index.

Posted on | In

Solution 1: accepted 1ms

Create a new node, looks not good. 

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode newHead = null;
    while (cur != null) {
        ListNode temp = new ListNode(cur.val);
        temp.next = newHead;
        newHead = temp;
        cur = cur.next;
    }
    return newHead;
}

Solution 2: accepted 0ms

No new nodes created yet still complicated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        if (newHead != null) {  // unnecessary condition
            head.next = newHead;
            newHead = head;
        } else {
            newHead = head;
            newHead.next = null;
        }
        head = next;
    }
    return newHead;
}

Solution 3: accepted 0ms

Should be the most concise iterative solution.

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

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

Solution 4: accepted 1ms

Recursive solution.

  1. Base case: when head == null || head.next == null, we have the newHead, which is the last element in LinkedList.
  2. Recursive rule: next.next = current; current.next = null.

Time: O(n)
Space: O(n) (stack space consumption) 

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head; // find the newHead which remains throughout the program
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head; // if we use newHead.next, we lost nodes in the middle
    head.next = null;
    return newHead;       
}

Posted on | In

Solution 1: accepted

Amortized O(1) operations: pop() and peek(). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MyQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;
    
    /** Initialize your data structure here. */
    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        input.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.isEmpty()? 1 : output.pop();
    }
    
    /** Get the front element. */
    public int peek() { // similar to pop()
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.isEmpty()? 1 : output.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

Posted on | In

Solution 1: accepted 0ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        if (p == null && q == null) { // both p, q are null
            return true;  
        }
        else if (p != null && q != null) { // both p, q are not null
            return (p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
        }
        else {  // one of p, q is null
            return false; 
        }
    }
}

Posted on | In

Solution 1: accepted 2ms

BFS. Simply reverse the result from question 102. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (root == null) {
      return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
      ArrayList<Integer> list = new ArrayList<>();
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        list.add(node.val);
        if (node.left != null) {
          queue.add(node.left);
        }
        if (node.right != null) {
          queue.add(node.right);
        }
      }
      result.add(list);
    }
    Collections.reverse(result);
    return result;
}

Posted on | In

Solution 1: accepted 16ms

A common brute force solution 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || k == 0) {
        return head;
    }
    ListNode dummy = head;
    ListNode tail = null;
    int length = 0;
    while (dummy != null) {
        tail = dummy;
        dummy = dummy.next;
        length++;
    }
    
    k = k % length;
    dummy = head;
    for (int i = 1; i < length - k; i++) {
        dummy = dummy.next;
    }
    
    ListNode newHead = head;
    if (dummy.next != null) {
        newHead = dummy.next;
        dummy.next = null;
        tail.next = head;
    }
    return newHead;
}

Posted on | In

Test cases

1
2
3
4
5
6
7
[]
[1,1]
[1,1,2]
[1,1,2,2]
[1,2,2,3]
[1,2,2,3,3]
[1,2,3,4,5]

Solution 1: accepted 1ms

Try to use only ListNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode deleteDuplicates(ListNode head) {
    ListNode pointer = head;
    ListNode previous = null;
    while (pointer != null) {    
        ListNode fast = pointer.next;
        boolean duplicate = false;
        while (fast != null && pointer.val == fast.val) {
            fast = fast.next;
            duplicate = true;
        }
        if (!duplicate) {
            previous = pointer;
        } else {
            if (previous == null) { // [1,1,...]
                head = fast;
            } else {
                previous.next = fast; // [1,2,2,3...]
            }
        }
        pointer = fast;
    }
    return head;
}

Solution 2: accepted 1ms

Use a virtual node to help organize the list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode deleteDuplicates(ListNode head) {        
    ListNode virtualHead = new ListNode(0);
    virtualHead.next = head;
    ListNode pre = virtualHead;
    ListNode cur = head;
    while (cur != null) {                
        while (cur.next != null && cur.val == cur.next.val) {
            cur = cur.next;
        }
        if (pre.next == cur) { // if both pre and cur point to the same node (no duplicates detected)
            pre = cur; // simply move on
        } else { 
            pre.next = cur.next; // skip points in between
        }
        cur = cur.next; // move on
    }
    return virtualHead.next;
}

Posted on | In

Solution 1: accepted 1ms

pointer - slow
next - fast 

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode deleteDuplicates(ListNode head) {
    ListNode pointer = head;
    while (pointer != null) {
        ListNode next = pointer.next;
        while (next != null && pointer.val == next.val) {
            next = next.next;
        }
        pointer.next = next;
        pointer = pointer.next;
    }
    return head;
}

Posted on | In

Solution 1: accepted 3ms 93%

Well, it shouldn’t be this long. Can we optimize it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    head = dummy;
    for (int i = 1; i < m; i++) {
        head = head.next;
    }
    ListNode cur = head.next;
    ListNode rev = null; // reversed part
    ListNode tail = null;
    int count = n - m;
    for (int i = m; i <= n; i++) {
        ListNode temp = cur.next;
        if (rev != null) {
            cur.next = rev;
            rev = cur;
        } else {
            rev = cur;
            tail = cur;
            rev.next = null;
        }
        cur = temp;
        count--;
        if (i >= n) {
            tail.next = cur;
            head.next = rev;
        }
    }
    return dummy.next;
}

Posted on | In

Solution 1: accepted

In-order traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private int last = Integer.MIN_VALUE;
    private boolean first = true; // for special case [-2147483648]
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        if (!isValidBST(root.left)) {
            return false;
        }
        
        if (!first && last >= root.val) {
            return false;
        }
        first = false;
        last = root.val;
        
        if (!isValidBST(root.right)) {
            return false;
        }
                
        return true;
    }
}