Valid Parentheses ( Java + Python)

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Longest Common Prefix (Java)

Leetcode

Write a function to find the longest common prefix string amongst an array of strings.

Anagrams (Java)

LeetCode

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Valid Sudoku (Java)

LeetCode

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution: Helpe table

Declare 9 boolean array with length 9  separately for rows, columns and blocks and hold them in ArrayList. Because the number range of sudoku is 1-9, so each number in each row, col and block should be unique, then we can go through every position of given board, check if the number has been

Found in current row,current column  and current block. If so, return false;

*** Be careful about the index of block in blockChecker

Path Sum II (Java)

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution:  DFS

Apply DFS check every possible combination, record result if meet requirement

Subsets (Java)

Leetcode

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution: DFS

For  subset of a given set, it must contain a [],
So we can initialize a result with [[]] as start point.  For example, given set [1,2,3]
We can build the result from [[]]-> [[],[1]]->[[],[1],[2],[1,2]]->[[],[1],[2], [1,2], [3], [1,3], [2,3], [1, 2,3]]

Jump Game (Java)

Leetcode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

3Sum Closest (Java)

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

Convert Sorted List to Binary Search Tree (Java)

Given a singly linked list where elements are sorted in ascending order, convert it to a height 

balanced BST.

Solution:

Provide two solutions below.  One is relatively simple to come out which just convert the LinkedList to
 array then Convert the array to BST. But this solution may not be the one Interviewer wants.

The second one  performs the conversion in place, apply the feature of linked list  we can build the tree
from  bottom to up. Meanwhile use start and end two value to indicate the bounds

Search for a Range (Java)

Leetcode

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Solution: because of O(logn), so we should consider about binary search, so how to apply binary search to find the low bound and high bound? We can make target -0.5 for searching low bound and target+0. 5 for the high bound. Be careful the corner case

Flatten Binary Tree to Linked List (Java)

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution:

Divide and Conquer, convert left and right tree to list separately, then connect root. right to list converted by left tree, make root. left to null, then search for the lastNode of right tree and connect it to list converted by original right tree.

Count and Say (Java)

Leetcode

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Binary Tree Zigzag Level Order Traversal (Java)

LeetCode

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Combination Sum

LeetCode

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

Solution: DFS

calculate each possible combination

Partition List (Java)

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Triangle (Java)

LeetCode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution: DP (met during Amazon interview)

Declare pathSum array with length of triangle size(). For triangle, the bottom row length is equal to the height of triangle, so use pathSum to hold the bottom row's value, then from bottom to up, find minimum path

Pow(x, n) (Java)

LeetCode:

Implement pow(x, n).

Solution: Binary Search

N-Queens (Java)

Leetcode

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Slution: DFS

Insertion Sort List (Java)

LeetCode

Sort a linked list using insertion sort.

Add Binary (Java)

LeetCode

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Letter Combinations of a Phone Number (Java)

Leetcode

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Solution: DFS, Helper table

Construct Binary Tree from Inorder and Postorder Traversal (Java)

LeetCode

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Validate Binary Search Tree (Java)

LeetCode

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 must also be binary search trees.

Construct Binary Tree from Preorder and Inorder Traversal (Java)

LeetCode

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution: Divide and Conquer

According to the rule of preorder traversal,  the first item in the preorder array must be the root. and the question also told us "You may assume that duplicates do not exist in the tree." so we can go through inorder array find the root's position, then  we got left tree and right tree. finally we can apply recursion to got the tree we want base on above logic.

Reverse Linked List II (Java)

LeetCode

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Next Permutation (Java)

LeetCode

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1




Permutations II (Java)

LeetCode

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Best Time to Buy and Sell Stock III (Java)

LeetCode

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).

Solution: Divide and Conquer, DP

O(n^2) solution is easy came out, we can use O(n) time to get max profit depend on the solution of Best Time to Buy and Sell Stock I. so we can just dived the whole prices array at every point , try to calculate current max profit from left and right and then add them together is what we want. However, there are many repeat calculation when calculate left max profit and right max profit. So we can apply DP to record max profits for each left side and right side. then add them together at each point use one for loop

Remove Duplicates from Sorted List II (Java)

LeetCode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution: 

The logic is pretty straight, however, the corner cases need pay more attention.
check the comments in the code.