Binary Tree Inorder Traversal (Java)

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Best Time to Buy and Sell Stock II

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: DP

maxProfit[i]=maxProfit[i-1]+prices[i]-prices[i-1] if prices[i]>prices[i-1]

maxProfit[i]=maxProfit[i-1] if prices[i]<=prices[i-1]

Generate Parentheses (Java)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"




Solution: Greedy and Recursive

Take advantage of the feature of parentheses, left side and right side must match each other,  in other words, if there a left side parenthese,  whatever position it is, there must be a right side parenthese to match it.

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution: DP

ways[n]=ways[n-1]+ways[n-2];

No matter what n is,  it must be reached  from n-1 or n-2 , then use array to  record unique ways from 0 to end 

Best Time to Buy and Sell Stock (Java)

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:
loop through entire list  and  catch min_price and the position of this this price, when current reached price's position after min_price's position then do calculate difference and up max_profit

Unique Paths Java

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Solution:DP 

Ways to destination point is equal to ways to up neighbor of destination point and left neighbor of destination point 

then we can generalize 

ways[m][n]=ways[m-1][n] + ways[m][n-1]

Binary Tree Postorder Traversal (Java)

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution;

For iterative solution, we know postal order is visit children before parent so  a stack could be apply here as a helper structure. Then, we can ' push left child from root until left most leaf into stack. then start pop node  from the stack, however, if the current node which going to be pop out has right node we should start push all left nodes of the right child until to leaf. But the trick point is how to tell if the mid need to be pop out  , We can use a child node to catch every popped out  node, then if the mid's right node equal to child node which mean this mid's right node has been visited, it is a good time to pop out the mid one .

Permutations (Java)

Given a collection of numbers, return all possible permutations.

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

Minimum Path Sum (Java)

 

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Apply DFS first failed on time limitation, then adopted DP with 2 dimension matrix passed OJ, finally refector code to use 1 dimension rotational array

Search a 2D Matrix (Java + Python)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

For an  O (rows * cols) solution is too simple to meet the interviewer’s expectation. So what is the better solution should be? Binary search should be a good tool when I face search problem, however, how BS could be apply  in matrix?   if we regard 0 as start point, total_cols*total_rows-1 as the end point to look the matrix as a array then we can apply BS. However, how could we convert the position to row_NO and col_NO?  We  know row_NO * total_cols+col_NO=position, So in programming  row_NO=postion/total_cols, col_NO=postion%total_cols. then we can adapt this feature in our program  to apply binary search to get O(log(cols+rows)) search

Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Remove Duplicates from Sorted Array II (Python + Java)

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Spiral Matrix II ( Java + Python)

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

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

Set Matrix Zeros (Java and Python)

Set Matrix Zeroes

 Total Accepted: 10610 Total Submissions: 35135My Submissions

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Pascal's Triangle II Java+Python

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Path Sum (Java and Python)

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

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

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

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Combinations (Java)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

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

Solution: a classical DFS problem, pay attention to the format of solve this question which can be apply to many other DFS problems

Remove Nth Node From End of List (Java)

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Populating Next Right Pointers in Each Node II (Java and Python)

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Solution : The main idea actually is tree level traversal, we can just use one node called current represent current level (start from root) and two other nodes which called nextLevelHead and nextLevelEnd to record next level's left child and right child and when current node is null then exchange current and nextLevelHead until nextLevelHead is also null

Palindrome Number (Java and Python)

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem

Sum Root to Leaf Numbers(Java and Python)

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

When I met this question, I intuitively come out that recursion may be a good way to solve this problem. For a recursive solution, the base case is extremely important and it is always the key point to solve a question.

Depend on my experience, for a tree question, the root==null is always a base case, another base case in this question is decided when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this situation and it also should be a base case here. Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum variable. The reason I use an array to hold the same value is because Java can only passed by value. For example, 

in a=1; void calculate(int a){ a=a+1; } System.out.println(a); // the result is still 1 , not 2 In order to track sum value of each calculation and not return the value of sum, we should use a collection or a wrapper class to hold it  

So I use an array here to hold this sum value. If you anybody has another way to solve this problem, please leave a comment for me.

Minimum Depth of Binary Tree (Python and Java)

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Search in Rotated Sorted Array (Java+Python)

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

       

Search a item in sorted array we should think about binary search. Cause the given array has been rotated unknow times, so binary search can not be apply directly here.

       

Throgh observation we can see, no matter how a sorted array be rotated, there is

 always one side is sorted.

       

So we can pick the middle item at first and compare it with given array's leftMost and rightMost items to check which side is sorted, for given example 4, 5 , 6, 7 , 0 , 1, 2

mid is 7, leftMost is 4, rightMost is 2, because of 4<7 so we can know left side is sorted.

       

Depend on the conclusion we got above, if the given target is between 4->7, such as 6, we can just seach left side for it, otherwise we search the right side.

       

A trick situation is when duplicate exist in the array, discard the requriement of this quesiton, my         solution will also cover duplicate exist situation. 

If duplicate exist, then leftMost or rightMost item may equal to middle item, if only one of them equal to mid such as A[leftMost]==A[mid] then from leftMost to Mid should have same value. then we can only search the right side from mid to right most. If both A[rightMost] and A[leftMost] equal to A[Mid] we have to search both sides.

Trapping Rain Water (Java + Python)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Solution: DP 

 To calculate the total volume is to calculate volumes can hold at each position.

 To calculate how many volumes can hold at each position is to calculate it's right bound height  and right bound height 

Current position can hold water only at the situation when the low side among both sides higher than the height at current position

If so,  use the lower one minus current height as height to multiply the width 1 is how many volumes can hold at current position

How to calculate the height of both sides for each position? We can apply DP theory to record  highest height bound can get from left to current and highest height bound can get from right to current  

HigehstLeftSideHeight so far from giving example, should be  0,1,1,2,2,2,2,3,3,3,3,3

HighestRightSideHeight so far for given example is 1,2,2,2,3,3,3,3,3,3,3,3

Then loop through giving array for each position to calculate how many volumes can hold there and update the total volume it can hold

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]]