# LeetCode-Solutions-in-Swift 0,0,1,2,0,5

LeetCode Solutions in Swift 3.1

Where it all begins: https://github.com/apple/swift.

#### LeetCode Solutions in Swift 3.1

• Designed for your next job interview in Swift.
• Optimal solutions handpicked from the LeetCode community.
• Best time/space complexity guaranteed. (Think about O(1) space in Binary Tree Inorder Traversal. It’s that good.)
• Written with Swift-specific language features in mind. (guard/defer, map/filter/reduce, optionality, inout/@noescape, characters as extended grapheme clusters, etc)
• Comprehensive test cases guarding against wrong answers and timeouts.
• A work in progress. Currently at 102 / ( 453 - 79 Paid Subscription ) = 27.3%, with 612 test cases.

Please note: Subscript-based O(1) time random access to characters inside a string is not supported by Swift, due to the way Swift strings are stored. Amortized O(1) time random access could be achieved if we manually slice the string and convert it into an array.

##### Requires Xcode 8.3.1 (8E1000a) or later.
1. Two Sum - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N), s=O(N) - Inspired by @naveed.zafar
2. Add Two Numbers - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N), s=O(1) - Inspired by @potpie
3. Longest Substring Without Repeating Characters - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N), s=O(1) - Inspired by @heiyanbin
4. Median of Two Sorted Arrays - Hard - Swift Solution - ObjC Solution - Test Cases - t=O(log(min(m,n))), s=O(1) - Inspired by @MissMary - Be sure to read @MissMary’s full explanation on how she achieved logarithmic time complexity with a few nice mathematic tricks.
5. Longest Palindromic Substring - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N^2), s=O(1) - Inspired by @hh1985
6. ZigZag Conversion - Easy - Swift Solution - Test Cases - t=O(N), s=O(N) - Inspired by @dylan_yu
7. Reverse Integer - Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @wshaoxuan
8. String to Integer (atoi) - Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @yuruofeifei
9. Palindrome Number - Easy - Swift Solution - Test Cases, t=O(N), s=O(1) - Inspired by @hln9319
10. Regular Expression Matching - Hard - Swift Solution - Test Cases - DP, t=O(M*N), s=O(M*N) - Inspired by @xiaohui7
11. Container With Most Water - Medium - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @franticguy
12. Integer To Roman - Medium - Swift Solution - Test Cases - t=O(1), s=O(1) - Inspired by @flytosky
13. Roman To Integer - Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @makeittrue
14. Longest Common Prefix - Easy - Swift Solution - Test Cases - t=O(N*M), s=O(1) - Inspired by @garysui
15. 3Sum - Medium - Swift Solution - Test Cases - t=O(N^2), s=O(N) - Inspired by @peerlessbloom
16. 3Sum Closest - Medium - Swift Solution - Test Cases - t=O(N^2), s=O(N) - Inspired by @vaibhavatul47
17. Letter Combinations of A Phone Number - Medium - Swift Solution - ObjC Solution - Test Cases - t=(3^N), s=O(3^N) - Inspired by @lirensun
18. 4Sum - Medium - Swift Solution - Test Cases - t=O(N^3), s=O(N) - Inspired by @zhaohaoshu
19. Remove Nth Node From End of List - Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @i
20. Valid Parentheses - Easy - Swift Solution - Test Cases - t=O(N), s=O(N) - Inspired by @exodia
21. Merge Two Sorted Lists - Easy - Swift Solution - Test Cases - t=O(max(M,N)), s=O(1) - Inspired by @xiaohui7
22. Generate Parentheses - Medium - Swift Solution - Test Cases - t=O(N^2), s=O(N^2) - Inspired by @klyc0k
23. Merge K Sorted Lists - Hard - Swift Solution - Test Cases - t=O(N*logK), s=O(logK), where where N is the total number of elements, K is the number of lists - Inspired by @wksora
24. Swap Nodes in Pairs - Medium - Swift Solution - Test Cases, t=O(N), s=O(1) - Inspired by @mike3
25. Reverse Nodes in k-Group - Hard - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @sean hyuntaek and @shpolsky
26. Remove Duplicates from Sorted Array - Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @liyangguang1988
27. Remove Element- Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @daxianji007
28. Implement strStr() - Easy - Swift Solution - Test Cases - KMP: t=O(M+N), s=O(N). Brute-force: t=O(M*N), s=O(1) - Brute-force inspired by @shichaotan, KMP inspired by @zhenhai.
29. Divide Two Integers - Medium - Swift Solution - Test Cases - t=O((logN)^2), s=O(1) - Inspired by @lucastan & @ngcl
30. Substring with Concatenation of All Words - Hard - Swift Solution - Test Cases - t=O(N*W), s=O(L*W), where N is the length of the string, W is the length of a word, L is the length of the words list. - Inspired by @ramakanthd92
31. Next Permutation - Medium - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @yuyibestman
32. Longest Valid Parentheses - Hard - Swift Solution - Test Cases - One pass, t=O(N), s=O(N) - Inspired by @jerryrcwong
33. Search in Rotated Sorted Array - Hard - Swift Solution - Test Cases - t=O(logN), s=O(1) - Inspired by @sean hyuntaek
34. Search for a Range - Medium - Swift Solution - Test Cases - t=O(logN), s=O(1)
35. Search Insert Position - Medium - Swift Solution - Test Cases - t=O(logN), s=O(1)
36. Valid Sudoku - Medium - Swift Solution - Test Cases - t=O(1), s=O(1)
37. Sudoku Solver - Hard - Swift Solution - Test Cases - DFS
38. Count and Say - Easy - Swift Solution - Test Cases - t=(2^N), s=O(2^N)
39. Combination Sum - Medium - Swift Solution - Test Cases - t=O(N*M), s=O(M), where N is the length of the candidates array, M is the value of the target integer.
40. Combination Sum II - Medium - Swift Solution - Test Cases - t=O(N*M), s=O(M), where N is the length of the candidates array, M is the value of the target integer.
41. First Missing Positive - Hard - Swift Solution - Test Cases - t=O(N), s=O(1)
42. Trapping Rain Water - Hard - Swift Solution - Test Cases - t=O(N), s=O(1)
43. Multiply Strings - Medium - Swift Solution - Test Cases - t=O(N*M), s=O(N+M)
44. Wildcard Matching - Hard - Swift Solution - Test Cases - t=O(N), s=O(1)
45. Jump Game II - Hard - Swift Solution - Test Cases - t=O(N), s=O(1)
46. Permutations - Medium - Swift Solution - Test Cases - t=O(N!), s=O(N!)
47. Permutations II - Hard - Swift Solution - Test Cases - t=O(N!), s=O(N!)
48. Rotate Image - Medium - Swift Solution - Test Cases - t=O(N*N), s=O(1)
49. Anagrams - Medium - Swift Solution - Test Cases - t=O(N), s=O(N)
50. Pow(x, n) - Medium - Swift Solution - Test Cases - t=O(logN), s=O(logN)
51. N-Queens - Hard - Swift Solution - Test Cases - t=O(N^2), s=O(N^2)
52. N-Queens II - Hard - Swift Solution - Test Cases - t= well it’s complicated…
53. Maximum Subarray - Medium - Swift Solution - Test Cases - t=O(N), s=O(1)
54. Spiral Matrix - Medium - Swift Solution - Test Cases - t=O(N), s=O(N)
55. Jump Game - Medium - Swift Solution - Test Cases - t=O(N), s=O(1)
56. Merge Intervals - Hard - Swift Solution - Test Cases - t=O(N*logN), s=O(N)
57. Insert Interval - Hard - Swift Solution - Test Cases - t=O(N), s=O(N)
58. Length of Last Word - Easy - Swift Solution - Test Cases - t=O(N), s=O(1)
59. Spiral Matrix II - Medium - Swift Solution - Test Cases - t=O(N^2), s=O(N^2)
60. Permutation Sequence - Medium - Swift Solution - Test Cases - t=O(N^2), s=O(N)
61. Rotate List - Medium - Swift Solution - Test Cases - t=O(N), s=O(1)
62. Unique Paths - Medium - Swift Solution - Test Cases - t=O(min(M, N)), s=O(1)
63. Unique Paths II - Medium - Swift Solution - Test Cases - t=O(M*N), s=O(1)
64. Minimum Path Sum - Medium - Swift Solution - Test Cases - t=O(M*N), s=O(1)
65. Valid Number - Hard - Swift Solution - Test Cases - t=O(N), s=O(1)
66. Plus One - Easy - Swift Solution - Test Cases - t=O(N), s=O(1)
67. Add Binary - Easy - Swift Solution - Test Cases - t=O(max(M,N)), s=O(max(M,N))
68. Text Justification - Hard - Swift Solution - Test Cases - t<=O(N*L), s<=O(N*L), where N is the length of the input words array, L is the required justified length
69. Sqrt(x) - Medium - Swift Solution - Test Cases - t=O(logN), s=O(1)
70. Climbing Stairs - Easy - Swift Solution - Test Cases - t=O(N), s=O(1)
71. Simplify Path - Medium - Swift Solution - Test Cases - t=O(N), s=O(N)
72. Edit Distance - Hard - Swift Solution - Test Cases - t=O(M*N), s=O(min(M,N))
73. Set Matrix Zeroes - Medium - Swift Solution - Test Cases - t=O(M*N), s=O(1)
74. Search a 2D Matrix - Medium - Swift Solution - Test Cases - t=O(logN), s=O(1)
75. Sort Colors - Medium - Swift Solution - Test Cases - t=O(N), s=O(1), one pass
76. Minimum Window Substring - Hard - Swift Solution - Test Cases - t=O(N), s=O(N)
77. Combinations - Medium - Swift Solution - Test Cases - t=O(Combination(n, k)+2^(k-1)), s is complicated.
78. Subsets - Medium - Swift Solution - Test Cases - t=O(N*2^N), s=O(n*2^N)
79. Word Search - Medium - Swift Solution - Test Cases - t=O(M*N*L), s=O(L), where L is the length of the word.
80. Remove Duplicates from Sorted Array II - Medium - Swift Solution - Test Cases - t=O(N), s=O(1)
81. Search in Rotated Sorted Array II - Medium - Swift Solution - Test Cases - average t=O(logN), worst case t=O(N), s=O(1)
82. Remove Duplicates from Sorted List II - Medium - Swift Solution - Test Cases - t=O(N), s=O(1)
83. Remove Duplicates from Sorted List - Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @Tao2014
84. Largest Rectangle in Histogram - Hard - Swift Solution - Test Cases - t=O(N), s=O(N) - Inspired by geeksforgeeks
85. Maximal Rectangle - Hard - Swift Solution - Test Cases - t=O(M*N), s=O(min(M,N)) - Inspired by @morrischen2008
86. Partition List - Medium - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @shichaotan
87. Scramble String - Hard - Swift Solution - Test Cases - time and space complexity need further investigation - Inspired by @Charles_p and @dtx0
88. Merge Sorted Array - Easy - Swift Solution - Test Cases - t=O(N), s=O(1) - Inspired by @leetchunhui
89. Gray Code - Medium - Swift Solution - Test Cases - t=O(2^N), s=O(2^N) - Inspired by @mike3
90. Subsets II - Medium - Swift Solution - Test Cases - t=O(2^N), s=O(2^N) - Inspired by @mathsam
91. Decode Ways - Medium - Swift Solution - Test Cases - t=O(N), s=O(N) - Inspired by @manky
92. Reverse Linked List II - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N), s=O(1), One Pass - Inspired by @ardyadipta
93. Restore IP Addresses - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(1), s=O(1) - Inspired by @fiona_mao
94. Binary Tree Inorder Traversal - Medium - Swift Solution - ObjC Solution - Test Cases - Recursion and Iteration t=O(N), average s=O(log(N)), worst s=O(N) - Morris t=O(N), both average & worst s=O(1) - The way we achieved s=O(1) is pretty impressive. Be sure to read the Morris algorithm - Inspired by @lvlolitte and @blue_y
95. Unique Binary Search Trees II - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N^(N-1)), s=I’ve no idea - Inspired by @Jayanta
96. Unique Binary Search Trees - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N^2), s=O(N) - Inspired by @liaison
97. Interleaving String - Hard - Swift Solution - ObjC Solution - Test Cases - t=O(N*M), s=O(N*M) - Inspired by @sherryxmhe
98. Validate Binary Search Tree - Medium - Swift Solution - ObjC Solution - Test Cases - t=O(N), average s=O(logN), worst s=O(N) - Inspired by @jakwings
99. Recover Binary Search Tree - Hard - Swift Solution - ObjC Solution - Test Cases - t=O(N), s=(1) - Inspired by @siyang3
100. Same Tree - Easy - Swift Solution - ObjC Solution - Test Cases - t=O(N), average s=O(logN), worst s=O(N) - Inspired by @JohnWeiGitHub and @scott
101. Symmetric Tree - Easy - Swift Solution - ObjC Solution - Test Cases - t=O(N), best s=O(logN), worst s=O(N) - Inspired by @xuanaux
102. Binary Tree Level Order Traversal - Swift Solution - Test Cases - t=O(N), best s=O(logN), worst s=O(N) - Inspired by @d40a

Optional chaining, closure, subscript, enumeration, generic, extension, access control, automatic reference counting, string, character, nested type, type casting, protocol, xctestcase, xctest, online judge, oj, xcode, cocoa, cocoa touch, foundation, ios, 面试, 算法, 递归, 迭代, 找工作, 手机, 苹果, wwdc, POJ, PKU Online Judge, OJ, data structure, algorithm, algorithms, data structures, 数据结构, 算法与数据结构, interview, interviews, interviewer, interviewers, facebook, google, linkedin, apple, flag, cracking the coding interview, job, recruit, recruiter, recruiting.

### Related Repositories

#### LeetCode-Solutions-in-Swift

LeetCode Solutions in Swift 3.1 ...

#### LeetCode-Swift

LeetCode Solutions in Swift ...

#### SwiftyLeetCode

LeetCode algorithm solutions in Swift ...

#### leetcode

My leetcode solutions written in C++ & Swift. ...

#### SwiftyLeetcode

Not only Leetcode solutions in Swift. ...