[LeetCode] Median of Two Sorted Arrays (More elegant solution)

I have written a solution for this question before: http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-java/ That solution seems easy to understand. However, it turns out to be very difficult to implement. The hardest part is how we come up with a correct way to handle borders. After reading some post, I found there is another way to achieve findKth number from two … Read more[LeetCode] Median of Two Sorted Arrays (More elegant solution)

[LeetCode] Palindrome Partitioning I and II(Java)

Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = “aab”, Return

Palindrome Partitioning II Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = “aab”, … Read more[LeetCode] Palindrome Partitioning I and II(Java)

[LeetCode] Best Time to Buy and Sell Stock III (Java)

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Analysis In this … Read more[LeetCode] Best Time to Buy and Sell Stock III (Java)

[LeetCode] Distinct Subsequences (Java)

Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not). Here is an example: … Read more[LeetCode] Distinct Subsequences (Java)

[LeetCode] Recover Binary Search Tree (Java)

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? Analysis We can use in-order traverse to find the swapped element. During the traverse, we can find the element that … Read more[LeetCode] Recover Binary Search Tree (Java)

[LeetCode] Validate Binary Search Tree (Java)

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees … Read more[LeetCode] Validate Binary Search Tree (Java)

[LeetCode] Unique Binary Search Trees I and II (Java)

Unique Binary Search Trees Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s.

Unique Binary Search Trees II Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique … Read more[LeetCode] Unique Binary Search Trees I and II (Java)