All posts in Algorithms
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
Problem statement Given a set of intervals in any order merge the overlapping intervals and return the list of merged intervals. Sample input

[{6,8} {2,4} {1,3} {5,5} {1,4} {3,4} {6,8} {8,10}] 
Sample output
Solution The first step we are going to take is sort the intervals in ascending order based on their ending time. Next, we . . . Read more
Problem statement is a chess piece that moves in an shape. We define the possible moves of as any movement from some position to some satisfying either of the following: and , or and Note that and allow for the same exact set of movements. For example, the diagram below . . . Read more
Problem statement Given an array with numbers print a longest increasing subarray in . Sample Input

1 2 3 0 5 19 23 45 1 2 10 
Sample Output
Solution We want to solve this problem in time complexity. The easiest approach is to to start iterating over our array and increase our sequence length as long as . . . . Read more