NeetCode 150 Solutions in Swift
Here are the solutions for some of the most popular NeetCode 150 questions written in Swift. Each solution includes clear logic and efficient implementation.
1. Two Sum
// Function to find two numbers in
// the array that sum up to the target value.
// It returns the indices of the two numbers.
func twoSum(_ nums: [Int],
_ target: Int) -> [Int] {
var dict = [Int: Int]()
// Loop through the array while checking if
// the difference (target - num) exists in the dictionary.
for (i, num) in nums.enumerated() {
if let index = dict[target - num] {
return [index, i]
}
dict[num] = i
}
return []
}
// Usage:
// let result = twoSum([2, 7, 11, 15], 9)
// Returns [0, 1]
2. Best Time to Buy and Sell Stock
// Function to calculate the maximum
// profit by buying and selling stocks.
// It returns the maximum profit possible.
func maxProfit(_ prices: [Int]) -> Int {
var minPrice = Int.max
var maxProfit = 0
// Loop through the prices to find the
// lowest buying price and the maximum profit.
for price in prices {
minPrice = min(minPrice, price)
maxProfit = max(maxProfit, price - minPrice)
}
return maxProfit
}
// Usage:
// let profit = maxProfit([7, 1, 5, 3, 6, 4]) // Returns 5
3. Contains Duplicate
// Function to check if the array contains any duplicates.
// It returns true if there are duplicates, otherwise false.
func containsDuplicate(_ nums: [Int]) -> Bool {
return Set(nums).count != nums.count
}
// Usage:
// let hasDuplicates = containsDuplicate([1, 2, 3, 1]) // Returns true
4. Product of Array Except Self
// Function to return an array where each element is the product of all the elements except itself.
// This implementation uses a prefix and postfix approach to avoid division.
func productExceptSelf(_ nums: [Int]) -> [Int] {
let n = nums.count
var result = Array(repeating: 1, count: n)
// Step 1: Calculate prefix products using a while loop.
var prefix = 1
var i = 0
while i < n {
result[i] = prefix
prefix *= nums[i]
i += 1
}
// Step 2: Calculate postfix products and multiply with prefix.
var postfix = 1
i = n - 1
while i >= 0 {
result[i] *= postfix
postfix *= nums[i]
i -= 1
}
return result
}
// Usage:
// let product = productExceptSelf([1, 2, 3, 4]) // Returns [24, 12, 8, 6]
5. Maximum Subarray
// Function to find the contiguous subarray with the largest sum.
// It returns the maximum sum of the subarray.
func maxSubArray(_ nums: [Int]) -> Int {
var currentSum = nums[0]
var maxSum = nums[0]
// Loop through the array, updating the current sum and maximum sum.
var i = 1
while i < nums.count {
currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)
i += 1
}
return maxSum
}
// Usage:
// let maxSum = maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) // Returns 6
6. Maximum Product Subarray
// Function to find the contiguous subarray with the largest product.
// It returns the maximum product of the subarray.
func maxProduct(_ nums: [Int]) -> Int {
var result = nums[0]
var curMax = nums[0]
var curMin = nums[0]
// Loop through the array, updating the current maximum and minimum products.
var i = 1
while i < nums.count {
let tempMax = max(nums[i], nums[i] * curMax, nums[i] * curMin)
curMin = min(nums[i], nums[i] * curMax, nums[i] * curMin)
curMax = tempMax
result = max(result, curMax)
i += 1
}
return result
}
// Usage:
// let maxProd = maxProduct([2,3,-2,4]) // Returns 6
7. Find Minimum in Rotated Sorted Array
// Function to find the minimum element in a rotated sorted array.
// It uses a binary search approach to find the minimum.
func findMin(_ nums: [Int]) -> Int {
var left = 0
var right = nums.count - 1
// Binary search to find the smallest element.
while left < right {
let mid = left + (right - left) / 2
if nums[mid] > nums[right] {
left = mid + 1
} else {
right = mid
}
}
return nums[left]
}
// Usage:
// let minElement = findMin([3, 4, 5, 1, 2]) // Returns 1
8. Search in Rotated Sorted Array
// Function to search for a target value in a rotated sorted array.
// It returns the index of the target, or -1 if not found.
func search(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = nums.count - 1
// Binary search to find the target.
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target {
return mid
}
if nums[left] <= nums[mid] {
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
// Usage:
// let index = search([4,5,6,7,0,1,2], 0) // Returns 4
9. 3Sum
// Function to find all unique triplets in the array which gives the sum of zero.
// It returns a list of all unique triplets.
func threeSum(_ nums: [Int]) -> [[Int]] {
let nums = nums.sorted()
var result = [[Int]]()
for i in 0.. 0 && nums[i] == nums[i - 1] { continue }
var left = i + 1
var right = nums.count - 1
while left < right {
let sum = nums[i] + nums[left] + nums[right]
if sum == 0 {
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right && nums[left] == nums[left - 1] { left += 1 }
while left < right && nums[right] == nums[right + 1] { right -= 1 }
} else if sum < 0 {
left += 1
} else {
right -= 1
}
}
}
return result
}
// Usage:
// let triplets = threeSum([-1, 0, 1, 2, -1, -4]) // Returns [[-1, -1, 2], [-1, 0, 1]]
10. Valid Parentheses
// Function to check if the given string contains valid parentheses.
// It returns true if the parentheses are valid, otherwise false.
func isValid(_ s: String) -> Bool {
var stack = [Character]()
let map: [Character: Character] = [")": "(", "]": "[", "}": "{"]
// Loop through the string, using a stack to validate parentheses pairs.
for char in s {
if let match = map[char] {
if stack.popLast() != match {
return false
}
} else {
stack.append(char)
}
}
return stack.isEmpty
}
// Usage:
// let isValidParentheses = isValid("()[]{}") // Returns true
11. Valid Anagram
func isAnagram(_ s: String, _ t: String) -> Bool {
return s.sorted() == t.sorted()
}
12. Group Anagrams
func groupAnagrams(_ strs: [String]) -> [[String]] {
var dict = [String: [String]]()
for str in strs {
let key = String(str.sorted())
dict[key, default: []].append(str)
}
return Array(dict.values)
}
13. Top K Frequent Elements
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
var dict = [Int: Int]()
for num in nums {
dict[num, default: 0] += 1
}
let sorted = dict.sorted { $0.value > $1.value }
return sorted.prefix(k).map { $0.key }
}
14. Encode and Decode Strings
class Codec {
func encode(_ strs: [String]) -> String {
var result = ""
for str in strs {
result += "\(str.count)#\(str)"
}
return result
}
func decode(_ s: String) -> [String] {
var strs = [String]()
var i = 0
while i < s.count {
var j = i
while s[s.index(s.startIndex, offsetBy: j)] != "#" {
j += 1
}
let length = Int(s[i..15. Longest Consecutive Sequence
func longestConsecutive(_ nums: [Int]) -> Int {
let numSet = Set(nums)
var longest = 0
for num in numSet {
if !numSet.contains(num - 1) {
var currentNum = num
var currentStreak = 1
while numSet.contains(currentNum + 1) {
currentNum += 1
currentStreak += 1
}
longest = max(longest, currentStreak)
}
}
return longest
}
16. Clone Graph
class Node {
var val: Int
var neighbors: [Node?]
init(_ val: Int) {
self.val = val
self.neighbors = []
}
}
func cloneGraph(_ node: Node?) -> Node? {
guard let node = node else { return nil }
var visited = [Node: Node]()
func clone(_ node: Node) -> Node {
if let clonedNode = visited[node] {
return clonedNode
}
let cloneNode = Node(node.val)
visited[node] = cloneNode
cloneNode.neighbors = node.neighbors.compactMap { $0.map { clone($0!) } }
return cloneNode
}
return clone(node)
}
17. Course Schedule
func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
var graph = Array(repeating: [Int](), count: numCourses)
var indegree = Array(repeating: 0, count: numCourses)
// Build the graph and track indegrees
for prereq in prerequisites {
let course = prereq[0]
let prereqCourse = prereq[1]
graph[prereqCourse].append(course)
indegree[course] += 1
}
var queue = [Int]()
// Enqueue all courses with no prerequisites (indegree 0)
var i = 0
while i < numCourses {
if indegree[i] == 0 {
queue.append(i)
}
i += 1
}
var coursesTaken = 0
// Process the queue using a while loop
while !queue.isEmpty {
let course = queue.removeFirst()
coursesTaken += 1
// Decrease the indegree of all courses dependent on the current course
for nextCourse in graph[course] {
indegree[nextCourse] -= 1
if indegree[nextCourse] == 0 {
queue.append(nextCourse)
}
}
}
// If we have taken all courses, return true
return coursesTaken == numCourses
}
18. Pacific Atlantic Water Flow
func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
let rows = heights.count
let cols = heights[0].count
var pacific = Array(repeating: Array(repeating: false, count: cols), count: rows)
var atlantic = Array(repeating: Array(repeating: false, count: cols), count: rows)
// DFS function to mark reachable cells
func dfs(_ row: Int, _ col: Int, _ visited: inout [[Bool]], _ prevHeight: Int) {
if row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col] || heights[row][col] < prevHeight {
return
}
visited[row][col] = true
dfs(row + 1, col, &visited, heights[row][col])
dfs(row - 1, col, &visited, heights[row][col])
dfs(row, col + 1, &visited, heights[row][col])
dfs(row, col - 1, &visited, heights[row][col])
}
// Start DFS from Pacific and Atlantic edges
var col = 0
while col < cols {
dfs(0, col, &pacific, heights[0][col]) // Pacific Ocean (top row)
dfs(rows - 1, col, &atlantic, heights[rows - 1][col]) // Atlantic Ocean (bottom row)
col += 1
}
var row = 0
while row < rows {
dfs(row, 0, &pacific, heights[row][0]) // Pacific Ocean (left column)
dfs(row, cols - 1, &atlantic, heights[row][cols - 1]) // Atlantic Ocean (right column)
row += 1
}
// Collect cells that can flow to both oceans
var result = [[Int]]()
row = 0
while row < rows {
col = 0
while col < cols {
if pacific[row][col] && atlantic[row][col] {
result.append([row, col])
}
col += 1
}
row += 1
}
return result
}
19. Number of Islands
func numIslands(_ grid: [[Character]]) -> Int {
var grid = grid
let rows = grid.count
let cols = grid[0].count
var islandCount = 0
// DFS function to mark visited land
func dfs(_ row: Int, _ col: Int) {
if row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == "0" {
return
}
grid[row][col] = "0" // Mark the land as visited by setting it to '0'
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
}
// Loop through every cell in the grid
var row = 0
while row < rows {
var col = 0
while col < cols {
if grid[row][col] == "1" { // Found an island
islandCount += 1
dfs(row, col) // Perform DFS to mark the entire island
}
col += 1
}
row += 1
}
return islandCount
}
20. Word Search
func exist(_ board: [[Character]], _ word: String) -> Bool {
let rows = board.count
let cols = board[0].count
let wordArray = Array(word)
// Helper DFS function to search the word in the grid
func dfs(_ row: Int, _ col: Int, _ index: Int) -> Bool {
if index == wordArray.count {
return true
}
if row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != wordArray[index] {
return false
}
var tempBoard = board
tempBoard[row][col] = "#" // Mark the cell as visited
let found = dfs(row + 1, col, index + 1) ||
dfs(row - 1, col, index + 1) ||
dfs(row, col + 1, index + 1) ||
dfs(row, col - 1, index + 1)
tempBoard[row][col] = wordArray[index] // Restore the cell value
return found
}
// Traverse the board to find the starting point for the word
var row = 0
while row < rows {
var col = 0
while col < cols {
if dfs(row, col, 0) {
return true
}
col += 1
}
row += 1
}
return false
}
21. Longest Substring Without Repeating Characters
func lengthOfLongestSubstring(_ s: String) -> Int {
var charIndexMap = [Character: Int]()
var maxLength = 0
var left = 0
for (right, char) in s.enumerated() {
if let prevIndex = charIndexMap[char], prevIndex >= left {
left = prevIndex + 1
}
charIndexMap[char] = right
maxLength = max(maxLength, right - left + 1)
}
return maxLength
}
22. Longest Repeating Character Replacement
func characterReplacement(_ s: String, _ k: Int) -> Int {
var count = [Character: Int]()
var maxFreq = 0
var left = 0
var result = 0
for (right, char) in s.enumerated() {
count[char, default: 0] += 1
maxFreq = max(maxFreq, count[char]!)
if (right - left + 1) - maxFreq > k {
count[s[s.index(s.startIndex, offsetBy: left)]]! -= 1
left += 1
}
result = max(result, right - left + 1)
}
return result
}
23. Minimum Window Substring
func minWindow(_ s: String, _ t: String) -> String? {
var dictT = [Character: Int]()
var windowCounts = [Character: Int]()
for char in t {
dictT[char, default: 0] += 1
}
let required = dictT.count
var left = 0, right = 0, formed = 0
var ans: (length: Int, start: Int, end: Int) = (Int.max, 0, 0)
while right < s.count {
let charRight = s[s.index(s.startIndex, offsetBy: right)]
windowCounts[charRight, default: 0] += 1
if let valT = dictT[charRight], windowCounts[charRight] == valT {
formed += 1
}
while left <= right && formed == required {
let charLeft = s[s.index(s.startIndex, offsetBy: left)]
if (right - left + 1) < ans.length {
ans = (right - left + 1, left, right)
}
windowCounts[charLeft]! -= 1
if let valT = dictT[charLeft], windowCounts[charLeft]! < valT {
formed -= 1
}
left += 1
}
right += 1
}
return ans.length == Int.max ? nil : String(s[s.index(s.startIndex, offsetBy: ans.start)...s.index(s.startIndex, offsetBy: ans.end)])
}
24. Sliding Window Maximum
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
var result = [Int]()
var deque = [Int]()
for i in 0..= k - 1 {
result.append(nums[deque.first!])
}
}
return result
}
25. Valid Palindrome
func isPalindrome(_ s: String) -> Bool {
let filtered = s.lowercased().filter { $0.isLetter || $0.isNumber }
return filtered == filtered.reversed()
}
26. Longest Palindromic Substring
func longestPalindrome(_ s: String) -> String {
if s.isEmpty { return "" }
var start = 0, end = 0
let characters = Array(s)
for i in 0.. end - start {
start = i - (len - 1) / 2
end = i + len / 2
}
}
return String(characters[start...end])
}
func expandFromMiddle(_ s: [Character], _ left: Int, _ right: Int) -> Int {
var left = left, right = right
while left >= 0 && right < s.count && s[left] == s[right] {
left -= 1
right += 1
}
return right - left - 1
}
26. Longest Palindromic Substring
func longestPalindrome(_ s: String) -> String {
if s.isEmpty { return "" }
var start = 0, end = 0
let characters = Array(s)
for i in 0.. end - start {
start = i - (len - 1) / 2
end = i + len / 2
}
}
return String(characters[start...end])
}
func expandFromMiddle(_ s: [Character], _ left: Int, _ right: Int) -> Int {
var left = left, right = right
while left >= 0 && right < s.count && s[left] == s[right] {
left -= 1
right += 1
}
return right - left - 1
}
27. Palindromic Substrings
func countSubstrings(_ s: String) -> Int {
var count = 0
let characters = Array(s)
for i in 0.. Int {
var left = left, right = right
var count = 0
while left >= 0 && right < s.count && s[left] == s[right] {
count += 1
left -= 1
right += 1
}
return count
}
28. Word Break (BFS Approach)
func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
let wordSet = Set(wordDict)
var queue = [0]
var visited = Array(repeating: false, count: s.count)
while !queue.isEmpty {
let start = queue.removeFirst()
if visited[start] {
continue
}
var end = start + 1
while end <= s.count {
let startIndex = s.index(s.startIndex,offsetBy: start)
let endIndex = s.index(s.startIndex,offsetBy: end)
let substring = String(s[startIndex..endIndex-1])
if wordSet.contains(substring) {
if end == s.count {
return true
}
queue.append(end)
}
end += 1
}
visited[start] = true
}
return false
}
29. Combination Sum
func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
var result = [[Int]]()
func backtrack(_ remaining: Int, _ start: Int, _ path: [Int]) {
if remaining < 0 { return }
if remaining == 0 {
result.append(path)
return
}
var i = start
while i < candidates.count {
backtrack(remaining - candidates[i], i, path + [candidates[i]])
i += 1
}
}
backtrack(target, 0, [])
return result
}
30. Permutation in String
func checkInclusion(_ s1: String, _ s2: String) -> Bool {
if s1.count > s2.count { return false }
let s1Count = Array(s1).reduce(into: [Character: Int]()) { $0[$1, default: 0] += 1 }
var s2Count = Array(s2.prefix(s1.count)).reduce(into: [Character: Int]()) { $0[$1, default: 0] += 1 }
if s1Count == s2Count { return true }
for i in s1.count..s2.count-1 {
let startChar = s2[s2.index(s2.startIndex, offsetBy: i - s1.count)]
let endChar = s2[s2.index(s2.startIndex, offsetBy: i)]
s2Count[endChar, default: 0] += 1
s2Count[startChar]! -= 1
if s2Count[startChar]! == 0 {
s2Count.removeValue(forKey: startChar)
}
if s1Count == s2Count { return true }
}
return false
}
31. Merge Intervals
func merge(_ intervals: [[Int]]) -> [[Int]] {
guard intervals.count > 1 else { return intervals }
let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
var stack = [sortedIntervals[0]] // Use stack to store the merged intervals
for i in 1..sortedIntervals.count-1 {
let current = sortedIntervals[i]
let top = stack.last!
// If the current interval overlaps with the top of the stack, merge them
if current[0] <= top[1] {
stack[stack.count - 1][1] = max(top[1], current[1])
} else {
// Otherwise, push the current interval onto the stack
stack.append(current)
}
}
return stack
}
32. Insert Interval
func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
var result = [[Int]]()
var i = 0
// Add all intervals before newInterval
while i < intervals.count && intervals[i][1] < newInterval[0] {
result.append(intervals[i])
i += 1
}
// Merge overlapping intervals with newInterval
var mergedInterval = newInterval
while i < intervals.count && intervals[i][0] <= newInterval[1] {
mergedInterval[0] = min(mergedInterval[0], intervals[i][0])
mergedInterval[1] = max(mergedInterval[1], intervals[i][1])
i += 1
}
result.append(mergedInterval)
// Add remaining intervals
while i < intervals.count {
result.append(intervals[i])
i += 1
}
return result
}
33. Non-overlapping Intervals
func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
var count = 0
var prevEnd = sortedIntervals[0][1]
var i = 1
while i < sortedIntervals.count {
if sortedIntervals[i][0] < prevEnd {
count += 1 // Count the overlapping interval
} else {
prevEnd = sortedIntervals[i][1] // Update the previous end to the current interval
}
i += 1
}
return count
}
34. Meeting Rooms
func canAttendMeetings(_ intervals: [[Int]]) -> Bool {
let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
for i in 1..sortedIntervals.count-1 {
if sortedIntervals[i][0] < sortedIntervals[i - 1][1] {
return false
}
}
return true
}
35. Meeting Rooms II
func minMeetingRooms(_ intervals: [[Int]]) -> Int {
let starts = intervals.map { $0[0] }.sorted()
let ends = intervals.map { $0[1] }.sorted()
var rooms = 0
var endPtr = 0
for i in 0..starts.count-1 {
if starts[i] < ends[endPtr] {
rooms += 1
} else {
endPtr += 1
}
}
return rooms
}
36. Reverse Linked List
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var current = head
while current != nil {
let nextTemp = current!.next
current!.next = prev
prev = current
current = nextTemp
}
return prev
}
37. Linked List Cycle
func hasCycle(_ head: ListNode?) -> Bool {
var slow = head
var fast = head
while fast != nil && fast!.next != nil {
slow = slow!.next
fast = fast!.next!.next
if slow === fast {
return true
}
}
return false
}
38. Merge Two Sorted Lists
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
let dummy = ListNode(0)
var current = dummy
var l1 = list1
var l2 = list2
while l1 != nil && l2 != nil {
if l1!.val < l2!.val {
current.next = l1
l1 = l1!.next
} else {
current.next = l2
l2 = l2!.next
}
current = current.next!
}
current.next = l1 ?? l2
return dummy.next
}
39. Reorder List
func reorderList(_ head: ListNode?) {
guard head != nil else { return }
var slow = head
var fast = head
while fast != nil && fast!.next != nil {
slow = slow!.next
fast = fast!.next!.next
}
var prev: ListNode? = nil
var curr = slow!.next
slow!.next = nil
while curr != nil {
let nextTemp = curr!.next
curr!.next = prev
prev = curr
curr = nextTemp
}
var first = head
var second = prev
while second != nil {
let tmp1 = first!.next
let tmp2 = second!.next
first!.next = second
second!.next = tmp1
first = tmp1
second = tmp2
}
}
40. Remove N-th Node From End of List
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
let dummy = ListNode(0)
dummy.next = head
var first: ListNode? = dummy
var second: ListNode? = dummy
for _ in 0...n {
first = first!.next
}
while first != nil {
first = first!.next
second = second!.next
}
second!.next = second!.next!.next
return dummy.next
}
41. Copy List with Random Pointer
class Node {
var val: Int
var next: Node?
var random: Node?
init(_ val: Int) {
self.val = val
self.next = nil
self.random = nil
}
}
func copyRandomList(_ head: Node?) -> Node? {
guard let head = head else { return nil }
var nodeMap = [Node: Node]()
var current: Node? = head
while current != nil {
nodeMap[current!] = Node(current!.val)
current = current!.next
}
current = head
while current != nil {
let copyNode = nodeMap[current!]!
copyNode.next = nodeMap[current!.next ?? nil]
copyNode.random = nodeMap[current!.random ?? nil]
current = current!.next
}
return nodeMap[head]
}
42. Add Two Numbers
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(0)
var p = l1, q = l2, current = dummy
var carry = 0
while p != nil || q != nil {
let x = p?.val ?? 0
let y = q?.val ?? 0
let sum = carry + x + y
carry = sum / 10
current.next = ListNode(sum % 10)
current = current.next!
p = p?.next
q = q?.next
}
if carry > 0 {
current.next = ListNode(carry)
}
return dummy.next
}
43. Flatten Binary Tree to Linked List
func flatten(_ root: TreeNode?) {
var current = root
while current != nil {
if current!.left != nil {
var rightmost = current!.left
while rightmost!.right != nil {
rightmost = rightmost!.right
}
rightmost!.right = current!.right
current!.right = current!.left
current!.left = nil
}
current = current!.right
}
}
44. Find Median from Data Stream
class MedianFinder {
var small = [Int]()
var large = [Int]()
init() { }
func addNum(_ num: Int) {
small.append(num)
small.sort(by: >)
if small.count > large.count {
large.append(small.removeFirst())
}
if !large.isEmpty && large.first! < small.first! {
let temp = large.removeFirst()
large.append(small.removeFirst())
small.append(temp)
}
}
func findMedian() -> Double {
if small.count > large.count {
return Double(small.first!)
} else {
return Double(small.first! + large.first!) / 2.0
}
}
}
45. Binary Tree Level Order Traversal
func levelOrder(_ root: TreeNode?) -> [[Int]] {
var result = [[Int]]()
guard let root = root else { return result }
var queue = [root]
while !queue.isEmpty {
var level = [Int]()
var levelSize = queue.count
var i = 0
while i < levelSize {
let node = queue.removeFirst()
level.append(node.val)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
i += 1
}
result.append(level)
}
return result
}
46. Maximum Depth of Binary Tree
func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
return 1 + max(maxDepth(root.left), maxDepth(root.right))
}
47. Same Tree
func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
if p == nil && q == nil { return true }
if p == nil || q == nil { return false }
if p!.val != q!.val { return false }
return isSameTree(p!.left, q!.left) && isSameTree(p!.right, q!.right)
}
48. Subtree of Another Tree
func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
guard let root = root else { return false }
if isSameTree(root, subRoot) { return true }
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
}
func isSameTree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
if s == nil && t == nil { return true }
if s == nil || t == nil { return false }
if s!.val != t!.val { return false }
return isSameTree(s!.left, t!.left) && isSameTree(s!.right, t!.right)
}
49. Lowest Common Ancestor of a Binary Search Tree
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
guard let root = root, let p = p, let q = q else { return nil }
if p.val < root.val && q.val < root.val {
return lowestCommonAncestor(root.left, p, q)
} else if p.val > root.val && q.val > root.val {
return lowestCommonAncestor(root.right, p, q)
} else {
return root
}
}
50. Binary Tree Maximum Path Sum
func maxPathSum(_ root: TreeNode?) -> Int {
var maxSum = Int.min
func maxGain(_ node: TreeNode?) -> Int {
guard let node = node else { return 0 }
let leftGain = max(maxGain(node.left), 0)
let rightGain = max(maxGain(node.right), 0)
let priceNewPath = node.val + leftGain + rightGain
maxSum = max(maxSum, priceNewPath)
return node.val + max(leftGain, rightGain)
}
_ = maxGain(root)
return maxSum
}
51. Construct Binary Tree from Preorder and Inorder Traversal
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
var preorderIndex = 0
var inorderIndexMap = [Int: Int]()
for (index, value) in inorder.enumerated() {
inorderIndexMap[value] = index
}
func arrayToTree(_ left: Int, _ right: Int) -> TreeNode? {
if left > right {
return nil
}
let rootValue = preorder[preorderIndex]
preorderIndex += 1
let root = TreeNode(rootValue)
root.left = arrayToTree(left, inorderIndexMap[rootValue]! - 1)
root.right = arrayToTree(inorderIndexMap[rootValue]! + 1, right)
return root
}
return arrayToTree(0, preorder.count - 1)
}
52. Validate Binary Search Tree
func isValidBST(_ root: TreeNode?) -> Bool {
return validate(root, nil, nil)
}
func validate(_ node: TreeNode?, _ lower: Int?, _ upper: Int?) -> Bool {
guard let node = node else { return true }
if let lower = lower, node.val <= lower { return false }
if let upper = upper, node.val >= upper { return false }
return validate(node.left, lower, node.val) && validate(node.right, node.val, upper)
}
53. Kth Smallest Element in a BST
func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
var inorderArray = [Int]()
func inorder(_ node: TreeNode?) {
guard let node = node else { return }
inorder(node.left)
inorderArray.append(node.val)
inorder(node.right)
}
inorder(root)
return inorderArray[k - 1]
}
54. Implement Trie (Prefix Tree)
class Trie {
class TrieNode {
var children = [Character: TrieNode]()
var isEndOfWord = false
}
private let root = TrieNode()
func insert(_ word: String) {
var current = root
for char in word {
if current.children[char] == nil {
current.children[char] = TrieNode()
}
current = current.children[char]!
}
current.isEndOfWord = true
}
func search(_ word: String) -> Bool {
var current = root
for char in word {
if let nextNode = current.children[char] {
current = nextNode
} else {
return false
}
}
return current.isEndOfWord
}
func startsWith(_ prefix: String) -> Bool {
var current = root
for char in prefix {
if let nextNode = current.children[char] {
current = nextNode
} else {
return false
}
}
return true
}
}
55. Design Add and Search Words Data Structure
class WordDictionary {
class TrieNode {
var children = [Character: TrieNode]()
var isEndOfWord = false
}
private let root = TrieNode()
func addWord(_ word: String) {
var current = root
for char in word {
if current.children[char] == nil {
current.children[char] = TrieNode()
}
current = current.children[char]!
}
current.isEndOfWord = true
}
func search(_ word: String) -> Bool {
return searchInNode(word, 0, root)
}
private func searchInNode(_ word: String, _ index: Int, _ node: TrieNode?) -> Bool {
guard let node = node else { return false }
if index == word.count {
return node.isEndOfWord
}
let char = Array(word)[index]
if char == "." {
for child in node.children.values {
if searchInNode(word, index + 1, child) {
return true
}
}
return false
} else {
return searchInNode(word, index + 1, node.children[char])
}
}
}
56. Word Search II
class WordSearchII {
class TrieNode {
var children = [Character: TrieNode]()
var word: String?
}
func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
let root = buildTrie(words)
var result = Set()
var board = board
for i in 0.. TrieNode {
let root = TrieNode()
for word in words {
var node = root
for char in word {
if node.children[char] == nil {
node.children[char] = TrieNode()
}
node = node.children[char]!
}
node.word = word
}
return root
}
private func dfs(_ board: inout [[Character]], _ i: Int, _ j: Int, _ node: TrieNode, _ result: inout Set) {
guard i >= 0 && i < board.count && j >= 0 && j < board[0].count else { return }
let char = board[i][j]
guard let nextNode = node.children[char] else { return }
if let word = nextNode.word {
result.insert(word)
}
board[i][j] = "#"
dfs(&board, i + 1, j, nextNode, &result)
dfs(&board, i - 1, j, nextNode, &result)
dfs(&board, i, j + 1, nextNode, &result)
dfs(&board, i, j - 1, nextNode, &result)
board[i][j] = char
}
}
57. Longest Palindromic Subsequence
func longestPalindromeSubseq(_ s: String) -> Int {
let n = s.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
let chars = Array(s)
for i in (0...n-1).reversed() {
dp[i][i] = 1
for j in i+1..n-1 {
if chars[i] == chars[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][n-1]
}
58. Palindromic Substrings
func countSubstrings(_ s: String) -> Int {
var count = 0
let characters = Array(s)
for i in 0.. Int {
var count = 0
var left = left, right = right
while left >= 0 && right < s.count && s[left] == s[right] {
count += 1
left -= 1
right += 1
}
return count
}
59. Word Break
func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
let wordSet = Set(wordDict)
var dp = Array(repeating: false, count: s.count + 1)
dp[0] = true
var i = 1
while i <= s.count {
var j = 0
while j < i {
let startIndex = s.index(s.startIndex, offsetBy: j)
let endIndex = s.index(s.startIndex, offsetBy: i)
let substring = String(s[startIndex...endIndex-1])
if dp[j] && wordSet.contains(substring) {
dp[i] = true
break
}
j += 1
}
i += 1
}
return dp[s.count]
}
60. Combination Sum II
func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
var result = [[Int]]()
var candidates = candidates.sorted()
func backtrack(_ start: Int, _ target: Int, _ currentList: [Int]) {
if target == 0 {
result.append(currentList)
return
}
for i in start.. start && candidates[i] == candidates[i - 1] { continue }
if candidates[i] > target { break }
backtrack(i + 1, target - candidates[i], currentList + [candidates[i]])
}
}
backtrack(0, target, [])
return result
}
61. Partition Equal Subset Sum
func canPartition(_ nums: [Int]) -> Bool {
let totalSum = nums.reduce(0, +)
if totalSum % 2 != 0 { return false }
let target = totalSum / 2
var dp = Set()
dp.insert(0)
for num in nums {
var nextDp = dp
for val in dp {
nextDp.insert(val + num)
}
dp = nextDp
if dp.contains(target) {
return true
}
}
return false
}
62. Decode Ways
func numDecodings(_ s: String) -> Int {
if s.isEmpty || s.first == "0" { return 0 }
var dp = Array(repeating: 0, count: s.count + 1)
dp[0] = 1
dp[1] = 1
let chars = Array(s)
for i in 2...s.count {
let oneDigit = Int(String(chars[i - 1]))!
let twoDigits = Int(String(chars[i - 2...i - 1]))!
if oneDigit >= 1 {
dp[i] += dp[i - 1]
}
if twoDigits >= 10 && twoDigits <= 26 {
dp[i] += dp[i - 2]
}
}
return dp[s.count]
}
63. Unique Paths
// 63. Unique Paths
func uniquePaths(_ m: Int, _ n: Int) -> Int {
var dp = Array(repeating: Array(repeating: 1, count: n), count: m)
var i = 1
while i < m {
var j = 1
while j < n {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
j += 1
}
i += 1
}
return dp[m - 1][n - 1]
}
64. Unique Paths II
// 64. Unique Paths II
func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
let m = obstacleGrid.count
let n = obstacleGrid[0].count
var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1
var i = 1
while i < m {
dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0]
i += 1
}
var j = 1
while j < n {
dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j - 1]
j += 1
}
i = 1
while i < m {
j = 1
while j < n {
if obstacleGrid[i][j] == 1 {
dp[i][j] = 0
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
j += 1
}
i += 1
}
return dp[m - 1][n - 1]
}
65. Min Cost Climbing Stairs
// 65. Min Cost Climbing Stairs
func minCostClimbingStairs(_ cost: [Int]) -> Int {
var dp = cost
var i = 2
while i < cost.count {
dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
i += 1
}
return min(dp[cost.count - 1], dp[cost.count - 2])
}
66. House Robber
// 66. House Robber
func rob(_ nums: [Int]) -> Int {
if nums.isEmpty { return 0 }
if nums.count == 1 { return nums[0] }
var dp = nums
dp[1] = max(nums[0], nums[1])
var i = 2
while i < nums.count {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
i += 1
}
return dp[nums.count - 1]
}
67. House Robber II
func rob(_ nums: [Int]) -> Int {
if nums.count == 1 { return nums[0] }
return max(robRange(nums, 0, nums.count - 2), robRange(nums, 1, nums.count - 1))
}
private func robRange(_ nums: [Int], _ start: Int, _ end: Int) -> Int {
var prev1 = 0
var prev2 = 0
for i in start...end {
let current = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = current
}
return prev1
}
68. Coin Change
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
var dp = Array(repeating: amount + 1, count: amount + 1)
dp[0] = 0
for coin in coins {
for x in coin...amount {
dp[x] = min(dp[x], dp[x - coin] + 1)
}
}
return dp[amount] > amount ? -1 : dp[amount]
}
69. Longest Increasing Subsequence
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp = Array(repeating: 1, count: nums.count)
for i in 1.. nums[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
return dp.max() ?? 0
}
70. Longest Common Subsequence
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
let m = text1.count
let n = text2.count
let chars1 = Array(text1)
let chars2 = Array(text2)
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
for i in 1...m {
for j in 1...n {
if chars1[i - 1] == chars2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[m][n]
}
71. Delete Operation for Two Strings
func minDistance(_ word1: String, _ word2: String) -> Int {
let m = word1.count
let n = word2.count
let lcsLength = longestCommonSubsequence(Array(word1), Array(word2))
return m + n - 2 * lcsLength
}
private func longestCommonSubsequence(_ s1: [Character], _ s2: [Character]) -> Int {
let m = s1.count
let n = s2.count
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
for i in 1...m {
for j in 1...n {
if s1[i - 1] == s2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[m][n]
}
72. Edit Distance
func minDistance(_ word1: String, _ word2: String) -> Int {
let m = word1.count
let n = word2.count
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
for i in 0...m {
for j in 0...n {
if i == 0 {
dp[i][j] = j
} else if j == 0 {
dp[i][j] = i
} else if Array(word1)[i - 1] == Array(word2)[j - 1] {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
}
}
}
return dp[m][n]
}
73. Regular Expression Matching
func isMatch(_ s: String, _ p: String) -> Bool {
let m = s.count
let n = p.count
var dp = Array(repeating: Array(repeating: false, count: n + 1), count: m + 1)
dp[0][0] = true
let sArr = Array(s)
let pArr = Array(p)
for j in 1...n {
if pArr[j - 1] == "*" {
dp[0][j] = dp[0][j - 2]
}
}
for i in 1...m {
for j in 1...n {
if sArr[i - 1] == pArr[j - 1] || pArr[j - 1] == "." {
dp[i][j] = dp[i - 1][j - 1]
} else if pArr[j - 1] == "*" {
dp[i][j] = dp[i][j - 2]
if sArr[i - 1] == pArr[j - 2] || pArr[j - 2] == "." {
dp[i][j] = dp[i][j] || dp[i - 1][j]
}
}
}
}
return dp[m][n]
}
74. Wildcard Matching
func isMatch(_ s: String, _ p: String) -> Bool {
let m = s.count
let n = p.count
var dp = Array(repeating: Array(repeating: false, count: n + 1), count: m + 1)
dp[0][0] = true
let sArr = Array(s)
let pArr = Array(p)
for j in 1...n {
if pArr[j - 1] == "*" {
dp[0][j] = dp[0][j - 1]
}
}
for i in 1...m {
for j in 1...n {
if sArr[i - 1] == pArr[j - 1] || pArr[j - 1] == "?" {
dp[i][j] = dp[i - 1][j - 1]
} else if pArr[j - 1] == "*" {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1]
}
}
}
return dp[m][n]
}
75. Interleaving String
func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
let m = s1.count
let n = s2.count
if m + n != s3.count { return false }
var dp = Array(repeating: Array(repeating: false, count: n + 1), count: m + 1)
dp[0][0] = true
let s1Arr = Array(s1)
let s2Arr = Array(s2)
let s3Arr = Array(s3)
for i in 0...m {
for j in 0...n {
if i > 0 && s1Arr[i - 1] == s3Arr[i + j - 1] {
dp[i][j] = dp[i][j] || dp[i - 1][j]
}
if j > 0 && s2Arr[j - 1] == s3Arr[i + j - 1] {
dp[i][j] = dp[i][j] || dp[i][j - 1]
}
}
}
return dp[m][n]
}
76. Scramble String
func isScramble(_ s1: String, _ s2: String) -> Bool {
if s1 == s2 { return true }
let length = s1.count
let s1Arr = Array(s1)
let s2Arr = Array(s2)
var dp = Array(repeating: Array(repeating: Array(repeating: false, count: length + 1), count: length), count: length)
for i in 0..77. Distinct Subsequences
func numDistinct(_ s: String, _ t: String) -> Int {
let m = s.count
let n = t.count
let sArr = Array(s)
let tArr = Array(t)
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
for i in 0...m {
dp[i][0] = 1
}
for i in 1...m {
for j in 1...n {
if sArr[i - 1] == tArr[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
} else {
dp[i][j] = dp[i - 1][j]
}
}
}
return dp[m][n]
}
78. Decode String
func decodeString(_ s: String) -> String {
var stack = [(String, Int)]()
var currentString = ""
var currentNumber = 0
for char in s {
if char.isNumber {
currentNumber = currentNumber * 10 + Int(String(char))!
} else if char == "[" {
stack.append((currentString, currentNumber))
currentString = ""
currentNumber = 0
} else if char == "]" {
let (prevString, multiplier) = stack.removeLast()
currentString = prevString + String(repeating: currentString, count: multiplier)
} else {
currentString.append(char)
}
}
return currentString
}
79. Validate IP Address
func validIPAddress(_ IP: String) -> String {
if isValidIPv4(IP) {
return "IPv4"
} else if isValidIPv6(IP) {
return "IPv6"
} else {
return "Neither"
}
}
private func isValidIPv4(_ IP: String) -> Bool {
let components = IP.split(separator: ".")
if components.count != 4 { return false }
for component in components {
if component.isEmpty || component.count > 3 || !component.allSatisfy({ $0.isNumber }) { return false }
if let num = Int(component), num < 0 || num > 255 || (component.first == "0" && component.count > 1) {
return false
}
}
return true
}
private func isValidIPv6(_ IP: String) -> Bool {
let components = IP.split(separator: ":")
if components.count != 8 { return false }
for component in components {
if component.isEmpty || component.count > 4 || !component.allSatisfy({ $0.isHexDigit }) { return false }
}
return true
}
80. Serialize and Deserialize Binary Tree
class Codec {
func serialize(_ root: TreeNode?) -> String {
var result = [String]()
serializeHelper(root, &result)
return result.joined(separator: ",")
}
func deserialize(_ data: String) -> TreeNode? {
var values = data.split(separator: ",").map { String($0) }
return deserializeHelper(&values)
}
private func serializeHelper(_ root: TreeNode?, _ result: inout [String]) {
guard let root = root else {
result.append("null")
return
}
result.append(String(root.val))
serializeHelper(root.left, &result)
serializeHelper(root.right, &result)
}
private func deserializeHelper(_ values: inout [String]) -> TreeNode? {
if values.isEmpty { return nil }
let value = values.removeFirst()
if value == "null" { return nil }
let node = TreeNode(Int(value)!)
node.left = deserializeHelper(&values)
node.right = deserializeHelper(&values)
return node
}
}
81. Insert Delete GetRandom O(1)
class RandomizedSet {
private var dict = [Int: Int]()
private var list = [Int]()
func insert(_ val: Int) -> Bool {
if dict[val] != nil { return false }
dict[val] = list.count
list.append(val)
return true
}
func remove(_ val: Int) -> Bool {
guard let index = dict[val] else { return false }
let last = list.removeLast()
if index < list.count {
list[index] = last
dict[last] = index
}
dict.removeValue(forKey: val)
return true
}
func getRandom() -> Int {
return list[Int.random(in: 0..
82. Insert Delete GetRandom O(1) - Duplicates Allowed
class RandomizedCollection {
private var dict = [Int: Set]()
private var list = [Int]()
func insert(_ val: Int) -> Bool {
let alreadyPresent = dict[val] != nil
dict[val, default: Set()].insert(list.count)
list.append(val)
return !alreadyPresent
}
func remove(_ val: Int) -> Bool {
guard let indexes = dict[val], let index = indexes.first else { return false }
let last = list.removeLast()
if index < list.count {
list[index] = last
dict[last]?.insert(index)
dict[last]?.remove(list.count)
}
dict[val]?.remove(index)
if dict[val]?.isEmpty == true {
dict.removeValue(forKey: val)
}
return true
}
func getRandom() -> Int {
return list[Int.random(in: 0..
83. Serialize and Deserialize BST
class CodecBST {
func serialize(_ root: TreeNode?) -> String {
var result = [String]()
serializeHelper(root, &result)
return result.joined(separator: ",")
}
func deserialize(_ data: String) -> TreeNode? {
var values = data.split(separator: ",").map { Int($0)! }
return deserializeHelper(&values, Int.min, Int.max)
}
private func serializeHelper(_ root: TreeNode?, _ result: inout [String]) {
guard let root = root else { return }
result.append(String(root.val))
serializeHelper(root.left, &result)
serializeHelper(root.right, &result)
}
private func deserializeHelper(_ values: inout [Int], _ lower: Int, _ upper: Int) -> TreeNode? {
guard let value = values.first, value > lower, value < upper else { return nil }
values.removeFirst()
let node = TreeNode(value)
node.left = deserializeHelper(&values, lower, value)
node.right = deserializeHelper(&values, value, upper)
return node
}
}
84. Lowest Common Ancestor of Deepest Leaves
func lcaDeepestLeaves(_ root: TreeNode?) -> TreeNode? {
func depth(_ node: TreeNode?) -> Int {
guard let node = node else { return 0 }
return max(depth(node.left), depth(node.right)) + 1
}
func lca(_ node: TreeNode?) -> (Int, TreeNode?) {
guard let node = node else { return (0, nil) }
let left = lca(node.left)
let right = lca(node.right)
if left.0 == right.0 {
return (left.0 + 1, node)
}
return left.0 > right.0 ? (left.0 + 1, left.1) : (right.0 + 1, right.1)
}
return lca(root).1
}
85. Word Ladder
func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
let wordSet = Set(wordList)
if !wordSet.contains(endWord) { return 0 }
var queue = [(beginWord, 1)]
var visited = Set()
visited.insert(beginWord)
while !queue.isEmpty {
let (word, steps) = queue.removeFirst()
if word == endWord { return steps }
for i in 0.. 86. Word Ladder II
func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
var wordSet = Set(wordList)
if !wordSet.contains(endWord) { return [] }
var queue = [[beginWord]]
var result = [[String]]()
var levelVisited = Set()
var found = false
while !queue.isEmpty && !found {
var nextLevel = [[String]]()
for path in queue {
let word = path.last!
var chars = Array(word)
for i in 0.. 87. Minimum Window Substring
func minWindow(_ s: String, _ t: String) -> String {
var dictT = [Character: Int]()
var windowCounts = [Character: Int]()
for char in t {
dictT[char, default: 0] += 1
}
let required = dictT.count
var left = 0, right = 0, formed = 0
var ans: (length: Int, start: Int, end: Int) = (Int.max, 0, 0)
while right < s.count {
let charRight = s[s.index(s.startIndex, offsetBy: right)]
windowCounts[charRight, default: 0] += 1
if let valT = dictT[charRight], windowCounts[charRight] == valT {
formed += 1
}
while left <= right && formed == required {
let charLeft = s[s.index(s.startIndex, offsetBy: left)]
if (right - left + 1) < ans.length {
ans = (right - left + 1, left, right)
}
windowCounts[charLeft]! -= 1
if let valT = dictT[charLeft], windowCounts[charLeft]! < valT {
formed -= 1
}
left += 1
}
right += 1
}
return ans.length == Int.max ? "" : String(s[s.index(s.startIndex, offsetBy: ans.start)...s.index(s.startIndex, offsetBy: ans.end)])
}
88. Search Suggestions System
func suggestedProducts(_ products: [String], _ searchWord: String) -> [[String]] {
let sortedProducts = products.sorted()
var result = [[String]]()
var prefix = ""
for char in searchWord {
prefix.append(char)
var suggestions = [String]()
for product in sortedProducts {
if product.hasPrefix(prefix) {
suggestions.append(product)
}
if suggestions.count == 3 {
break
}
}
result.append(suggestions)
}
return result
}
89. Longest Substring with At Least K Repeating Characters
func longestSubstring(_ s: String, _ k: Int) -> Int {
if s.isEmpty || k > s.count { return 0 }
let charCount = Array(s).reduce(into: [Character: Int]()) { $0[$1, default: 0] += 1 }
let invalidChar = charCount.first { $0.value > 0 && $0.value < k }
guard let invalidChar = invalidChar else { return s.count }
return s.split(separator: invalidChar.key).map { longestSubstring(String($0), k) }.max() ?? 0
}
90. Range Sum Query - Mutable
class NumArray {
private var nums: [Int]
private var bit: [Int]
init(_ nums: [Int]) {
self.nums = nums
self.bit = Array(repeating: 0, count: nums.count + 1)
for i in 0.. Int {
return sum(right + 1) - sum(left)
}
private func sum(_ index: Int) -> Int {
var sum = 0
var i = index
while i > 0 {
sum += bit[i]
i -= i & -i
}
return sum
}
}
91. Count of Smaller Numbers After Self
func countSmaller(_ nums: [Int]) -> [Int] {
var result = [Int]()
var sortedList = [Int]()
for num in nums.reversed() {
let index = binarySearch(sortedList, num)
result.append(index)
sortedList.insert(num, at: index)
}
return result.reversed()
}
private func binarySearch(_ sortedList: [Int], _ target: Int) -> Int {
var left = 0
var right = sortedList.count
while left < right {
let mid = left + (right - left) / 2
if sortedList[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
return left
}
92. Guess Number Higher or Lower II
func getMoneyAmount(_ n: Int) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
for len in 2...n {
for start in 1...(n - len + 1) {
let end = start + len - 1
dp[start][end] = Int.max
for pivot in start...(end - 1) {
let cost = pivot + max(dp[start][pivot - 1], dp[pivot + 1][end])
dp[start][end] = min(dp[start][end], cost)
}
}
}
return dp[1][n]
}
93. Dungeon Game
func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
let m = dungeon.count
let n = dungeon[0].count
var dp = Array(repeating: Array(repeating: Int.max, count: n + 1), count: m + 1)
dp[m][n - 1] = 1
dp[m - 1][n] = 1
for i in (0..94. Best Meeting Point
func minTotalDistance(_ grid: [[Int]]) -> Int {
var rows = [Int]()
var cols = [Int]()
for i in 0.. Int {
var i = 0
var j = points.count - 1
var distance = 0
while i < j {
distance += points[j] - points[i]
i += 1
j -= 1
}
return distance
}
95. Range Sum Query 2D - Mutable
class NumMatrix {
private var matrix: [[Int]]
private var bit: [[Int]]
private var m: Int
private var n: Int
init(_ matrix: [[Int]]) {
self.m = matrix.count
self.n = matrix[0].count
self.matrix = matrix
self.bit = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
for i in 0.. Int {
return sum(row2 + 1, col2 + 1) - sum(row1, col2 + 1) - sum(row2 + 1, col1) + sum(row1, col1)
}
private func sum(_ row: Int, _ col: Int) -> Int {
var sum = 0
var i = row
while i > 0 {
var j = col
while j > 0 {
sum += bit[i][j]
j -= j & -j
}
i -= i & -i
}
return sum
}
}
96. Skyline Problem
func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
var points = [(Int, Int)]()
for building in buildings {
points.append((building[0], -building[2]))
points.append((building[1], building[2]))
}
points.sort { $0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0 }
var result = [[Int]]()
var heights = [0]
var prevMaxHeight = 0
for point in points {
if point.1 < 0 {
heights.append(-point.1)
} else {
if let index = heights.firstIndex(of: point.1) {
heights.remove(at: index)
}
}
let currentMaxHeight = heights.max()!
if currentMaxHeight != prevMaxHeight {
result.append([point.0, currentMaxHeight])
prevMaxHeight = currentMaxHeight
}
}
return result
}
97. Alien Dictionary
func alienOrder(_ words: [String]) -> String {
var graph = [Character: Set]()
var indegree = [Character: Int]()
for word in words {
for char in word {
graph[char] = Set()
indegree[char] = 0
}
}
for i in 0.. word2.count {
return ""
}
}
var queue = [Character]()
for (char, count) in indegree {
if count == 0 {
queue.append(char)
}
}
var result = ""
while !queue.isEmpty {
let char = queue.removeFirst()
result.append(char)
for neighbor in graph[char]! {
indegree[neighbor]! -= 1
if indegree[neighbor]! == 0 {
queue.append(neighbor)
}
}
}
return result.count == indegree.count ? result : ""
}
98. Number of Islands II
class UnionFind {
private var parent: [Int]
private var rank: [Int]
var count = 0
init(_ n: Int) {
parent = Array(0.. Int {
if p != parent[p] {
parent[p] = find(parent[p])
}
return parent[p]
}
func union(_ p: Int, _ q: Int) {
let rootP = find(p)
let rootQ = find(q)
if rootP == rootQ { return }
if rank[rootP] > rank[rootQ] {
parent[rootQ] = rootP
} else if rank[rootP] < rank[rootQ] {
parent[rootP] = rootQ
} else {
parent[rootQ] = rootP
rank[rootP] += 1
}
count -= 1
}
func addIsland() {
count += 1
}
}
func numIslands2(_ m: Int, _ n: Int, _ positions: [[Int]]) -> [Int] {
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
let uf = UnionFind(m * n)
var grid = Array(repeating: Array(repeating: 0, count: n), count: m)
var result = [Int]()
for position in positions {
let row = position[0]
let col = position[1]
if grid[row][col] == 1 {
result.append(uf.count)
continue
}
grid[row][col] = 1
let index = row * n + col
uf.addIsland()
for direction in directions {
let newRow = row + direction.0
let newCol = col + direction.1
if newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1 {
let newIndex = newRow * n + newCol
uf.union(index, newIndex)
}
}
result.append(uf.count)
}
return result
}
99. Find the Duplicate Number
func findDuplicate(_ nums: [Int]) -> Int {
var slow = nums[0]
var fast = nums[0]
repeat {
slow = nums[slow]
fast = nums[nums[fast]]
} while slow != fast
fast = nums[0]
while slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
100. Merge Intervals
func merge(_ intervals: [[Int]]) -> [[Int]] {
guard intervals.count > 1 else { return intervals }
let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
var result = [sortedIntervals[0]]
for interval in sortedIntervals[1...] {
let lastInterval = result.last!
if interval[0] <= lastInterval[1] {
result[result.count - 1][1] = max(lastInterval[1], interval[1])
} else {
result.append(interval)
}
}
return result
}
101. Longest Increasing Path in a Matrix
// Given a matrix, find the longest increasing path.
func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
guard matrix.count > 0 && matrix[0].count > 0 else { return 0 }
let rows = matrix.count
let cols = matrix[0].count
var memo = Array(repeating: Array(repeating: 0, count: cols), count: rows)
var maxLength = 0
// Directions for moving in the matrix
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
func dfs(_ row: Int, _ col: Int) -> Int {
if memo[row][col] != 0 { return memo[row][col] }
var maxPath = 1
for direction in directions {
let newRow = row + direction.0
let newCol = col + direction.1
if newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && matrix[newRow][newCol] > matrix[row][col] {
maxPath = max(maxPath, dfs(newRow, newCol) + 1)
}
}
memo[row][col] = maxPath
return maxPath
}
for row in 0..102. Number of Connected Components in an Undirected Graph
// Finds the number of connected components in an undirected graph.
func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
var parent = Array(0.. Int {
if parent[node] != node {
parent[node] = find(parent[node])
}
return parent[node]
}
func union(_ u: Int, _ v: Int) {
let rootU = find(u)
let rootV = find(v)
if rootU != rootV {
parent[rootU] = rootV
}
}
for edge in edges {
union(edge[0], edge[1])
}
var componentSet = Set()
for i in 0.. 103. Alien Dictionary (Advanced)
// Determines the order of characters in an alien language.
func alienOrder(_ words: [String]) -> String {
var graph = [Character: Set]()
var indegree = [Character: Int]()
// Initialize the graph and indegree for each character.
for word in words {
for char in word {
graph[char] = Set()
indegree[char] = 0
}
}
// Build the graph by comparing adjacent words.
for i in 0.. word2.count {
return ""
}
}
// Topological sort using Kahn's algorithm.
var queue = [Character]()
for (char, count) in indegree {
if count == 0 {
queue.append(char)
}
}
var result = ""
while !queue.isEmpty {
let char = queue.removeFirst()
result.append(char)
for neighbor in graph[char]! {
indegree[neighbor]! -= 1
if indegree[neighbor]! == 0 {
queue.append(neighbor)
}
}
}
return result.count == indegree.count ? result : ""
}
// Usage Example
let words = ["wrt", "wrf", "er", "ett", "rftt"]
print(alienOrder(words)) // Output: "wertf"
104. Course Schedule III
// Determines the maximum number of courses that can be taken.
func scheduleCourse(_ courses: [[Int]]) -> Int {
let sortedCourses = courses.sorted { $0[1] < $1[1] }
var totalTime = 0
var maxHeap = [Int]()
for course in sortedCourses {
totalTime += course[0]
maxHeap.append(course[0])
maxHeap.sort(by: >)
if totalTime > course[1] {
totalTime -= maxHeap.removeFirst()
}
}
return maxHeap.count
}
// Usage Example
let courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
print(scheduleCourse(courses)) // Output: 3
105. Network Delay Time
// Finds the time it takes for all nodes to receive the signal.
func networkDelayTime(_ times: [[Int]], _ N: Int, _ K: Int) -> Int {
var graph = [Int: [(Int, Int)]]()
for time in times {
graph[time[0], default: []].append((time[1], time[2]))
}
var dist = [Int: Int]()
for i in 1...N {
dist[i] = Int.max
}
dist[K] = 0
var heap = [(0, K)]
while !heap.isEmpty {
let (currentDist, node) = heap.removeFirst()
if currentDist > dist[node]! { continue }
if let neighbors = graph[node] {
for (neighbor, weight) in neighbors {
let newDist = currentDist + weight
if newDist < dist[neighbor]! {
dist[neighbor] = newDist
heap.append((newDist, neighbor))
heap.sort { $0.0 < $1.0 }
}
}
}
}
let maxDist = dist.values.max()!
return maxDist == Int.max ? -1 : maxDist
}
// Usage Example
let times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
let N = 4
let K = 2
print(networkDelayTime(times, N, K)) // Output: 2
106. Path With Minimum Effort
// Finds the minimum effort required to travel from the top-left to the bottom-right corner of a grid.
func minimumEffortPath(_ heights: [[Int]]) -> Int {
let rows = heights.count
let cols = heights[0].count
var left = 0
var right = 1_000_000
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
func canReach(_ maxEffort: Int) -> Bool {
var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
var queue = [(0, 0)]
visited[0][0] = true
while !queue.isEmpty {
let (row, col) = queue.removeFirst()
if row == rows - 1 && col == cols - 1 { return true }
for direction in directions {
let newRow = row + direction.0
let newCol = col + direction.1
if newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol] && abs(heights[newRow][newCol] - heights[row][col]) <= maxEffort {
visited[newRow][newCol] = true
queue.append((newRow, newCol))
}
}
}
return false
}
while left < right {
let mid = (left + right) / 2
if canReach(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
// Usage Example
let heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]
print(minimumEffortPath(heights)) // Output: 2
107. Redundant Connection
// Finds the redundant edge in a graph that makes it a tree.
func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
var parent = Array(0...edges.count)
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
func union(_ x: Int, _ y: Int) -> Bool {
let rootX = find(x)
let rootY = find(y)
if rootX == rootY { return false }
parent[rootX] = rootY
return true
}
for edge in edges {
if !union(edge[0], edge[1]) {
return edge
}
}
return []
}
// Usage Example
let edges = [[1, 2], [1, 3], [2, 3]]
print(findRedundantConnection(edges)) // Output: [2, 3]
108. Critical Connections in a Network
// Finds all critical connections in a network (bridges in a graph).
func criticalConnections(_ n: Int, _ connections: [[Int]]) -> [[Int]] {
var graph = Array(repeating: [Int](), count: n)
for connection in connections {
graph[connection[0]].append(connection[1])
graph[connection[1]].append(connection[0])
}
var discovery = Array(repeating: -1, count: n)
var lowest = Array(repeating: 0, count: n)
var result = [[Int]]()
var time = 0
func dfs(_ node: Int, _ parent: Int) {
discovery[node] = time
lowest[node] = time
time += 1
for neighbor in graph[node] {
if neighbor == parent { continue }
if discovery[neighbor] == -1 {
dfs(neighbor, node)
lowest[node] = min(lowest[node], lowest[neighbor])
if lowest[neighbor] > discovery[node] {
result.append([node, neighbor])
}
} else {
lowest[node] = min(lowest[node], discovery[neighbor])
}
}
}
for i in 0..109. Surrounded Regions
// Flips all 'O's on the border and connected to the border to 'X's.
func solve(_ board: inout [[Character]]) {
let rows = board.count
let cols = board[0].count
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
func dfs(_ row: Int, _ col: Int) {
if row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != "O" {
return
}
board[row][col] = "T"
for direction in directions {
dfs(row + direction.0, col + direction.1)
}
}
// Mark 'O's on the border and connected to the border.
for row in 0..110. Longest Consecutive Sequence
// Finds the longest consecutive elements sequence.
func longestConsecutive(_ nums: [Int]) -> Int {
let numSet = Set(nums)
var longest = 0
for num in numSet {
if !numSet.contains(num - 1) {
var currentNum = num
var currentStreak = 1
while numSet.contains(currentNum + 1) {
currentNum += 1
currentStreak += 1
}
longest = max(longest, currentStreak)
}
}
return longest
}
// Usage Example
let nums = [100, 4, 200, 1, 3, 2]
print(longestConsecutive(nums)) // Output: 4
111. Word Search
// Searches for a word in a 2D board of characters.
func exist(_ board: [[Character]], _ word: String) -> Bool {
let rows = board.count
let cols = board[0].count
let wordArray = Array(word)
func dfs(_ row: Int, _ col: Int, _ index: Int) -> Bool {
if index == wordArray.count { return true }
if row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != wordArray[index] {
return false
}
var tempBoard = board
tempBoard[row][col] = "#"
let found = dfs(row + 1, col, index + 1) ||
dfs(row - 1, col, index + 1) ||
dfs(row, col + 1, index + 1) ||
dfs(row, col - 1, index + 1)
return found
}
for row in 0..112. Maximal Rectangle
// Finds the largest rectangle containing only 1's in a 2D binary matrix.
func maximalRectangle(_ matrix: [[Character]]) -> Int {
guard matrix.count > 0 else { return 0 }
let rows = matrix.count
let cols = matrix[0].count
var heights = Array(repeating: 0, count: cols)
var maxArea = 0
for row in matrix {
for col in 0.. Int {
var stack = [-1]
var maxArea = 0
for i in 0..= heights[i] {
let height = heights[stack.removeLast()]
let width = i - stack.last! - 1
maxArea = max(maxArea, height * width)
}
stack.append(i)
}
while stack.last != -1 {
let height = heights[stack.removeLast()]
let width = heights.count - stack.last! - 1
maxArea = max(maxArea, height * width)
}
return maxArea
}
// Usage Example
let matrix: [[Character]] = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
print(maximalRectangle(matrix)) // Output: 6
113. Binary Tree Maximum Path Sum
// Finds the maximum path sum in a binary tree.
func maxPathSum(_ root: TreeNode?) -> Int {
var maxSum = Int.min
func maxGain(_ node: TreeNode?) -> Int {
guard let node = node else { return 0 }
let leftGain = max(maxGain(node.left), 0)
let rightGain = max(maxGain(node.right), 0)
let priceNewPath = node.val + leftGain + rightGain
maxSum = max(maxSum, priceNewPath)
return node.val + max(leftGain, rightGain)
}
_ = maxGain(root)
return maxSum
}
// Usage Example
let root = TreeNode(1, TreeNode(2), TreeNode(3))
print(maxPathSum(root)) // Output: 6
114. Merge k Sorted Lists
// Merges k sorted linked lists into one sorted linked list.
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
guard lists.count > 0 else { return nil }
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(0)
var current: ListNode? = dummy
var l1 = l1
var l2 = l2
while l1 != nil && l2 != nil {
if l1!.val < l2!.val {
current!.next = l1
l1 = l1!.next
} else {
current!.next = l2
l2 = l2!.next
}
current = current!.next
}
current!.next = l1 ?? l2
return dummy.next
}
func merge(_ lists: [ListNode?], _ left: Int, _ right: Int) -> ListNode? {
if left == right { return lists[left] }
let mid = (left + right) / 2
let l1 = merge(lists, left, mid)
let l2 = merge(lists, mid + 1, right)
return mergeTwoLists(l1, l2)
}
return merge(lists, 0, lists.count - 1)
}
// Usage Example
// Assuming `ListNode` class is defined, as well as helper functions for building lists.
115. Find Median from Data Stream
// Finds the median from a data stream of integers.
class MedianFinder {
var low = [Int]() // Max heap
var high = [Int]() // Min heap
func addNum(_ num: Int) {
if low.isEmpty || num <= low[0] {
low.append(num)
low.sort(by: >)
} else {
high.append(num)
high.sort(by: <)
}
balanceHeaps()
}
func findMedian() -> Double {
if low.count > high.count {
return Double(low[0])
} else {
return Double(low[0] + high[0]) / 2.0
}
}
private func balanceHeaps() {
if low.count > high.count + 1 {
high.append(low.removeFirst())
high.sort(by: <)
} else if high.count > low.count {
low.append(high.removeFirst())
low.sort(by: >)
}
}
}
// Usage Example
let finder = MedianFinder()
finder.addNum(1)
finder.addNum(2)
print(finder.findMedian()) // Output: 1.5
finder.addNum(3)
print(finder.findMedian()) // Output: 2.0
116. Sliding Window Maximum
// Finds the maximum value in each sliding window of size k.
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
var result = [Int]()
var deque = [Int]()
for i in 0..= k - 1 {
result.append(nums[deque.first!])
}
}
return result
}
// Usage Example
let nums = [1,3,-1,-3,5,3,6,7]
let k = 3
print(maxSlidingWindow(nums, k)) // Output: [3,3,5,5,6,7]
117. First Missing Positive
// Finds the smallest missing positive integer.
func firstMissingPositive(_ nums: [Int]) -> Int {
var nums = nums
let n = nums.count
for i in 0.. 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i] {
nums.swapAt(i, nums[i] - 1)
}
}
for i in 0.. 118. Trapping Rain Water
// Finds the amount of water that can be trapped after raining.
func trap(_ height: [Int]) -> Int {
guard height.count > 2 else { return 0 }
var left = 0, right = height.count - 1
var leftMax = 0, rightMax = 0
var water = 0
while left < right {
if height[left] < height[right] {
if height[left] >= leftMax {
leftMax = height[left]
} else {
water += leftMax - height[left]
}
left += 1
} else {
if height[right] >= rightMax {
rightMax = height[right]
} else {
water += rightMax - height[right]
}
right -= 1
}
}
return water
}
// Usage Example
let height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height)) // Output: 6
119. Best Time to Buy and Sell Stock with Cooldown
// Finds the maximum profit with cooldown periods.
func maxProfit(_ prices: [Int]) -> Int {
guard prices.count > 1 else { return 0 }
var sold = 0, held = Int.min, rest = 0
for price in prices {
let prevSold = sold
sold = held + price
held = max(held, rest - price)
rest = max(rest, prevSold)
}
return max(sold, rest)
}
// Usage Example
let prices = [1,2,3,0,2]
print(maxProfit(prices)) // Output: 3
120. Word Break II
// Finds all possible sentences from a string that can be segmented into a space-separated sequence of dictionary words.
func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
let wordSet = Set(wordDict)
var memo = [String: [String]]()
func backtrack(_ s: String) -> [String] {
if let result = memo[s] { return result }
if s.isEmpty { return [""] }
var result = [String]()
for word in wordSet {
if s.hasPrefix(word) {
let subResults = backtrack(String(s.dropFirst(word.count)))
for subResult in subResults {
result.append(word + (subResult.isEmpty ? "" : " ") + subResult)
}
}
}
memo[s] = result
return result
}
return backtrack(s)
}
// Usage Example
let s = "catsanddog"
let wordDict = ["cat", "cats", "and", "sand", "dog"]
print(wordBreak(s, wordDict)) // Output: ["cats and dog", "cat sand dog"]
121. Largest Rectangle in Histogram
// Finds the largest rectangle that can be formed in a histogram.
func largestRectangleArea(_ heights: [Int]) -> Int {
var stack = [-1]
var maxArea = 0
for i in 0..= heights[i] {
let height = heights[stack.removeLast()]
let width = i - stack.last! - 1
maxArea = max(maxArea, height * width)
}
stack.append(i)
}
while stack.last != -1 {
let height = heights[stack.removeLast()]
let width = heights.count - stack.last! - 1
maxArea = max(maxArea, height * width)
}
return maxArea
}
// Usage Example
let heights = [2,1,5,6,2,3]
print(largestRectangleArea(heights)) // Output: 10
122. Decode Ways II
// Decodes a string of digits with '*' wildcards into possible letter combinations.
func numDecodings(_ s: String) -> Int {
let mod = 1_000_000_007
var dp = [1, 0, 0] // dp[i % 3]: i-th step with s[i]
for char in s {
var currentDp = Array(repeating: 0, count: 3)
if char == "*" {
currentDp[0] = 9 * dp[0] % mod
currentDp[0] = (currentDp[0] + 9 * dp[1] % mod) % mod
} else {
let num = Int(String(char))!
currentDp[0] = (dp[0] * (num > 0 ? 1 : 0)) % mod
}
dp = currentDp
}
return dp[0]
}
// Usage Example
let s = "1*"
print(numDecodings(s)) // Output: 18
123. Shortest Path to Get All Keys
// Finds the shortest path to collect all keys in a grid.
func shortestPathAllKeys(_ grid: [String]) -> Int {
let rows = grid.count
let cols = grid[0].count
var start: (row: Int, col: Int) = (0, 0)
var allKeys = 0
for row in 0..()
visited.insert("\(start.row)-\(start.col)-0")
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while !queue.isEmpty {
let (row, col, keys, steps) = queue.removeFirst()
for direction in directions {
let newRow = row + direction.0
let newCol = col + direction.1
guard newRow >= 0, newRow < rows, newCol >= 0, newCol < cols else { continue }
let char = grid[newRow][grid[newRow].index(grid[newRow].startIndex, offsetBy: newCol)]
if char == "#" { continue }
var newKeys = keys
if char.isLowercase {
newKeys |= 1 << (char.asciiValue! - Character("a").asciiValue!)
}
if newKeys == allKeys { return steps + 1 }
if char.isUppercase && (newKeys & (1 << (char.asciiValue! - Character("A").asciiValue!))) == 0 {
continue
}
let state = "\(newRow)-\(newCol)-\(newKeys)"
if !visited.contains(state) {
visited.insert(state)
queue.append((newRow, newCol, newKeys, steps + 1))
}
}
}
return -1
}
// Usage Example
let grid = ["@.a.#", "###.#", "b.A.B"]
print(shortestPathAllKeys(grid)) // Output: 8
124. Swim in Rising Water
// Finds the minimum time required to swim from the top-left corner to the bottom-right corner.
func swimInWater(_ grid: [[Int]]) -> Int {
let n = grid.count
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var minTime = 0
var queue = [(0, 0)]
visited[0][0] = true
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while !queue.isEmpty {
minTime = grid[queue[0].0][queue[0].1]
var nextQueue = [(Int, Int)]()
for (row, col) in queue {
if row == n - 1 && col == n - 1 { return minTime }
for direction in directions {
let newRow = row + direction.0
let newCol = col + direction.1
if newRow >= 0, newRow < n, newCol >= 0, newCol < n, !visited[newRow][newCol], grid[newRow][newCol] <= minTime {
visited[newRow][newCol] = true
nextQueue.append((newRow, newCol))
}
}
}
queue = nextQueue
minTime += 1
}
return minTime
}
// Usage Example
let grid = [[0, 2], [1, 3]]
print(swimInWater(grid)) // Output: 3
125. Cherry Pickup II
// Collects the maximum number of cherries in a 2D grid with two robots.
func cherryPickup(_ grid: [[Int]]) -> Int {
let rows = grid.count
let cols = grid[0].count
var dp = Array(repeating: Array(repeating: Array(repeating: -1, count: cols), count: cols), count: rows)
func dfs(_ row: Int, _ col1: Int, _ col2: Int) -> Int {
if col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols { return 0 }
if dp[row][col1][col2] != -1 { return dp[row][col1][col2] }
var result = 0
result += grid[row][col1]
if col1 != col2 { result += grid[row][col2] }
if row != rows - 1 {
var maxValue = 0
for newCol1 in col1 - 1...col1 + 1 {
for newCol2 in col2 - 1...col2 + 1 {
maxValue = max(maxValue, dfs(row + 1, newCol1, newCol2))
}
}
result += maxValue
}
dp[row][col1][col2] = result
return result
}
return dfs(0, 0, cols - 1)
}
// Usage Example
let grid = [[3, 1, 1], [2, 5, 1], [1, 5, 5], [2, 1, 1]]
print(cherryPickup(grid)) // Output: 24
126. Maximum Points You Can Obtain from Cards
// Finds the maximum number of points you can obtain from cards.
func maxScore(_ cardPoints: [Int], _ k: Int) -> Int {
let totalSum = cardPoints.reduce(0, +)
let windowSize = cardPoints.count - k
var windowSum = cardPoints[0..127. Stone Game III
// Determines the winner of the stone game III.
func stoneGameIII(_ stoneValue: [Int]) -> String {
let n = stoneValue.count
var dp = Array(repeating: Int.min, count: n + 1)
dp[n] = 0
for i in (0.. 0 {
return "Alice"
} else if dp[0] < 0 {
return "Bob"
} else {
return "Tie"
}
}
// Usage Example
let stoneValue = [1, 2, 3, 7]
print(stoneGameIII(stoneValue)) // Output: "Bob"
128. Jump Game VI
// Finds the maximum score to reach the last index of the array.
func maxResult(_ nums: [Int], _ k: Int) -> Int {
var deque = [0]
var dp = nums
for i in 1..129. Minimum Difficulty of a Job Schedule
// Finds the minimum difficulty to schedule the jobs.
func minDifficulty(_ jobDifficulty: [Int], _ d: Int) -> Int {
let n = jobDifficulty.count
if n < d { return -1 }
var dp = Array(repeating: Array(repeating: Int.max, count: n), count: d)
dp[0][0] = jobDifficulty[0]
for j in 1..130. Minimum Number of Refueling Stops
// Finds the minimum number of refueling stops required to reach the target distance.
func minRefuelStops(_ target: Int, _ startFuel: Int, _ stations: [[Int]]) -> Int {
var dp = [startFuel]
for i in 0..= location {
if dp.count > j + 1 {
dp[j + 1] = max(dp[j + 1], dp[j] + fuel)
} else {
dp.append(dp[j] + fuel)
}
}
}
for i in 0..= target {
return i
}
}
return -1
}
// Usage Example
let target = 100
let startFuel = 50
let stations = [[25, 25], [50, 50]]
print(minRefuelStops(target, startFuel, stations)) // Output: 1
131. Number of Ways to Paint N × 3 Grid
// Finds the number of ways to paint a 3-column grid.
func numOfWays(_ n: Int) -> Int {
let mod = 1_000_000_007
var color2 = 6
var color3 = 6
for _ in 1..132. Number of Ways to Arrive at Destination
// Finds the number of ways to arrive at the destination.
func countPaths(_ n: Int, _ roads: [[Int]]) -> Int {
let mod = 1_000_000_007
var graph = [Int: [(Int, Int)]]()
for road in roads {
let (u, v, t) = (road[0], road[1], road[2])
graph[u, default: []].append((v, t))
graph[v, default: []].append((u, t))
}
var dist = Array(repeating: Int.max, count: n)
var ways = Array(repeating: 0, count: n)
dist[0] = 0
ways[0] = 1
var queue = [(0, 0)] // (node, dist)
while !queue.isEmpty {
let (node, d) = queue.removeFirst()
if d > dist[node] { continue }
for (neighbor, time) in graph[node, default: []] {
let newDist = d + time
if newDist < dist[neighbor] {
dist[neighbor] = newDist
ways[neighbor] = ways[node]
queue.append((neighbor, newDist))
} else if newDist == dist[neighbor] {
ways[neighbor] = (ways[neighbor] + ways[node]) % mod
}
}
}
return ways[n - 1]
}
// Usage Example
let n = 7
let roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
print(countPaths(n, roads)) // Output: 4
133. Minimum Initial Energy to Finish Tasks
// Finds the minimum initial energy required to finish all tasks.
func minimumEffort(_ tasks: [[Int]]) -> Int {
let sortedTasks = tasks.sorted { ($0[1] - $0[0]) > ($1[1] - $1[0]) }
var totalEnergy = 0
var result = 0
for task in sortedTasks {
let (actual, minEnergy) = (task[0], task[1])
totalEnergy = max(totalEnergy + actual, minEnergy)
result = max(result, totalEnergy)
}
return result
}
// Usage Example
let tasks = [[1,2],[2,4],[4,8]]
print(minimumEffort(tasks)) // Output: 8
134. Stone Game VII
// Finds the maximum difference in scores Alice can obtain in the Stone Game VII.
func stoneGameVII(_ stones: [Int]) -> Int {
let n = stones.count
var prefixSum = [0]
for stone in stones {
prefixSum.append(prefixSum.last! + stone)
}
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for length in 2...n {
for i in 0...(n - length) {
let j = i + length - 1
dp[i][j] = max(prefixSum[j + 1] - prefixSum[i + 1] - dp[i + 1][j],
prefixSum[j] - prefixSum[i] - dp[i][j - 1])
}
}
return dp[0][n - 1]
}
// Usage Example
let stones = [5,3,1,4,2]
print(stoneGameVII(stones)) // Output: 6
135. Super Egg Drop
// Finds the minimum number of attempts to find the critical floor.
func superEggDrop(_ k: Int, _ n: Int) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1)
var attempts = 0
while dp[attempts][k] < n {
attempts += 1
for j in 1...k {
dp[attempts][j] = dp[attempts - 1][j - 1] + dp[attempts - 1][j] + 1
}
}
return attempts
}
// Usage Example
let k = 2
let n = 100
print(superEggDrop(k, n)) // Output: 14
136. Word Ladder II
// Finds all shortest transformation sequences from the start word to the end word.
func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
let wordSet = Set(wordList)
if !wordSet.contains(endWord) { return [] }
var queue = [[beginWord]]
var result = [[String]]()
var levelVisited = Set()
var visited = Set()
visited.insert(beginWord)
var found = false
// BFS to find all the shortest paths
while !queue.isEmpty && !found {
var nextLevel = [[String]]()
for path in queue {
let word = path.last!
var chars = Array(word)
// Try changing each character
for i in 0.. 137. Find the City with the Smallest Number of Neighbors at a Threshold Distance
// Finds the city with the smallest number of neighbors within a threshold distance.
func findTheCity(_ n: Int, _ edges: [[Int]], _ distanceThreshold: Int) -> Int {
var dist = Array(repeating: Array(repeating: Int.max / 2, count: n), count: n)
for edge in edges {
dist[edge[0]][edge[1]] = edge[2]
dist[edge[1]][edge[0]] = edge[2]
}
for i in 0..138. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
// Finds the maximum area of a piece of cake after horizontal and vertical cuts.
func maxArea(_ h: Int, _ w: Int, _ horizontalCuts: [Int], _ verticalCuts: [Int]) -> Int {
let mod = 1_000_000_007
let maxH = (horizontalCuts + [0, h]).sorted().zip().map { $0.1 - $0.0 }.max()!
let maxW = (verticalCuts + [0, w]).sorted().zip().map { $0.1 - $0.0 }.max()!
return maxH * maxW % mod
}
// Usage Example
let h = 5
let w = 4
let horizontalCuts = [1, 2, 4]
let verticalCuts = [1, 3]
print(maxArea(h, w, horizontalCuts, verticalCuts)) // Output: 4
139. Minimum Cost to Make at Least One Valid Path in a Grid
// Finds the minimum cost to make at least one valid path in a grid.
func minCost(_ grid: [[Int]]) -> Int {
let rows = grid.count
let cols = grid[0].count
var cost = Array(repeating: Array(repeating: Int.max, count: cols), count: rows)
var deque = [(0, 0, 0)]
let directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
cost[0][0] = 0
while !deque.isEmpty {
let (row, col, currCost) = deque.removeFirst()
for i in 0..<4 0="" 1="" :="" col="" directions="" grid="" i="" if="" let="" newcol="col" newcost="currCost" newrow="" row="">= 0, newRow < rows, newCol >= 0, newCol < cols, newCost < cost[newRow][newCol] {
cost[newRow][newCol] = newCost
deque.append((newRow, newCol, newCost))
}
}
}
return cost[rows - 1][cols - 1]
}
// Usage Example
let grid = [[1, 1, 3], [3, 2, 2], [1, 1, 4]]
print(minCost(grid)) // Output: 0
140. Count Vowels Permutation
// Finds the number of possible vowel permutations of length n.
func countVowelPermutation(_ n: Int) -> Int {
let mod = 1_000_000_007
var dp = [1, 1, 1, 1, 1]
for _ in 1..141. Minimum Number of Flips to Make the Binary String Alternating
// Finds the minimum number of flips to make the binary string alternating.
func minFlips(_ s: String) -> Int {
let n = s.count
let sArray = Array(s + s)
let alt1 = Array(repeating: "01", count: n + 1).joined()
let alt2 = Array(repeating: "10", count: n + 1).joined()
var result = n
var diff1 = 0
var diff2 = 0
for i in 0..<2 1="" alt1="" alt2="" diff1="" diff2="" i="" if="" n="" sarray="">= n {
if sArray[i - n] != alt1[i - n] { diff1 -= 1 }
if sArray[i - n] != alt2[i - n] { diff2 -= 1 }
}
if i >= n - 1 {
result = min(result, min(diff1, diff2))
}
}
return result
}
// Usage Example
let s = "111000"
print(minFlips(s)) // Output: 2
142. Minimum XOR Sum of Two Arrays
// Finds the minimum XOR sum of two arrays.
func minimumXORSum(_ nums1: [Int], _ nums2: [Int]) -> Int {
let n = nums1.count
var dp = Array(repeating: Int.max, count: 1 << n)
dp[0] = 0
for mask in 0..<(1 << n) {
let count = mask.nonzeroBitCount
for i in 0..143. Minimum Falling Path Sum II
// Finds the minimum falling path sum in a 2D array, with no two elements from the same column.
func minFallingPathSum(_ arr: [[Int]]) -> Int {
let rows = arr.count
let cols = arr[0].count
var dp = arr[0]
for row in 1..144. Cherry Pickup
// Finds the maximum number of cherries two people can collect from a grid.
func cherryPickup(_ grid: [[Int]]) -> Int {
let n = grid.count
var dp = Array(repeating: Array(repeating: Array(repeating: -1, count: n), count: n), count: n)
func dfs(_ r1: Int, _ c1: Int, _ r2: Int) -> Int {
let c2 = r1 + c1 - r2
if r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1 {
return Int.min
}
if r1 == n - 1 && c1 == n - 1 { return grid[r1][c1] }
if dp[r1][c1][r2] != -1 { return dp[r1][c1][r2] }
var result = grid[r1][c1]
if r1 != r2 { result += grid[r2][c2] }
result += max(dfs(r1 + 1, c1, r2 + 1), dfs(r1, c1 + 1, r2 + 1), dfs(r1 + 1, c1, r2), dfs(r1, c1 + 1, r2))
dp[r1][c1][r2] = result
return result
}
return max(0, dfs(0, 0, 0))
}
// Usage Example
let grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]
print(cherryPickup(grid)) // Output: 5
145. Best Time to Buy and Sell Stock IV
// Finds the maximum profit with at most k transactions.
func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
let n = prices.count
if n == 0 { return 0 }
// If k is greater than half the number of days, treat as unlimited transactions.
if k > n / 2 {
return prices.reduce(0) { acc, price in
acc + max(price - acc, 0)
}
}
var dp = Array(repeating: Array(repeating: 0, count: n), count: k + 1)
var i = 1
while i <= k {
var maxProfit = -prices[0]
var j = 1
while j < n {
dp[i][j] = max(dp[i][j - 1], prices[j] + maxProfit)
maxProfit = max(maxProfit, dp[i - 1][j] - prices[j])
j += 1
}
i += 1
}
return dp[k][n - 1]
}
// Usage Example
let prices = [3, 2, 6, 5, 0, 3]
let k = 2
print(maxProfit(k, prices)) // Output: 7
146. Maximum Profit in Job Scheduling
// Finds the maximum profit in non-overlapping job scheduling.
func jobScheduling(_ startTime: [Int], _ endTime: [Int], _ profit: [Int]) -> Int {
let n = startTime.count
var jobs = [(startTime: Int, endTime: Int, profit: Int)]()
// Create jobs array with start, end, and profit.
var i = 0
while i < n {
jobs.append((startTime[i], endTime[i], profit[i]))
i += 1
}
// Sort jobs by end time.
jobs.sort { $0.endTime < $1.endTime }
var dp = Array(repeating: 0, count: n)
dp[0] = jobs[0].profit
func binarySearch(_ index: Int) -> Int {
var low = 0
var high = index - 1
while low <= high {
let mid = (low + high) / 2
if jobs[mid].endTime <= jobs[index].startTime {
if jobs[mid + 1].endTime <= jobs[index].startTime {
low = mid + 1
} else {
return mid
}
} else {
high = mid - 1
}
}
return -1
}
i = 1
while i < n {
let includeProfit = jobs[i].profit
let lastNonConflictJob = binarySearch(i)
if lastNonConflictJob != -1 {
dp[i] = max(dp[i - 1], includeProfit + dp[lastNonConflictJob])
} else {
dp[i] = max(dp[i - 1], includeProfit)
}
i += 1
}
return dp[n - 1]
}
// Usage Example
let startTime = [1, 2, 3, 3]
let endTime = [3, 4, 5, 6]
let profit = [50, 10, 40, 70]
print(jobScheduling(startTime, endTime, profit)) // Output: 120
147. Parallel Courses
// Finds the minimum number of semesters to take all courses.
func minimumSemesters(_ n: Int, _ relations: [[Int]]) -> Int {
var graph = Array(repeating: [Int](), count: n + 1)
var indegree = Array(repeating: 0, count: n + 1)
for relation in relations {
graph[relation[0]].append(relation[1])
indegree[relation[1]] += 1
}
var queue = [Int]()
for i in 1...n {
if indegree[i] == 0 {
queue.append(i)
}
}
var semesters = 0
var coursesTaken = 0
while !queue.isEmpty {
var nextQueue = [Int]()
for course in queue {
coursesTaken += 1
for nextCourse in graph[course] {
indegree[nextCourse] -= 1
if indegree[nextCourse] == 0 {
nextQueue.append(nextCourse)
}
}
}
queue = nextQueue
semesters += 1
}
return coursesTaken == n ? semesters : -1
}
// Usage Example
let n = 3
let relations = [[1, 3], [2, 3]]
print(minimumSemesters(n, relations)) // Output: 2
148. Maximum Building Height
// Finds the maximum possible height of buildings.
func maxBuilding(_ n: Int, _ restrictions: [[Int]]) -> Int {
var res = restrictions + [[1, 0], [n, n - 1]]
res.sort { $0[0] < $1[0] }
// First pass to limit height from left to right.
for i in 1..149. Find Kth Smallest Pair Distance
// Finds the kth smallest pair distance.
func smallestDistancePair(_ nums: [Int], _ k: Int) -> Int {
let sortedNums = nums.sorted()
func countPairs(withDiffLessOrEqualTo diff: Int) -> Int {
var count = 0
var left = 0
for right in 1.. diff {
left += 1
}
count += right - left
}
return count
}
var low = 0
var high = sortedNums.last! - sortedNums.first!
while low < high {
let mid = (low + high) / 2
if countPairs(withDiffLessOrEqualTo: mid) < k {
low = mid + 1
} else {
high = mid
}
}
return low
}
// Usage Example
let nums = [1, 3, 1]
let k = 1
print(smallestDistancePair(nums, k)) // Output: 0
150. Number of Good Ways to Split a String
// Finds the number of good ways to split a string using while loops.
func numSplits(_ s: String) -> Int {
var leftSet = Set()
var rightSet = Set(s)
var leftCount = [Int]()
var rightCount = [Int]()
// Use a while loop to iterate through the string from left to right.
var i = 0
while i < s.count {
let char = s[s.index(s.startIndex, offsetBy: i)]
leftSet.insert(char)
leftCount.append(leftSet.count)
i += 1
}
// Use a while loop to iterate through the string from right to left.
i = s.count - 1
while i >= 0 {
let char = s[s.index(s.startIndex, offsetBy: i)]
rightSet.insert(char)
rightCount.append(rightSet.count)
i -= 1
}
rightCount.reverse()
var result = 0
i = 0
// Use a while loop to compare leftCount and rightCount.
while i < s.count - 1 {
if leftCount[i] == rightCount[i + 1] {
result += 1
}
i += 1
}
return result
}
// Usage Example
let s = "aacaba"
print(numSplits(s)) // Output: 2
Sign up here with your email
ConversionConversion EmoticonEmoticon