Subsets with Duplicates

Description LeetCode 90 Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Analysis Subset problem has not only one solution. The easiest solution is bit method. Just use

Development Environment for Mac

1 Chrome Directly download Chrome from https://www.google.com/chrome/. 2 Xcode Directly install Xcode from App Store. 3 Xcode command line tools Open Terminal and agree the Xcode license. Then install Xcode command line tools. 4 iTerm2 ITerm 2 is a comfortable terminal. It can be downloaded from https://www.iterm2.com/downloads.html. 5 Homebrew This is a tool that can help

Scramble String

Description LeetCode 87 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = “great”: great / \ gr eat / \ / \ g r e at / \ a t To scramble the string, we may choose any non-leaf node

Maximal Rectangle

Description LeetCode 85 Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area. Example: Input: [ [“1″,”0″,”1″,”0″,”0”], [“1″,”0″,”1″,”1″,”1”], [“1″,”1″,”1″,”1″,”1”], [“1″,”0″,”0″,”1″,”0”] ] Output: 6 Analysis When firstly considering about this problem, the problem seems to be a extension of Largest Rectangle in Histogram. But how can

Largest Rectangle in Histogram

Description LeetCode 84 Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].   The largest rectangle is shown in the shaded area, which has area = 10 unit.

Word Search

Description LeetCode 79 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example: board = [ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’],

Edit Distance

Description Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = “horse”, word2 = “ros” Output: 3 Explanation: horse -> rorse (replace ‘h’ with ‘r’) rorse -> rose (remove

Simplify Path

Description LeetCode 71 Given an absolute path for a file (Unix-style), simplify it. For example, path = “/home/”, => “/home” path = “/a/./b/../../c/”, => “/c” Corner Cases: Did you consider the case where path = “/../”? In this case, you should return “/”. Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”. In this case, you should ignore redundant slashes and return “/home/foo”.

Search in Rotated Sorted Array

Description LeetCode 33 Suppose an array sorted in ascending order 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. Your algorithm’s runtime complexity must be in

Find First and Last Position of Element in Sorted Array

Description LeetCode 34 Given an array of integers nums sorted in ascending order, 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]. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: