LeetCode - Medium

Reminders for problem solutions from https://leetcode.com Code snippets on Swift

112 flashcards · Computer Science · by Bohdan Orlov

1. 2. Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

   Remember: carry over e.g. [5] + [5] = [0, 1] length difference e.g. [5] + [1, 2, 3] = [6, 2, 3] [minor] use dummyNode as convenience to keep reference to rootNode Time/Space complexity: O(max(m,n)) func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? { var dummyNode = ListNode(0) var currentNode = dummyNode var carryOver = 0 var n1 = l1 var n2 = l2 while n1 != nil || n2 != nil || carryOver != 0 { let val1 = n1?.val ?? 0 let val2 = n2?.val ?? 0 let result = val1 + val2 + carryOver c…

2. 3. Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

   Remember: use sliding window concept [leftIdx, rightIdx] move leftIdx if previously seen lftIdx = prevIdx + 1 skip move if not in window prevIdx >= lftIdx Complexity. Time: O(n), Space: O(min(m,n)) (m = charset) func lengthOfLongestSubstring(_ s: String) -> Int { var encounters = [Character: Int]() var length = 0 var lftIdx = 0 for (rgtIndex, char) in s.enumerated() { if let prevIdx = encounters[char], prevIdx >= lftIdx { lftIdx = prevIdx + 1 } let tmpLength = (rgtIndex - lftIdx) + 1 length = m…

3. 5. Longest Palindromic Substring Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

   Remember: expansion of palindromes around possible centres converting to array might improve solution initial range not palindrome rtrn initLeft...initLeft Complexity. Time: O(n2), Space: O(1) Linear solution exists func palindromRange(_ initLeft: String.Index, _ initRight: String.Index, _ s: String) -> ClosedRange<String.Index> { if s[initLeft] != s[initRight] { return initLeft...initLeft } var left = initLeft var right = initRight var nextLeft = left var nextRight = right while s[nextLeft] ==…

4. 6. ZigZag Conversion The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows); Example 2: Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G…

   Remember: Result for Example 2: [0, 6, 12], [1, 5, 7, 11, 13], [2, 4, 8, 10], [3, 9] margin is count of diagonal free rows (2) maxDistance is between characters in margin rows (6) pair describes distance between elements in row: [6], [4, 2], [2, 4], [6] Start with row index, apply pair increments: [0, 6, 6], [0, 4, 2, 4, 2], [0, 2, 4, 2], [0, 6] Every step swaps pair currentPair = currentPair == pair.first ? pair.last! : pair.first! Complexity. Time: O(n), Space: O(1) (additional to result) cla…

5. 8. String to Integer (atoi) Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effe…

   Remember: two problems: #1 find start of number, #2 convert number #1: skip " " if didn't reach number #1: count "+"/"-" unless reached number #1: number reached if reached "+"/"-" or digit [0-9] #2: go left to right #2: number is still valid if can multiply by 10 #2: checking last digit is important if current number equal Int32.max / 10 #2 keep sign because Int32 range = [-231...231 -1] Complexity. Time: O(n), Space: O(n) (Array(str)) func myAtoi(_ str: String) -> Int { let numerals: [Charact…

6. 11. 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 and n is at least 2. Example 1: Input: [2,1] Output: 1

   Remember: Just move the smaller border to the bigger border Decreasing width decreasing area Moving smaller border preserves as much area as possible Complexity. Time: O(n), Space: O(1) func maxArea(_ height: [Int]) -> Int { var l = 0 var r = height.count - 1 var maxArea = 0 while l != r { let w = r - l let h = min(height[l], height[r]) let area = w * h maxArea = max(maxArea, area) if height[l] < height[r] { l += 1 } else { r -= 1 } } return maxArea }

7. 12. Integer to Roman Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four i…

   plain map instead of complex logic use division and reminder to cut digits on left/reminder Complexity. Time: O(n), Space: O(1) func intToRoman(_ num: Int) -> String { let numerals = [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")] var reminder = num var result = "" for (value, symbol) in numerals { result += String(repeating: symbol, count: reminder / value) reminder %= value } return result }

8. 15. 3Sum Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

   for each possible left number (0..<nums.count -2) select next mid = left + 1 and right = s.count - 1 add to result if equal to 0 - left (2sum target) left++ if too small, right-- if too big skip left if left - 1 was the same skip mid/right if in result and next is the same sort time n*log(n) dominated by n2 Complexity. Time: O(n2), Space: O(n) for sorted array func threeSum(_ nums: [Int]) -> [[Int]] { if nums.count < 3 { return [] } var results = [[Int]]() let s = nums.sorted() for left in 0..<…

9. 16. 3Sum Closest Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example: Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

   for each possible left number (0..<nums.count -2) select next mid = left + 1 and right = s.count - 1 add to result if equal to target - left (2sum target) left++ if too small, right-- if too big sort time n*log(n) dominated by n2 Complexity. Time: O(n2), Space: O(n) for sorted array func threeSumClosest(_ nums: [Int], _ target: Int) -> Int { var result: Int! let s = nums.sorted() for left in 0..<s.count - 2 { if left > 0 && s[left - 1] == s[left] { continue } var mid = left + 1 var right = s.co…

10. 17. Letter Combinations of a Phone Number Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example: Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

    recursive solution backtrack and merge in characters for digit Complexity. Time: O(4n), Space: O(n) let map: [Character: [String]] = ["2": ["a", "b", "c"], "3": ["d", "e", "f"], "4": ["g", "h", "i"], "5": ["j", "k", "l"], "6": ["m", "n", "o"], "7": ["p","q", "r", "s"], "8": ["t", "u", "v"], "9": ["w", "x", "y", "z"]] func letterCombinations(_ digits: String) -> [String] { return mergeCharacters(for: digits) } func mergeCharacters(for digits: String) -> [String] { if digits.count == 0 { return […

11. 18. 4Sum Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

    sort slice off the first number skip duplicate first numbers use three sum for the rest Complexity. Time: O(n3), Space: O(n) for sorted array func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] { if nums.count < 4 { return [] } let s = nums.sorted() var results = [[Int]]() for i in 0..<s.count - 3 { if i > 0 && s[i - 1] == s[i] { continue } for sum in threeSum(Array(s.dropFirst(i + 1)), target - s[i]) { results.append([s[i]] + sum) } } return results }

13. 22. Generate Parentheses 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: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]

    Catalan numbers on each step branch into valid options add ( if some left add ) if less than ( when reach 2n backtrack the final string Complexity. Time: O(< nlogn), Space: O(< n2) func generateParenthesis(_ n: Int) -> [String] { return results("", 0, 0, n) } func results(_ str: String, _ open: Int, _ close: Int, _ n: Int) -> [String] { if str.count == n * 2 { return [str] } var result = [String]() if open < n { result += results(str + "(", open + 1, close, n) } if close < open { result += resu…

14. 24. Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. Example: Given 1->2->3->4, you should return the list as 2->1->4->3. Note: Your algorithm should use only constant extra space. You may not modify the values in the list's nodes, only nodes itself may be changed.

    use dummy head swap two elements ahead first element in pari becomes next element Complexity. Time: O(n), Space: O(1) func swapPairs(_ head: ListNode?) -> ListNode? { var dummy = ListNode(-1) dummy.next = head var current = dummy while let n1 = current.next, let n2 = n1.next { n1.next = n2.next n2.next = n1 current.next = n2 current = n1 } return dummy.next }

15. 29. Divide Two Integers Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero. Example 1: Input: dividend = 10, divisor = 3 Output: 3 Example 2: Input: dividend = 7, divisor = -3 Output: -2 Note: Both dividend and divisor will be 32-bit signed integers. The divisor will never be 0. Assume we are dealing with an environment which…

    15 / 2 = 4 + 2 + 1 O(logn): while dividend >= divisor { for n in 0...31 { if dividend - divisor * pow(2, n) res += pow(2, n) dividend -= pow(2, n) } } O(31): instead of growing divisor by 2n times shrink dividend by 2n times starting from n = 31 first divisible shrunk dividend means its time to subtract divisor * 2n we can carry on moving n to 0 because reminder is always getting smaller func divide(_ dividend: Int, _ divisor: Int) -> Int { if dividend == Int32.min && divisor == -1 { return Int…

16. 31. Next Permutation 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 in-place and use only constant extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

    Observe that edge case is: 321 e.g. descending sorted array There is only next permutation if i + 1 > i e.g 12, 123, 132 We find the first index from right where i - 1 < i swap it with the most right bigger than i - 1 number this keeps the right part sorted reversing the right part gives us the least possible premutation Complexity. Time: O(n), Space: O(1) class Solution { func nextPermutation(_ nums: inout [Int]) { for i in stride(from: nums.count - 1, to: 0, by: -1) { let j = i - 1 guard nums…

17. 33. Search in Rotated Sorted Array 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 the order of O(log n). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums = [4,5,6,…

    Easy to understand: Find smallest element with binary search == rotation do binary search taking into account the rotation Complexity. Time: O(nlogn), Space: O(1) Hard to understand: Check if target in left or right sorted parts if it is than "zoom"-in into that part but moving hi or lo to med else target in "other" part, zoom into that part Complexity. Time: O(nlogn), Space: O(1) func search(_ nums: [Int], _ target: Int) -> Int { var lo = 0 var hi = nums.count while lo < hi { let mid = (lo + h…

18. 34. Find First and Last Position of Element in Sorted Array 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: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

    use two binary searches to find boundaries Complexity. Time: O(nlogn), Space: O(1) func searchRange(_ nums: [Int], _ target: Int) -> [Int] { var lo = 0 var hi = nums.count while lo < hi { let med = lo + (hi - lo) / 2 if nums[med] >= target { hi = med } else { lo = med + 1 } } guard lo < nums.count && nums[lo] == target else { return [-1, -1] } var left = lo hi = nums.count - 1 while lo < hi { let med = (lo + (hi - lo) / 2) if nums[med + 1] <= target { lo = med + 1 } else { hi = med } } var righ…

19. 36. Valid Sudoku Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

    Check all rows Check all columns Check all subboxes Complexity. Time: O(nlogn), Space: O(n) where n is size func isValidSudoku(_ board: [[Character]]) -> Bool { for column in 0..<board.count { var encounters = Set<Character>() for row in 0..<board.count { let char = board[row][column] guard char != "." else { continue } if encounters.contains(char) { return false } else { encounters.insert(char) } } } for row in 0..<board.count { var encounters = Set<Character>() for column in 0..<board.count {…

20. 39. Combination Sum Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

    Backtracking through all possibilities Cutting off numbers bigger than the one used Complexity. Time: O(n^t)?? t = target/minValue, Space: O(1) where n is size func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] { var results = [[Int]]() var choices = [Int]() combination(&choices, target, candidates.count, candidates, &results) return results } func combination(_ choices: inout [Int],_ remainder: Int, _ end: Int, _ candidates: [Int],_ results: inout [[Int]]) { if remainder == 0 {…

21. 40. Combination Sum II Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1,…

    Backtracking through all possibilities Cutting off numbers used Complexity. Time: O(n^t)?? t = target/minValue, Space: O(1) where n is size func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] { var results = [[Int]]() var choices = [Int]() combination(&choices, target, candidates.count, candidates.sorted(), &results) return results } func combination(_ choices: inout [Int],_ remainder: Int, _ end: Int, _ candidates: [Int],_ results: inout [[Int]]) { if remainder == 0 { results.a…

22. 43. Multiply Strings Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Note: The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself. You must not use any built-in BigInteger library or co…

    i = n.count - 1, j = m.count - 1 result[i+j] += n[i] + m[j] if result[i+j] > 0 { result[i+j - 1] += result[i+j] / 10 result[i+j] = result[i+j] % 10 } Complexity. Time: O(n*m), Space: O(n+m) func multiply(_ num1: String, _ num2: String) -> String { if num1 == "0" || num2 == "0" { return "0" } let num1 = Array(num1) let num2 = Array(num2) var result = Array(repeating: 0, count: num1.count + num2.count) for (idx, c2) in num2.reversed().enumerated() { for (idx2, c1) in num1.reversed().enumerated()…

23. 46. Permutations Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

    remove numbers one by one recurse into remaining array add number into the first position Complexity. Time: O(n!), Space: O(1) func permute(_ nums: [Int]) -> [[Int]] { if nums.isEmpty { return [[]] } var results = [[Int]]() for (idx, n) in nums.enumerated() { var tmp = nums tmp.remove(at: idx) results += permute(tmp).map { [n] + $0 } } return results }

24. 47. Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]

    skip already encountered numbers rest same as all permutations func permuteUnique(_ nums: [Int]) -> [[Int]] { if nums.isEmpty { return [[]] } var results = [[Int]]() var encounters = Set<Int>() for (idx, n) in nums.enumerated() { guard encounters.insert(n).inserted else { continue } var tmp = nums tmp.remove(at: idx) results += permuteUnique(tmp).map { [n] + $0 } } return results }

25. 48. Rotate Image You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] Example 2: Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6…

    Split into 8 imaginary sectors around diagonals and halfs |1\2|3/4| |8/7|6\5| reverse up and down |8\7|6/5| |1/2|3\4| reverse around leading diagonal |7\8|1/2| |6/5|4\3| * another solution is to calculate using offsets individually up to n/2 func rotate(_ matrix: inout [[Int]]) { matrix.reverse() for i in 0..<matrix.count { for j in i..<matrix.count { (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]) } } } Complexity. Time: O(n2), Space: O(1)

26. 49. Group Anagrams Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter.

    make key by sorting characters of a letter store in Dictionary Complexity. Time: O(nklogk) k - max size of a word, Space: O(1) func groupAnagrams(_ strs: [String]) -> [[String]] { var results = [String: [String]]() for str in strs { let key = String(str.sorted()) var anagramsForKey = results[key] ?? [String]() anagramsForKey.append(str) results[key] = anagramsForKey } return Array(results.values) }

27. 50. Pow(x, n) Implement pow(x, n), which calculates x raised to the power n (xn). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Note: -100.0 < x < 100.0

    Notice that 24 == 42 e.g xn = (x2)n/2 if x is odd than just result *= x and n = n - 1 check if x is odd by looking at the first bit func myPow(_ x: Double, _ n: Int) -> Double { if n > 0 { return fastPow(x, UInt(n)) } else { return fastPow(1 / x, UInt(-n)) } } func fastPow(_ x: Double, _ n: UInt) -> Double { var r: Double = 1 var x = x var n = n while n > 0 { if firstBit(n) == 1 { r *= x n -= 1 } x *= x n /= 2 } return r } func firstBit(_ n: UInt) -> UInt { return (~1 & n) ^ n }

28. 54. Spiral Matrix Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Example 1: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5] Example 2: Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] Output: [1,2,3,4,8,12,11,10,9,5,6,7]

    we can use notion of level for square matrix square matrix has min(n,m) / 2 levels for non square matrix copy remaining row/column if needed Complexity. Time: O(n*m), Space: O(1) func spiralOrder(_ matrix: [[Int]]) -> [Int] { var result = [Int]() let h = matrix.count if h == 0 { return result } let w = matrix[0].count for lvl in 0..<(min(w,h) / 2) { let hiW = w - 1 - lvl let hiH = h - 1 - lvl for t in lvl..<hiW { result += [matrix[lvl][t]] } for r in lvl..<hiH { result += [matrix[r][hiW]] } for…

29. 55. Jump Game Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length i…

    go left to right mark maximum reachable number if it is over end than return true else if we reached maximum reachable number and it is 0 return false Complexity. Time: O(n), Space: O(1) func canJump(_ nums: [Int]) -> Bool { var reachablePos = nums[0] for (pos, jump) in nums.enumerated() { guard pos <= reachablePos else { return false } reachablePos = max(reachablePos, pos + jump) } return true }

30. 56. Merge Intervals Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

    sort by start time take first interval iterate all intervals and merge into current if overlaps if don't overlap add current interval into results and select new current interval don't forged to add last current interval into results Complexity. Time: O(nlogn), Space: O(1) class Solution { func merge(_ intervals: [Interval]) -> [Interval] { if intervals.isEmpty { return [] } var intervals = intervals.sorted { $0.start < $1.start } var result = [Interval]() var currentInterval = intervals.first!…

31. 59. Spiral Matrix II Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

    lo = 0 and hi = n - 1 boundary while lo < hi use i to fill in elements on each side then lo +=1, hi -=1 if lo == hithen fill center Complexity. Time: O(n), Space: O(1) func generateMatrix(_ n: Int) -> [[Int]] { var result = Array(repeating: Array(repeating: 0, count: n), count: n) var i = 1 var lo = 0 var hi = n - 1 while lo < hi { for t in lo..<hi { result[lo][t] = i i += 1 } for r in lo..<hi { result[r][hi] = i i += 1 } for b in stride(from: hi, to: lo, by: -1) { result[hi][b] = i i += 1 } fo…

32. 60. Permutation Sequence The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive. Given k will be between 1 and n! inclusive. Example 1: Input: n = 3, k = 3 Output: "213" Example 2: Input: n = 4, k = 9 Output: "2314"

    n=4, k=14 1,2,3,4, n! = 24 (14 - 1) / 6 = 2 remove item at index 2 and add to result 3 {1,2,4} n! = 6 n = 3, k = k - 2 * n! = 2 ... Complexity. Time: O(n), Space: O(n) func getPermutation(_ n: Int, _ k: Int) -> String { var sum = 1 var factorial = Array(repeating: 0, count:n) for i in 1...n { factorial[i - 1] = sum sum *= i } var numbers = Array(1...n) var k = k - 1 var result = [Int]() while !numbers.isEmpty { let combinationsLeft = factorial[numbers.count - 1] let idx = k / combinationsLeft r…

33. 61. Rotate List Given a linked list, rotate the list to the right by k places, where k is non-negative. Example 1: Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL Example 2: Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right: 0->1->2->NULL rotate 4…

    find length to get real k delay second node pointer by k swap nodes appropriately Complexity. Time: O(n), Space: O(1) func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? { var currentNode = head var length = head != nil ? 1 : 0 while let next = currentNode?.next { length += 1 currentNode = next } let realK = k % length var delay = realK var delayedNode = head currentNode = head while let next = currentNode?.next { currentNode = next if delay <= 0 { delayedNode = delayedNode?.next } delay…

34. 62. Unique Paths 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 7 x 3 grid. How many possible unique paths are there? Note: m and n will be at most 100. Example 1: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left…

    r[i][j] = r[i - 1][j] + r[i][j-1] for m=3 n=3 1 1 1 1 2 3 1 3 6 Complexity. Time: O(n*m), Space: O(n*m) func uniquePaths(_ m: Int, _ n: Int) -> Int { var results = Array(repeating: Array(repeating:1, count:n), count:m) for row in 1..<m { for column in 1..<n { results[row][column] = results[row - 1][column] + results[row][column - 1] } } return results[m - 1][n - 1] }

35. 63. Unique Paths II 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). Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. Note: m and n will be at most 100. Example…

    Input: [ [0,1,0], [0,1,0], [0,0,0] ] r[i][j] = r[i - 1][j] + r[i][j-1] for m=3 n=3 mark obstructed tiles with 0 1 0 0 1 0 0 1 1 1 Complexity. Time: O(n*m), Space: O(n*m) func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int { let m = obstacleGrid.count let n = obstacleGrid[0].count var results = Array(repeating: Array(repeating:0, count:n), count:m) results[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0 for row in 0..<m { for column in 0..<n { if obstacleGrid[row][column] == 1 { results[row][c…

36. 64. Minimum Path Sum 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. Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.

    r[i][j] =g[i][j] +min(r[i - 1][j], r[i][j-1]) Complexity. Time: O(n*m), Space: O(n*m) func minPathSum(_ grid: [[Int]]) -> Int { let m = grid.count let n = grid[0].count var result = grid for y in 1..<n { result[0][y] += result[0][y - 1] } for x in 1..<m { result[x][0] += result[x - 1][0] } for x in 1..<m { for y in 1..<n { result[x][y] += min(result[x - 1][y], result[x][y - 1]) } } return result[m - 1][n - 1] }

37. 71. Simplify Path 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".

    use stack to keep track of components ignore ./ pop if not empty when ../ Complexity. Time: O(n), Space: O(1) additional func simplifyPath(_ path: String) -> String { var components = [String]() for component in path.components(separatedBy: "/") { guard component.count > 0 else { continue } if component == "." { continue } if component == ".." { guard !components.isEmpty else { continue } components.removeLast() continue } components.append(component) } return "/" + components.joined(separator:…

38. 73. Set Matrix Zeroes Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place. Example 1: Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ] Example 2: Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ] Follow up: 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?

    Phase 1. Use first row and column to keep track if a particular row/column is 0. [0][0]can't keep both row and column so we column0 result it in separate variable Phase 2. Zero all elements if first element in row/column is a zero. Do this in reverse because we have to zero first row/column last. col0 = 1 Phase 1: [1,0,1], [0,0,1], [1,1,1] Phase 2: [1,0,1], [0,0,1], [1,1,1] Complexity. Time: O(n), Space: O(1) additional func setZeroes(_ matrix: inout [[Int]]) { let m = matrix.count let n = matr…

39. 74. Search a 2D Matrix 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. Example 1: Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true Example 2: Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 Output: false

    Solution 1 Use binary search find row first looking at the first element only find target in the row Complexity. Time: O(logn), Space: O(1) additional func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool { if matrix.isEmpty { return false } if matrix[0].isEmpty { return false } let row = searchRow(matrix, target, 0, matrix.count) return search(row, target, 0, row.count) } func searchRow(_ matrix: [[Int]], _ target: Int, _ lo: Int, _ hi: Int) -> [Int] { let midIdx = (hi + lo) / 2 let mid…

40. 75. Sort Colors Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for this problem. Example: Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Follow up: A rather straight forward solution is a two-pass algorithm using…

    iterate through the array with mid pointer if mid == 2 swap it with the right boundary element (marked with hi pointer) in this case mid remains the same, because the swapped element could be 0 or 1 if mid == 0 swap it with the left boundary element (marked with lo pointer) and increase mid note swapped element can't be 2 because 2 was taken care of in the if statement above if mid == 1, it is in the right position, so simply increase mid proceed untill mid reaches hi which means that area of 1…

41. 77. Combinations Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. Example: Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

    backtracking solution by cutting off used number and slot Complexity. Time: O(nk), Space: O(n) additional func combine(_ n: Int, _ k: Int) -> [[Int]] { var results = [[Int]]() combine(&results, [], n, k) return results } func combine(_ results: inout [[Int]], _ combination: [Int], _ n: Int, _ k: Int) { if k == 0 { results.append(combination) return } var combination = combination for i in stride(from: n, to: 0, by: -1) { combination.append(i) combine(&results, combination, i - 1, k - 1) combina…

42. 78. Subsets Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

    Backtracking adding a number, but removing used number Complexity. Time: O(2n), Space: O(1) additional func subsets(_ nums: [Int]) -> [[Int]] { var results = [[Int]]() premutate(&results, [], nums, 0) return results } func premutate(_ results: inout [[Int]], _ premutation: [Int], _ nums: [Int], _ start: Int) { results.append(premutation) var premutation = premutation for i in start..<nums.count { premutation.append(nums[i]) premutate(&results, premutation, nums, i + 1) premutation.removeLast()…

43. 79. Word Search 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'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE", return true. Given word = "ABCB", return false.

    Do DFS from each element n board elements count k word char count Complexity. Time: O(n23k), Space: O(n) additional func exist(_ board: [[Character]], _ word: String) -> Bool { var visited = board.map { $0.map { _ in false } } let word = Array(word) for i in 0..<board.count { for j in 0..<board[0].count { if find(&visited, board, word, 0, i, j) { return true } } } return false } func find(_ visited: inout [[Bool]], _ board: [[Character]], _ word: [Character], _ charIdx: Int, _ i: Int, _ j: Int)…

44. 80. Remove Duplicates from Sorted Array II Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example 1: Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn't matter what you leave beyond the retu…

    just look at prev prev element remove current if the same Complexity. Time: O(n), Space: O(1) additional func removeDuplicates(_ nums: inout [Int]) -> Int { var i = 2 while i < nums.count { if nums[i - 2] == nums[i] { nums.remove(at: i) } else { i += 1 } } return nums.count }

45. 81. Search in Rotated Sorted Array II 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 the order of O(log n). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums = [4,5…

    skip left right elements if the same because they prevent from understanding in which case we are Complexity. Time: O(average logn) worst n, Space: O(1) additional func search(_ nums: [Int], _ target: Int) -> Bool { return rotatedBinarySearch(nums, target, 0, nums.count - 1) } func rotatedBinarySearch(_ nums: [Int], _ target: Int, _ lo: Int, _ hi: Int) -> Bool { let mid = (lo + hi) / 2 if lo > hi { return false } if nums[lo] == target || nums[mid] == target || nums[hi] == target { return true }…

46. 82. Remove Duplicates from Sorted List II Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2: Input: 1->1->1->2->3 Output: 2->3

    Solution 1. Count occurrences of node decide to skip nodes or not. Complexity. Time: O(n), Space: O(1) additional func deleteDuplicates(_ head: ListNode?) -> ListNode? { let dummy = ListNode(-1) dummy.next = head var current: ListNode? = dummy while let node = current, let next = node.next { var runner = node.next var count = 0 while next.val == runner?.val { count += 1 runner = runner?.next } if count == 1 { current = node.next } else { current?.next = runner } } return dummy.next } Solution 2…

47. 86. Partition List Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. Example: Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5

    Maintain two lists connect them in the end Complexity. Time: O(n), Space: O(1) additional func partition(_ head: ListNode?, _ x: Int) -> ListNode? { let dummyLo = ListNode(-1) var loEnd = dummyLo let dummyHi = ListNode(-1) var hiEnd = dummyHi var current = head while let node = current { if node.val < x { loEnd.next = node loEnd = node } else { hiEnd.next = node hiEnd = node } current = node.next } loEnd.next = dummyHi.next return dummyLo.next }

48. 89. Gray Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. Example 1: Input: 2 Output: [0,1,3,2] Explanation: 00 - 0 01 - 1 11 - 3 10 - 2 For a given n, a gray code sequence may not be uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence. 00 - 0 10 - 2 11 - 3 01 - 1 Exampl…

    Solution 1. Backtracking. Complexity. Time: O(2n), Space: O(1) additional func grayCode(_ n: Int) -> [Int] { var results = [Int]() var bits = Array(repeating: 0, count: n) backtrack(&results, &bits, n) return results } func backtrack(_ results: inout [Int], _ bits: inout [Int], _ n: Int) { if n == 0 { var result = 0 for (idx, bit) in bits.enumerated() { result += (bit << idx) } results.append(result) return } backtrack(&results, &bits, n - 1) bits[n - 1] ^= 1 backtrack(&results, &bits, n - 1) }…

49. 90. Subsets II 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], [] ]

    sort numbers to keep duplicates next to each other construct result by cutting of numbers of num Complexity. Time: O(kn) k = max duplicates, Space: O(1) additional func subsetsWithDup(_ nums: [Int]) -> [[Int]] { var results = [[Int]]() subsets(&results, nums.sorted(), []) return results } func subsets(_ results: inout [[Int]], _ nums: [Int], _ choice: [Int]) { results.append(choice) var nums = nums while !nums.isEmpty { let el = nums.removeFirst() subsets(&results, nums, choice + [el]) while nu…

50. 91. Decode Ways A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

    For every ith digit, starting from ith index, either single digit number is valid (>0) or two digit number is valid (<=26), so no of ways dp[i]= ways for dp[i+1] (if ith single digit is valid, 0 otherwise) + dp[i+2] (if starting from i index 2 &1 digit numbers are valid, 0 otherwise) dp[i] = dp[i+1] + dp[i+2]; func numDecodings(_ s: String) -> Int { if s.isEmpty { return 1 } let n = s.count var ways = Array(repeating: 0, count: n + 1) let s = Array(s) ways[n] = 1 ways[n - 1] = s[n - 1] == "0" ?…

51. 93. Restore IP Addresses Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]

    Use backtracking to construct only valid instances. Complexity. Time: O(34), Space: O(4) additional space func restoreIpAddresses(_ s: String) -> [String] { var results = [String]() addAddresses(&results, Array(s), [], 4, 0) return results } func addAddresses(_ results: inout [String], _ s: [Character], _ r: [[Character]], _ partsLeft: Int, _ start: Int) { if let lastPart = r.last { guard Int(String(lastPart))! <= 255 else { return } if lastPart.count > 1 && lastPart[0] == "0"{ return } } if pa…

52. 94. Binary Tree Inorder Traversal Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively?

    Recursive: func inorderTraversal(_ root: TreeNode?) -> [Int] { guard let node = root else { return [] } return inorderTraversal(node.left) + [node.val] + inorderTraversal(node.right) } Iterative: func inorderTraversal(_ root: TreeNode?) -> [Int] { var results = [Int]() guard let node = root else { return [] } var stack = [TreeNode]() var cur: TreeNode? = node while cur != nil || !stack.isEmpty { while cur != nil { if let left = cur { stack.append(left) } cur = cur?.left } let valNode = stack.re…

53. 96. Unique Binary Search Trees Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

    Catalan numbers: func numTrees(_ n: Int) -> Int { var answer = 1 var i = 1 while i <= n { answer = answer * (i + n) / i i += 1 } return answer / i }

54. 341. Flatten Nested List Iterator Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Example 1: Input: [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1]. Example 2: Input: [1,[4,[6]]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns f…

    Complexity. Time: O(n), Space: O(n) additional space class Iterator { private var stack: [NestedInteger] init(integer: NestedInteger) { self.stack = [integer] } func hasNext() -> Bool { guard let last = stack.last else { return false } if last.isInteger() { return true } self.stack.removeLast() self.stack.append(contentsOf: last.getList().reversed()) return hasNext() } func next() -> Int { return self.stack.removeLast().getInteger() } }

55. 449. Serialize and Deserialize BST Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary…

    preorder into array iterate array and create value if valid. Complexity. Time: O(n), Space: O(n) additional space extension TreeNode { func encode() -> String { var array: [String] = [] encode(&array, self) return array.joined(separator: ",") } private func encode(_ array: inout [String], _ node:TreeNode?) { guard let node = node else { return } array.append(String(node.val)) encode(&array, node.left) encode(&array, node.right) } static func decode(_ string: String) -> TreeNode? { let array = s…

56. 647. Palindromic Substrings Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Note: The input string length won't exceed 1000.

    Complexity. Time: O(n^2), Space: O(n) due to Array(s) class Solution { func countSubstrings(_ s: String) -> Int { let chars:[Character] = Array(s) var total = 0 for i in 0..<chars.count { total += expand(chars, i, i) total += expand(chars, i, i + 1) } return total } func expand(_ chars:[Character], _ lo: Int, _ hi: Int) -> Int { var lo = lo var hi = hi var local = 0 while lo >= 0 && hi < chars.count { if chars[lo] != chars[hi] { return local } local += 1 lo -= 1 hi += 1 } return local } }

57. 322. Coin Change You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 Note: You may assume that you have an infinite number of each kind of coin.

    Complexity. Time: O(n*amount), Space: O(amount) class Solution { func coinChange(_ coins: [Int], _ amount: Int) -> Int { if amount == 0 { return 0 } var dp = Array(repeating: amount + 1, count: amount + 1) dp[0] = 0 for a in (1...amount) { for coin in coins { guard a >= coin else { continue } dp[a] = min(dp[a], dp[a - coin] + 1) } } return dp[amount] <= amount ? dp[amount] : -1 } }

58. 518. Coin Change 2 You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. Note: You can assume that 0 <= amount <= 5000 1 <= coin <= 5000 the number of coins is less than 500 the answer is guaranteed to fit into signed 32-bit integer Example 1: Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to ma…

    This is a classic knapsack problem. Complexity. Time: O(n*amount), Space: O(n*amount) func change(_ amount: Int, _ coins: [Int]) -> Int { var dp = Array(repeating: Array(repeating: 0, count: amount + 1), count: coins.count + 1) dp[0][0] = 1 for cIdx in stride(from: 1, to: coins.count + 1, by: 1) { dp[cIdx][0] = 1 for total in stride(from: 1, to: amount + 1, by: 1) { let coin = coins[cIdx - 1] let prev = (total >= coin) ? dp[cIdx][total - coin] : 0 dp[cIdx][total] = dp[cIdx - 1][total] + prev }…

59. 210. Course Schedule II There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an em…

    DFS, use post order to guaranty that all dependency added first to the result list. Temporary marks allows to detect cycles. Complexity. Time: O(n+e), Space: O(n) class Solution { var unmarked = Set<Int>() var markedPerm = Set<Int>() var markedTemp = Set<Int>() var order = [Int]() var adjList = [Int: [Int]]() func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] { unmarked = Set(Array(0..<numCourses)) for edge in prerequisites { adjList[edge[0]] = (adjList[edge[0]] ?? []) + [edge…

60. 829. Consecutive Numbers Sum Hard Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers? Example 1: Input: 5 Output: 2 Explanation: 5 = 5 = 2 + 3 Example 2: Input: 9 Output: 3 Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4 Example 3: Input: 15 Output: 4 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 Note: 1 <= N <= 10 ^ 9.

    sum of sequence 1...n: 1 + 2 + ... n = (n * (n - 1)) / 2 next sequence 2...n + 1: 2 + 3 + ... n + n + (n + 1) same as: 1 + 2 + ... n + n so next: 1 + 2 + ... n + n + n A sequence forms N if: (N - (1 + 2 + ... n)) % n = 0 Complexity. Time: O(sqrt(n)), Space: O(1) func consecutiveNumbersSum(_ N: Int) -> Int { var answer = 1 for n in stride(from: 2, to: Int(sqrt(Double(2 * N))) + 1, by: 1) { answer += (N - (n * (n - 1) / 2)) % n == 0 ? 1 : 0 } return answer }

61. 522. Longest Uncommon Subsequence II Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be anysubsequence of the other strings. A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empt…

    We are looking for longest string which is not subsequence of any other. Complexity. Time: O(n*n), Space: O(1) func findLUSlength(_ strs: [String]) -> Int { let sorted = strs.sorted { $0.count > $1.count } for (idx, str) in sorted.enumerated() { var subsequence = false for (idx2, other) in sorted.enumerated() { if idx == idx2 { continue } if isSubSequence(str, other) { subsequence = true print(str, other) break } } if !subsequence { return str.count } } return -1 } func isSubSequence(_ s1: Stri…

62. 900. RLE Iterator Write an iterator that iterates through a run-length encoded sequence. The iterator is initialized by RLEIterator(int[] A), where A is a run-length encoding of some sequence. More specifically, for all even i, A[i]tells us the number of times that the non-negative integer value A[i+1] is repeated in the sequence. The iterator supports one function: next(int n), which exhausts the next n elements (n >= 1) and returns the last element exhausted in this way. If there is no elemen…

    Complexity. Time: O(n), Space: O(1) class RLEIterator { let a: [Int] var idx = 0 var left: Int init(_ A: [Int]) { a = A left = A[0] } func next(_ n: Int) -> Int { if idx > a.count - 2 && left < n { return -1 } if left < n { let remainder = n - left idx += 2 left = idx < a.count ? a[idx] : 0 return next(remainder) } left -= n return a[idx + 1] } }

63. 417. Pacific Atlantic Water Flow Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower. Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean. Note: The order of…

    BFS from both oceans cells visited by both oceans is the result Complexity. Time: O(m*n), Space: O(m*n) func pacificAtlantic(_ matrix: [[Int]]) -> [[Int]] { let m = matrix.count if m == 0 { return [] } let n = matrix[m - 1].count if n == 0 { return [] } var pVisited = Array(repeating: Array(repeating: false, count: n), count: m) let rangeM = (0..<m) let rangeN = (0..<n) let pVertical: [(Int, Int)] = Array(rangeM).map { pVisited[$0][0] = true return ($0, 0) } let pHorizontal: [(Int, Int)] = Arra…

64. 200. Number of Islands Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: 11110 11010 11000 00000 Output: 1 Example 2: Input: 11000 11000 00100 00011 Output: 3

    DFS to find connected components Also we can use Union-Find. Complexity. Time: O(m*n), Space: O(m*n) func numIslands(_ grid: [[Character]]) -> Int { let m = grid.count let n = m > 0 ? grid[0].count : 0 var components = Array(repeating: Array(repeating: -1, count: n), count: m) var currentMark = 0 for i in (0..<m) { for j in (0..<n) { dfs((i,j), grid, (m - 1, n - 1), currentMark, &components) if components[i][j] == currentMark { currentMark += 1 } } } return currentMark } let dir = [(1, 0), (0,…

65. 20. Valid Parentheses Easy Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1: Input: "()" Output: true Example 2: Input: "()[]{}" Output: true Example 3: Input: "(]" Output: false Example 4: Input: "([)]" Output: false Example 5:…

    stack to keep track of open brackets a closed bracket "cancels" open, only if it matches Complexity. Time: O(n), Space: O(n) func isValid(_ s: String) -> Bool { var stack = [Character]() for c in Array(s) { switch c { case "{", "(", "[": stack.append(reversed(c)) case "}", ")", "]": if stack.isEmpty { return false } let last = stack.removeLast() if last != c { return false } default: fatalError() } } return stack.isEmpty } func reversed(_ c: Character) -> Character { switch c { case "{": return…

66. 253. Meeting Rooms II Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. Example 1: Input: [[0, 30],[5, 10],[15, 20]] Output: 2 Example 2: Input: [[7,10],[2,4]] Output: 1

    sort starts and ends separately this allows us to interate though starts and keep track of first end if next start happens before tracked end we need another room otherwise we track next end (next room to finish) Complexity. Time: O(nlog), Space: O(n) func minMeetingRooms(_ intervals: [Interval]) -> Int { var starts = intervals.map { $0.start } var ends = intervals.map { $0.end } starts.sort() ends.sort() var endIdx = 0 var rooms = 0 for start in starts { if start < ends[endIdx] { rooms += 1 }…

67. 139. Word Break Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "lee…

    iterate over each i position of s iterate over all words check if if could get there dp[start] == true check if this word matches letters s[range] == word if both true then i is reachable dp[i] Complexity. Time: O(ls*cd*avgLd), Space: O(ls) func wordBreak(_ s: String, _ wordDict: [String]) -> Bool { var dp = Array(repeating: false, count: s.count + 1) dp[0] = true for i in 1...s.count { for word in wordDict { let start = i - word.count guard start >= 0 && dp[start] == true else { continue } let…

68. 289. Game of Life According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by…

    use second bit to store next state Complexity. Time: O(m*n), Space: O(1) var dir = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (-1, 1), (1, -1)] func gameOfLife(_ board: inout [[Int]]) { var newBoard = board for i in 0..<board.count { for j in 0..<board[i].count { var alive = 0 for (di, dj) in dir { let rI = i + di let rJ = j + dj if rI < 0 || rI >= board.count || rJ < 0 || rJ >= board[i].count { continue } alive += board[rI][rJ] & 1 } if board[i][j] == 1 && (alive == 2 || alive == 3)…

69. 146. LRU Cache Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in O…

    dictionary and double linked list Complexity. Time: O(1), Space: O(n) class LRUCache { var head = Node() var tail = Node() var cache = [Int: Node]() let capacity: Int init(_ capacity: Int) { self.capacity = capacity head.next = tail tail.prev = head } func get(_ key: Int) -> Int { if let node = cache[key], let val = node.val { moveToHead(node) return val } return -1 } func put(_ key: Int, _ value: Int) { let node = cache[key] ?? Node() node.key = key node.val = value if cache[key] == nil { add(…

70. 103. Binary Tree Zigzag Level Order Traversal Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]

    Traverse only "old" part of the queue to separate levels simply reverse result of level based on level index Complexity. Time: O(n), Space: O(2logn) additional space func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] { guard let root = root else { return [] } var result = [[Int]]() var queue = [root] var reverseOrder = false while !queue.isEmpty { var level = [Int]() for _ in 0..<queue.count { let node = queue.removeFirst() level.append(node.val) if let left = node.left { queue.append(left) }…

71. 239. Sliding Window Maximum Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3]…

    push max elements to edges of sliding window select max from both sides Complexity. Time: O(n), Space: O(n) additional space func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] { if nums.isEmpty { return [] } var result = [Int]() var left = Array(repeating: Int.min, count: nums.count) var right = Array(repeating: Int.min, count: nums.count) for i in 0..<nums.count { left[i] = i % k == 0 ? nums[i] : max(nums[i], left[i - 1]) let j = nums.count - 1 - i right[j] = (j % k == 0 || i == 0) ? nums…

72. 138. Copy List with Random Pointer A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

    Linear space: just save pointers in a dictionary Java: after main copy, interlink original and copy list both ways: use original->next to link to copy node use copy->random to link to original node iterate copy list, then copy->random = copy->random->random->next Complexity. Time: O(n), Space: O(1) additional space RandomListNode iter = head, next; // First round: make copy of each node, // and link them together side-by-side in a single list. while (iter != null) { next = iter.next; RandomList…

73. 361. Bomb Enemy Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb. The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed. Note: You can only put the bomb at an empty cell. Example: Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]] Output: 3 Explanation: For the given grid, 0 E 0 0 E 0 W E 0…

    "spread" enemies count by scanning left to right and right to left then same for columns top to bottom, bottom to top. then find cell with max score. Complexity. Time: O(m+n), Space: O(m*n) additional space func maxKilledEnemies(_ grid: [[Character]]) -> Int { let m = grid.count let n = m > 0 ? grid[0].count : 0 var score = Array(repeating: Array(repeating: 0, count:n), count: m) var result = 0 for i in stride(from: 0, to: m, by: 1) { var lo = 0 var hi = 0 for j in stride(from: 0, to: n, by: 1)…

74. 653. Two Sum IV - Input is a BST Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True Example 2: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False

    inorder lo and inorder reverse hiiterators if sum is too small lo.next if sum is too big hi.next Complexity. Time: O(n), Space: O(logn) class Iterator: IteratorProtocol { var stack = [TreeNode]() let reverse: Bool init(_ root: TreeNode, _ reverse: Bool) { self.reverse = reverse append(of: root) } func next() -> TreeNode? { guard !stack.isEmpty else { return nil } let last = stack.removeLast() append(of: reverse ? last.left : last.right) return last } func append(of node: TreeNode?) { var node =…

75. 549. Binary Tree Longest Consecutive Sequence II Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree. Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order. Example 1: Input: 1 / \ 2 3 Output: 2 Explanation: The longest consecutive path i…

    post order dfs keep track of dec and inc sequences base case dec = 1 inc = 1 each "step up" chose best dec and inc resulthas to be tracked separately because progress is reset when sequence is reset Complexity. Time: O(n), Space: O(logn) func longestConsecutive(_ root: TreeNode?) -> Int { var result = 0 _ = dfs(root, &result) return result } func dfs(_ root: TreeNode?, _ result: inout Int) -> (Int, Int) { guard let root = root else { return (0,0) } var leftS = dfs(root.left, &result) var rightS…

76. 277. Find the Celebrity Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or…

    Complexity. Time: O(n*m), Space: O(1) func findCelebrity(_ know2d: [[Int]]) -> Int { let m = know2d.count let n = m == 0 ? 0 : know2d[0].count for i in stride(from: 0, to: n, by: 1) { var everyoneKnows = true for j in stride(from: 0, to: m, by: 1) { if j != i && know2d[j][i] == 0 { everyoneKnows = false break } } guard everyoneKnows else { continue } var knowsNoone = true for j in stride(from: 0, to: n, by: 1) { if j != i && know2d[i][j] != 0 { knowsNoone = false break } } guard knowsNoone else…

77. 859. Buddy Strings Easy Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B. Example 1: Input: A = "ab", B = "ba" Output: true Example 2: Input: A = "ab", B = "ab" Output: false Example 3: Input: A = "aa", B = "aa" Output: true Example 4: Input: A = "aaaaaaabc", B = "aaaaaaacb" Output: true Example 5: Input: A = "", B = "aa" Output: false Note: 0 <= A.length <= 20000 0 <= B.length <= 20000 A and B consist only of lo…

    Complexity. Time: O(n), Space: O(1) func buddyStrings(_ A: String, _ B: String) -> Bool { if A.count != B.count { return false} var wrongIndexes = [Int]() var characters = [Character : Int]() for (idx, (a,b)) in zip(A,B).enumerated() { characters[a, default: 0] += 1 if a != b { wrongIndexes.append(idx) } if wrongIndexes.count > 2 { return false } } if wrongIndexes.count == 2 { let first = wrongIndexes.first! let last = wrongIndexes.last! if Array(A)[first] == Array(B)[last] && Array(A)[last] ==…

78. 402. Remove K Digits Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Note: The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove t…

    stack characters from left to right when encounter smaller character pop all smaller characters. Complexity. Time: O(n), Space: O(n) func removeKdigits(_ num: String, _ k: Int) -> String { var k = k var stack = [Character]() for c in num { while let last = stack.last, last > c , k > 0 { stack.removeLast() k -= 1 } if stack.isEmpty && c == "0" { continue } stack.append(c) } stack.removeLast(min(k, stack.count)) return stack.isEmpty ? "0" : String(stack) }

79. 264. Ugly Number II Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note: 1 is typically treated as an ugly number. n does not exceed 1690.

    Since all numbers are constructed by * by 2, 3 or 6 we do so by finding smaller number first. its important to keep track of used numbers to avoid duplication. Complexity. Time: O(n), Space: O(n) func nthUglyNumber(_ n: Int) -> Int { var u = Array(repeating: 0, count: n) u[0] = 1 var p1 = 0 var p2 = 0 var p3 = 0 for i in 1..<n { u[i] = min(u[p1] * 2, u[p2] * 3, u[p3] * 5) if u[i] == u[p1] * 2 { p1 += 1 } if u[i] == u[p2] * 3 { p2 += 1 } if u[i] == u[p3] * 5 { p3 += 1 } } return u[n - 1] }

80. 792. Number of Matching Subsequences Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S. Example : Input: S = "abcde" words = ["a", "bb", "acd", "ace"] Output: 3 Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace". Note: All words in words and S will only consists of lowercase letters. The length of S will be in the range of [1, 50000]. The length of words will be in the range of [1, 5000]. The length of…

    Keep track of progress in each word. To avoid going through all words keep words by "waiting" character in a dictionary. Complexity. Time: O(n), Space: O(w) func numMatchingSubseq(_ S: String, _ words: [String]) -> Int { var waiting = [Character: [IndexingIterator<String>]]() var result = 0 words.forEach { var itr = $0.makeIterator() waiting[itr.next()!, default: []] += [itr] } for c in S { guard let itrs = waiting[c] else { continue } waiting[c] = [] for itr in itrs { var itr = itr if let next…

81. 328. Odd Even Linked List Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example 1: Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULL Example 2: Input: 2->1->3->5->6->4->7->NULL Output: 2->3->6->7->1->5->4->NULL Note: The relative order inside both the even…

    Complexity. Time: O(n), Space: O(1) func oddEvenList(_ head: ListNode?) -> ListNode? { guard let first = head else { return nil } guard let second = first.next else { return first } var oddHead = first var oddTail = first var evenHead = second var evenTail = second var current = second.next var even = false while let node = current { if even { evenTail.next = node evenTail = node } else { oddTail.next = node oddTail = node } even = !even current = node.next print(oddTail.val, evenTail.val) } ev…

82. 257. Binary Tree Paths Easy Given a binary tree, return all root-to-leaf paths. Note: A leaf is a node with no children. Example: Input: 1 / \ 2 3 \ 5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3

    Complexity. Time: O(n), Space: O(1) func binaryTreePaths(_ root: TreeNode?) -> [String] { var results = [String]() dfs(root, [], &results) return results } func dfs(_ node: TreeNode?, _ path: [Int], _ results: inout [String]) { guard let node = node else { return } if node.left == nil && node.right == nil { var path = path + [node.val] results += [path.map(String.init).joined(separator: "->")] return } dfs(node.left, path + [node.val], &results) dfs(node.right, path + [node.val], &results) }

83. 268. Missing Number Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. Example 1: Input: [3,0,1] Output: 2 Example 2: Input: [9,6,4,2,3,5,7,0,1] Output: 8 Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

    a ^ b ^ b = a Complexity. Time: O(n), Space: O(1) func missingNumber(_ nums: [Int]) -> Int { var res = nums.count for (i, n) in nums.enumerated() { res = res ^ i ^ nums[i] // a ^ b ^ b = a } return res }

84. 377. Combination Sum IV Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. Example: nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7. Follow up: What if negative numbers are allowed in the given array? How does it change the p…

    Complexity. Time: O(n*target), Space: O(target) func combinationSum4(_ nums: [Int], _ target: Int) -> Int { var dp = Array(repeating: Double(0), count: target + 1) dp[0] = 1 for i in 1...target { for n in nums { guard i - n >= 0 else { continue } dp[i] += dp[i - n] } } return Int(dp[target]) }

85. 236. Lowest Common Ancestor of a Binary Tree Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. Example 2:…

    DFS and return target node if found if root node has both left and right DFSs returning nodes then root is LCA, return it otherwise return found left or right DFS result Complexity. Time: O(n), Space: O(n) because tree might be skewed public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (root == p) { return p; } if (root == q) { return q; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(…

86. 767. Reorganize String Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same. If possible, output any possible result. If not possible, return the empty string. Example 1: Input: S = "aab" Output: "aba" Example 2: Input: S = "aaab" Output: "" Note: S will consist of lowercase letters and have length in range [1, 500].

    Sort by character frequency aaaabbc, now imagine bending string in the middle and interlacing with itself acababa. In this way every character sequence with be "interrupted" by another character. if any character count more that N+1/2 then its impossible. To simulate bending just will array in two passes 0,2,4,6... and 1,3,5,7... Complexity. Time: O(n+AlogA), Space: O(A) A-dict of additional space func reorganizeString(_ S: String) -> String { var countByChar = [Character:Int]() for c in Array(…

87. 67. Add Binary Easy Given two binary strings, return their sum (also a binary string). The input strings are both non-empty and contains only characters 1 or 0. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: "10101"

    Merge from the end Don't forget about carry over Complexity. Time: O(man(n,m)), Space: O(1) func addBinary(_ a: String, _ b: String) -> String { var carryOver = 0 var result = "" var a = a, b = b while !a.isEmpty || !b.isEmpty || carryOver != 0 { let aBit = a.popLast() == "1" ? 1 : 0 let bBit = b.popLast() == "1" ? 1 : 0 var localResult = aBit + bBit + carryOver if localResult == 3 { carryOver = 1 result = "1" + result } if localResult == 2 { carryOver = 1 result = "0" + result } if localResult…

88. 189. Rotate Array Easy Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Example 2: Input: [-1,-100,3,99] and k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100] Note: Try…

    concatenate two sub arrays devised by pivot point. Complexity. Time: O(man(n,m)), Space: O(1) func rotate(_ nums: inout [Int], _ k: Int) { var k = k % nums.count nums = Array(nums[nums.count - k..<nums.count]) + Array(nums[0..<nums.count - k]) }

89. 334. Increasing Triplet Subsequence Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.Note: Your algorithm should run in O(n) time complexity and O(1) space complexity. Example 1: Input: [1,2,3,4,5] Output: true Example 2: Input: [5,4,3,2,1] Output: false

    Go left to right keep track of lo and mid number update lo and mind when needed return true when number bigger then lo and mid found Complexity. Time: O(n), Space: O(1) func increasingTriplet(_ nums: [Int]) -> Bool { var lo = Int.max var mid = Int.max for n in nums { if n <= lo { lo = n } else if n <= mid { mid = n } else { return true } } return false }

90. 246. Strobogrammatic Number Easy A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. Example 1: Input: "69" Output: true Example 2: Input: "88" Output: true Example 3: Input: "962" Output: false

    Complexity. Time: O(n), Space: O(1) func isStrobogrammatic(_ num: String) -> Bool { var chars = Array(num) for idx in 0...num.count/2 { if counterpart(chars[idx]) != chars[chars.count - 1 - idx] { return false } } return true } func counterpart(_ c: Character) -> Character? { switch c { case "6": return "9" case "9": return "6" case "0","1","8": return c default: return nil } }

91. 404. Sum of Left Leaves Easy Find the sum of all left leaves in a given binary tree. Example: 3 / \ 9 20 / \ 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

    DFS Do not step into child which is right leave Complexity. Time: O(n), Space: O(1) func sumOfLeftLeaves(_ root: TreeNode?) -> Int { guard let root = root else { return 0 } if root.left == nil && root.right == nil { return 0 } return sumOfLeftLeavesRec(root) } func sumOfLeftLeavesRec(_ root: TreeNode?) -> Int { guard let root = root else { return 0 } if root.left == nil && root.right == nil { return root.val } if root.right?.left == nil && root.right?.right == nil { return sumOfLeftLeavesRec(ro…

92. 680. Valid Palindrome II Easy Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. Example 1: Input: "aba" Output: True Example 2: Input: "abca" Output: True Explanation: You could delete the character 'c'. Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

    Traverse from both ends when rich a mismatching characters remove left character and check if the rest is palindrome remove right character and check if the rest is palindrome If one of those true then answer is true Complexity. Time: O(n), Space: O(1) func validPalindrome(_ s: String) -> Bool { var chars = Array(s) var i = 0 var j = s.count - 1 while i <= j { if chars[i] == chars[j] { i += 1 j -= 1 continue } return validPalindrome(chars, i + 1, j) || validPalindrome(chars, i, j - 1) } return…

93. 658. Find K Closest Elements Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1: Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4] Example 2: Input: [1,2,3,4,5], k=4, x=-1 Output: [1,2,3,4] Note: The value k is positive and will always be smaller than the length of the sorted array. Length of the given array is positive and will not ex…

    Use binary search to find a first number in a sequence with distance to x as close to the last number in a sequence. Complexity. Time: O(logn), Space: O(1) func findClosestElements(_ arr: [Int], _ k: Int, _ x: Int) -> [Int] { var lo = 0 var hi = arr.count - k while lo < hi { let mid = (lo + hi) / 2 if x - arr[mid] > arr[mid + k] - x { lo = mid + 1 } else { hi = mid } } return Array(arr[lo..<lo + k]) }

94. 525. Contiguous Array Medium Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Note: The length of the given binary array will not exceed 50,000.

    It turns out distance between indexes with same count is our answer image Complexity. Time: O(n), Space: O(n) func findMaxLength(_ nums: [Int]) -> Int { var maxlen = 0 var count = 0 var idxByCount = [0: -1] for (idx,n) in nums.enumerated() { count += (n == 1 ? 1 : -1) if let prevIdx = idxByCount[count] { maxlen = max(maxlen, idx - prevIdx) } else { idxByCount[count] = idx } } return maxlen }

95. 287. Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is between 1 and n(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). T…

    Fast runner (2x) Slow runner (1x) When meet (intersection point) Lo runner for head Hi runner from intersection point When meet return result (cycle entrance) Complexity. Time: O(n), Space: O(1) func findDuplicate(_ nums: [Int]) -> Int { var fast = 0 var slow = 0 while true { fast = nums[fast] fast = nums[fast] slow = nums[slow] if nums[fast] == nums[slow] { break } } var lo = 0 var hi = max(fast, slow) while nums[lo] != nums[hi] { lo = nums[lo] hi = nums[hi] } return nums[hi] }

96. 53. Maximum Subarray Easy Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

    local maximum maxHere is bigger of previous maxHere + n[i]and n[i] global maximum is max of local maximums Complexity. Time: O(n), Space: O(1) func maxSubArray(_ nums: [Int]) -> Int { var maxHere = nums[0] var maxSoFar = nums[0] for x in nums[1..<nums.count] { maxHere = max(maxHere + x, x) maxSoFar = max(maxHere, maxSoFar) } return maxSoFar }

97. 121. Best Time to Buy and Sell Stock Easy 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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. Example 1: Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling pr…

    keep track of min buy price, sell price, and max profit Complexity. Time: O(n), Space: O(1) func maxProfit(_ prices: [Int]) -> Int { var buy = 0 var sell = 0 var maxProfit = 0 for (idx, x) in prices.enumerated() { if x < prices[buy] { buy = idx sell = buy } if x > prices[sell] { sell = idx } maxProfit = max(maxProfit, prices[sell] - prices[buy]) } return maxProfit }

98. 283. Move Zeroes Easy Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0] Note: You must do this in-place without making a copy of the array. Minimize the total number of operations.

    go left to right keep pointer to non zero (lo) and current pointer (hi) if swap then increment both, otherwise increment hi Complexity. Time: O(n), Space: O(1) func moveZeroes(_ nums: inout [Int]) { var lo = 0 var hi = 0 while hi < nums.count { if nums[hi] != 0 { nums.swapAt(lo, hi) lo += 1 } hi += 1 } }

99. 621. Task Scheduler Medium Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. You need to…

    Task with max count will define amount of idle slots which other tasks can occupy. By adding amount of tasks and idle slots we will get the result. Note the last task doesn't require idle tasks afterwards. Image Complexity. Time: O(n), Space: O(1) if A-Z func leastInterval(_ tasks: [Character], _ n: Int) -> Int { var counts = [Character:Int]() for task in tasks { counts[task, default: 0] += 1 } var keys = counts.keys.sorted { return counts[$0]! > counts[$1]! } let maxCount = counts[keys.first!]…

100. 560. Subarray Sum Equals K Medium Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

     If the cumulative sum uto two indices is the same, the sum of the elements lying in between those indices is 0. Extending the same thought further, if the cumulative sum upto two indices, say i and j j is at a difference of k k i.e. if sum[i] - sum[j] = k , the sum of elements lying between indices i i and j j is k Complexity. Time: O(n), Space: O(n) func subarraySum(_ nums: [Int], _ k: Int) -> Int { var countBySum = [Int: Int]() countBySum[0] = 1 var sum = 0 var total = 0 for n in nums { sum +…