Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[1]
0
[2]
3
[5]
5
[1,2,5]
4
[1,2,5]
11
[2,5,10,1]
27
[186,419,83,408]
6249
[156,265,40,280]   // TLE
9109

Solution 1: TLE

DP.

  1. Base case: dp[0] = 0
  2. Induction rule: dp[i] = min(dp[j] + 1) where j < i;

Time: O(n^3)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for(int i = 1; i <= amount; i++) {
      for (int j = 0; j < i; j++) {
        for (int value: coins) {
          if (value == i - j && dp[j] != Integer.MAX_VALUE) {
            dp[i] = Math.min(dp[i], dp[j] + 1);
          }
        }
      }
    }
    return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];
}

Solution 2: accepted 27ms

Dp.
Instead of check every value in (1, i), we only check the possible coin value, which is a much smaller range.

Time: O(n^2)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    Arrays.sort(coins);
    dp[0] = 0;
    for(int i = 1; i <= amount; i++) {
      for (int j = 0; j < coins.length; j++) {
        if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE) {
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
      }
    }
    return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];
}

Posted on | In

Solution 1: TLE

No DP bro. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class NumArray {
  int[] nums;
  public NumArray(int[] nums) {
    this.nums = nums;
  }
  public int sumRange(int i, int j) {
    int sum = 0;
    for(int k = i; k <= j; k++) {
      sum += nums[k];
    }
    return sum;
  }
}

Solution 2: accepted 198ms

DP.
Time: O(n)
Space: O(1) (no extra) 

1
2
3
4
5
6
7
8
9
10
11
12
13
public class NumArray {
  int[] nums;
  public NumArray(int[] nums) {
    this.nums = nums;
    for(int i = 1; i < nums.length; i++) {
      nums[i] += nums[i-1];
    }
  }
  public int sumRange(int i, int j) {
    return (i == 0)? nums[j] : nums[j] - nums[i-1];
  }
}

Posted on | In

Solution 1: accepted 17ms 3.83%

In your dream. 

1
2
3
4
5
6
7
public String reverseString(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = s.length() - 1; i >= 0; i--) {
        sb.append(s.charAt(i) + ""); // charAt() is too expensive
    }
    return sb.toString();
}

Solution 2: accepted 4ms

Well, this is cheating XD. Try to imagine and implement what’s inside the function. 

1
2
3
4
public String reverseString(String s) {
    StringBuilder sb = new StringBuilder(s);
    return sb.reverse().toString(); // reverse() has bitwise implementation so it's pretty fast
}

Solution 3: accepted 2ms 77.7%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String reverseString(String s) {
    // if (s.length() < 2) return s; // no impact on performance  
    char[] A = s.toCharArray(); // implementation: java.lang.System.arraycopy()
    int l = 0;
    int r = A.length - 1;
    while (l < r) {
        char temp = A[l];
        A[l] = A[r];
        A[r] = temp;
        l++;
        r--;
    }
    return String.valueOf(A);
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
[10]
[1,2,3,4]
[1]
[1,2,3,4]
[1,2,3,4,5,6]
[1,6]
[1,2,3,4,5,6]
[2]
[1,2,3,4,5,6]
[4]
[1,2,3,4,5,6]
[2, 4]

Posted on | In

Solution 1: accepted

This is an easy one.

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
public class Solution {
    public boolean isValid(String s) {
        Stack cache = new Stack();
        
        for (int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);
            if (current == '(' || current == '[' || current == '{')
                cache.push(current + "");
            
            if (current == ')')
                if (!cache.isEmpty() && cache.peek().equals("("))
                    cache.pop();  
                else
                    return false;
            if (current == ']')
                if (!cache.isEmpty() && cache.peek().equals("["))
                    cache.pop();  
                else
                    return false;
            if (current == '}')
                if (!cache.isEmpty() && cache.peek().equals("{"))
                    cache.pop();  
                else
                    return false;
            }
           
        
        
        return cache.isEmpty();
    }
}

Posted on | In

Solution 1: accepted

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 removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0)
            return head;
        
        ListNode dummy = new ListNode(0); // Use an empty head to avoid dealing with the head, such as NPE
        dummy.next = head;     
        ListNode fast = head;
        ListNode slow = dummy;
        
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        
        while (fast.next != null) {
            slow = slow.next;  // Change slow will only change what slow points to
            fast = fast.next;
        }
        // slow = [3,4,5]
        // fast = []
        // dummy = [0,1,2,3,4,5]
        
        // Change slow.next changes its value in memory, which is also referred by dummy,
        // therefore, dummy changed as well!
        slow.next = slow.next.next; 
        
        // slow = [3,5]
        // dummy = [0,1,2,3,5]
        
        return dummy.next;    // dummy starts with 0
    }

Why?

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

1
slow.next = slow.next.next;

will change both dummy and slow (but not head) whereas

1
2
3
slow = slow.next;
//or
slow = slow.next.next;

will only change slow, not dummy

Why?

If we retain both

1
2
dummy.next = head;
slow.next = head;

[1] 1 will return [1] instead of [], so we need to discard one of them

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
[1]
1
[]
0
[1,2,3,3,4,7,0,0,0]
6
[6,9,10]
3
[4,5,6,0,0,0]
3
[1,2,3]
3

Solution 1: accepted 0ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void merge(int[] nums1, int m, int[] nums2, int n) {
    m--;
    n--;
    while (m >= 0 || n >= 0) {  // this part is ugly
        if (n < 0) {  // not necessary, the rest of the nums1 is sorted
            nums1[m + n + 1] = nums1[m];
            m--;
        } else if (m < 0) {
            nums1[m + n + 1] = nums2[n];  
            n--;
        } else if (nums1[m] >= nums2[n]) {
            nums1[m + n + 1] = nums1[m];
            m--;
        } else {
            nums1[m + n + 1] = nums2[n];
            n--;
        }
    }
}
Conflict: can’t avoid, we need two loops
1
2
3
4
5
6
7
if (n < 0 || nums1[m] >= nums2[n]) {  // this line will raise error on nums2[n] when n < 0
    nums1[m + n + 1] = nums1[m];
    m--;
} else if (m < 0 || nums2[n] > nums1[m]) {
    nums1[m + n + 1] = nums2[n];
    n--;
}
Improved version
1
2
3
4
5
6
7
8
9
10
11
12
public void merge(int[] nums1, int m, int[] nums2, int n) {
    m--;
    n--;
    while (m >= 0 && n >= 0) {
        nums1[m + n + 1] = nums1[m] >= nums2[n]? nums1[m--] : nums2[n--];
    }
    while (n >= 0) {  // only need to deal with leftovers in nums2
        nums1[m + n + 1] = nums2[n];
        n--;
    }
}

Posted on | In

Test case

1
2
3
4
[][]
[1][]
[][1]
[-1,0,5][1,2,3]

Solution 1: accepted

Well…this is a 2ms solution, but only beats 2%! We have to do more!

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
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode temp = result;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                temp.next = new ListNode(l2.val);
                l2 = l2.next == null? null : l2.next;
            } else if (l2 == null) {
                temp.next = new ListNode(l1.val);
                l1 = l1.next == null? null : l1.next;
            } else if (l1.val >= l2.val) {
                temp.next = new ListNode(l2.val);
                l2 = l2.next == null? null : l2.next;
            } else if (l1.val < l2.val) {
                temp.next = new ListNode(l1.val);
                l1 = l1.next == null? null : l1.next;
            }
            temp = temp.next;
        }
        
        return result.next;
    }
}

Solution 2: accepted

We only need to concatenate what’s left to the final result. This will significantly improve the performance when one list is much longer than the other.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode temp = result;
        while (l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                temp.next = new ListNode(l2.val);
                l2 = l2.next == null? null : l2.next;
            } else if (l1.val < l2.val) {
                temp.next = new ListNode(l1.val);
                l1 = l1.next == null? null : l1.next;
            }
            temp = temp.next;
        }
        if (l1 != null)
            temp.next = l1;
        else if (l2 != null)
            temp.next = l2;
        
        return result.next;
    }
}

Posted on | In

Test cases

1
2
3
4
5
"0"
"1231230"
"0123123"
"1230123"
"12300123"

Solution 1: accepted 4ms

If the number start with 0 or has two contiguous 0, it doesn not make sense so we return 0;

  1. Base case:
    dp[0] = 1;
    dp[1] = s.charAt(0) == ‘0’? 0 : 1;

  2. Induction rule:
    dp[i] = if char is ‘0’, skip; 

    else dp += dp[i-1], if previous is not '0' and prev + currt <= 26, dp += dp[i-2];  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int numDecodings(String s) {
    int len = s.length();
    if (len == 0) return len;
    int[] dp = new int[len + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0'? 0 : 1;
    for(int i = 2; i <= len; i++) {
        int one = Integer.parseInt(s.substring(i-1, i));
        int two = Integer.parseInt(s.substring(i-2, i));
        if (one > 0 && one < 10)
            dp[i] += dp[i - 1];
        if (two > 9 && two < 27)
            dp[i] += dp[i - 2];
    }
    return dp[len];
}

Posted on | In

Test cases

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

Solution1: accepted

Primitive brute solution. 1ms but is below 99%.

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
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
            
        ListNode result = new ListNode(0);
        ListNode operation = result;
        ListNode even = head.next;
        ListNode odd = head;
        boolean terminate = false;
        while (even != null || odd != null) {
            
            operation.next = new ListNode(even.val);
            operation = operation.next;
            
            if (even.next != null && even.next.next != null) 
                even = even.next.next;
            else 
                terminate = true;
                
            operation.next = new ListNode(odd.val);
            operation = operation.next;
            
            if (odd.next != null && odd.next.next != null) 
                odd = odd.next.next;
            else 
                terminate = true;
            
            if (terminate)
                break;
            // System.out.println(head);
        }
        if (odd != null && odd.next == null)
            operation.next = new ListNode(odd.val);
            
        return result.next;
        
    }
}

Solution 2: accepted

Bring forward the second number and remove it from the first listnode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode operator = dummy;
        
        while(operator.next != null && operator.next.next != null) {
            ListNode odd = operator.next;
            ListNode even = operator.next.next;
            operator.next = even;
            odd.next = even.next; // Remove the used additional even
            operator.next.next = odd;
            operator = operator.next.next;
        }
        return dummy.next;
    }
}

Solution 3: accepted

1
2
3
4
5
6
7
8
9
public class Solution {
    public ListNode swapPairs(ListNode head) {
       if(head == null || head.next == null) return head;
        ListNode nextNode = head.next;
        head.next = swapPairs(nextNode.next);
        nextNode.next = head;
        return nextNode;
    }
}