All posts tagged algorithms
Problem statement 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 inplace, do not allocate extra memory. Here are some examples. . . . Read more
Problem statement Merge k sorted linked lists and return it as one sorted list. Solution We reduce the problem to the merging of two linked lists problem. This can be done in time and space. So we first write out the function to merge two sorted lists:

def merge(self, lst1, lst2): if lst1 == None: return lst2 if lst2 == None: return lst1 if lst1.val < lst2.val: lst1.next = self.merge(lst1.next, lst2) return lst1 else: lst2.next = self.merge(lst1, lst2.next) return lst2 
We can . . . Read more
Problem statement Given a set of candidate numbers (without duplicates) and a target number , find all unique combinations in where the candidate numbers sums to . The same repeated number may be chosen from unlimited number of times. Note: All numbers (including target) will be positive integers. The solution . . . Read more
Problem statement Given an array of integers, are there elements in such that ? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. For example, given array , A solution set is: Solution The idea behind the . . . Read more
Problem statement Given pairs of parentheses, write a function to generate all combinations of wellformed parentheses. For example, given , a solution set is:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ] 
Solution
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

class Solution(object): def generate(self, n, open_count, closed_count, s, result, visited): visited.add(s) if open_count == n and closed_count == n: result.append(s) for i in range(0, 2*nlen(s)): if open_count < n and not s+'(' in visited: self.generate(n,open_count+1, closed_count, s+'(', result, visited) if closed_count < open_count and not s+')' in visited: self.generate(n,open_count, closed_count+1, s+')', result, visited) def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ ans = [] self.generate(n, 0, 0, '', ans, set()) return ans def main(): solution = Solution() print(solution.generateParenthesis(10)) if __name__ == "__main__": main() 
Problem statement Given a string , find the longest palindromic substring in . You may assume that the maximum length of is . Sample input 1
Output 1
Sample input 1
Output 1
Solution We are going to iterate over each character in the input string . . . Read more
Problem statement Given an array of strings, group anagrams together. Sample input

["eat", "tea", "tan", "ate", "nat", "bat"] 
Sample output

[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] 
Note: All inputs will be in lowercase. Full code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ map = {} for w in strs: key = ''.join(sorted(w)) if not key in map: map[key] = [] map[key].append(w) return map.values() def main(): solution = Solution() print(solution.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])) if __name__ == "__main__": main() 
Problem statement Given a set of distinct integers, , return all possible subsets. Note: The solution set must not contain duplicate subsets. Sample input
Sample output

[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]] 
Full code
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

class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ power_set = [] power_set.append([]) for n in nums: new_power_set = [] for subset in power_set: new_power_set.append(subset) new_subset = subset[:] new_subset.append(n) new_power_set.append(new_subset) power_set = new_power_set return power_set def main(): solution = Solution() print(solution.subsets([1,2,3])) if __name__ == "__main__": main() 
Problem statement Given a linked list, swap every two adjacent nodes and return its head. For example: Given 1>2>3>4, you should return the list as 2>1>4>3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. Full code . . . Read more
Problem statement Given n nonnegative integers , where each represents a point at coordinate . vertical lines are drawn such that the two endpoints of line is at and . Find two lines, which together with xaxis forms a container, such that the container contains the most water. Note: You . . . Read more