Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

class Solution {
    func numSteps(_ s: String) -> Int {
        var str = Array(s)
        var operations = 0

        while str.count > 1 {
            if str.last == "0" {
                str.removeLast()
            } else {
                var i = str.count - 1
                while i >= 0 && str[i] == "1" {
                    str[i] = "0"
                    i -= 1
                }
                if i < 0 {
                    str.insert("1", at: 0)
                } else {
                    str[i] = "1"
                }
            }
            operations += 1
        }

        return operations
    }
}

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { 
        self.val = val 
        self.left = nil
        self.right = nil
    }
}

class FindElements {
    private var root: TreeNode?
    private var values: Set<Int>
    
    init(_ root: TreeNode?) {
        self.root = root
        self.values = Set<Int>()
        if let root = root {
            root.val = 0
            values.insert(0)
            recover(root)
        }
    }
    
    private func recover(_ node: TreeNode) {
        if let left = node.left {
            left.val = 2 * node.val + 1
            values.insert(left.val)
            recover(left)
        }
        if let right = node.right {
            right.val = 2 * node.val + 2
            values.insert(right.val)
            recover(right)
        }
    }
    
    func find(_ target: Int) -> Bool {
        return values.contains(target)
    }
}

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

class Solution {
    func isBipartite(_ graph: [[Int]]) -> Bool {
        var color = [Int: Int]()
        for node in 0..<graph.count {
            if color[node] == nil {
                var stack = [node]
                color[node] = 0
                while !stack.isEmpty {
                    let node = stack.removeLast()
                    for nei in graph[node] {
                        if color[nei] == nil {
                            stack.append(nei)
                            color[nei] = color[node]! ^ 1
                        } else if color[nei] == color[node] {
                            return false
                        }
                    }
                }
            }
        }
        return true
    }
}

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

class Solution {
    func mostCompetitive(_ nums: [Int], _ k: Int) -> [Int] {
        var queue = [Int]()
        var additionalCount = nums.count - k
        
        for num in nums {
            while !queue.isEmpty && queue.last! > num && additionalCount > 0 {
                queue.removeLast()
                additionalCount -= 1
            }
            queue.append(num)
        }
        
        return Array(queue.prefix(k))
    }
}

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

class Solution {
    func generateSentences(_ synonyms: [[String]], _ text: String) -> [String] {
        var graph = [String: Set<String>]()

        for pair in synonyms {
            graph[pair[0], default: Set()].insert(pair[1])
            graph[pair[1], default: Set()].insert(pair[0])
        }

        let words = text.split(separator: " ").map { String($0) }
        var synonymGroups = [[String]]()
        for word in words {
            synonymGroups.append(findSynonyms(graph, word))
        }

        var sentences = [String]()
        var sentence = ""
        generate(&sentences, synonymGroups, &sentence, 0)
        return sentences.sorted()
    }

    private func findSynonyms(_ graph: [String: Set<String>], _ word: String) -> [String] {
        var synonyms = Set<String>()
        var stack = [word]
        while !stack.isEmpty {
            let w = stack.removeLast()
            if synonyms.insert(w).inserted {
                for neighbor in graph[w] ?? [] {
                    stack.append(neighbor)
                }
            }
        }
        return Array(synonyms).sorted()
    }

    private func generate(_ sentences: inout [String], _ groups: [[String]], _ sentence: inout String, _ index: Int) {
        if index == groups.count {
            sentences.append(sentence.trimmingCharacters(in: .whitespaces))
            return
        }
        for word in groups[index] {
            let original = sentence
            sentence += " " + word
            generate(&sentences, groups, &sentence, index + 1)
            sentence = original
        }
    }
}

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

class Solution {
    func checkPossibility(_ nums: [Int]) -> Bool {
        var nums = nums
        var count = 0
        
        for i in 1..<nums.count {
            if nums[i] < nums[i - 1] {
                if count > 0 {
                    return false
                }
                count += 1
                if i == 1 || nums[i] >= nums[i - 2] {
                    nums[i - 1] = nums[i]
                } else {
                    nums[i] = nums[i - 1]
                }
            }
        }
        
        return true
    }
}

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
}

class Solution {
    func getAllElements(_ root1: TreeNode?, _ root2: TreeNode?) -> [Int] {
        var stack1 = [TreeNode](), stack2 = [TreeNode]()
        var output = [Int]()
        var root1 = root1
        var root2 = root2

        while root1 != nil || root2 != nil || !stack1.isEmpty || !stack2.isEmpty {
            while root1 != nil {
                stack1.append(root1!)
                root1 = root1!.left
            }
            while root2 != nil {
                stack2.append(root2!)
                root2 = root2!.left
            }
            if stack2.isEmpty || (!stack1.isEmpty && stack1.last!.val <= stack2.last!.val) {
                root1 = stack1.removeLast()
                output.append(root1!.val)
                root1 = root1!.right
            } else {
                root2 = stack2.removeLast()
                output.append(root2!.val)
                root2 = root2!.right
            }
        }
        return output
    }
}

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

func addBoldTags(_ keywords: [String], _ s: String) -> String {
    var bold = Array(repeating: false, count: s.count)
    let sArray = Array(s)
    
    for word in keywords {
        var start = s.range(of: word)
        while start != nil {
            let range = start!.lowerBound..<s.index(start!.lowerBound, offsetBy: word.count)
            for i in range {
                bold[s.distance(from: s.startIndex, to: i)] = true
            }
            start = s.range(of: word, range: range.upperBound..<s.endIndex)
        }
    }
    
    var result = ""
    var i = 0
    while i < s.count {
        if bold[i] {
            result += "<b>"
            while i < s.count && bold[i] {
                result.append(sArray[i])
                i += 1
            }
            result += "</b>"
        } else {
            result.append(sArray[i])
            i += 1
        }
    }
    
    return result
}

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

class Solution {
    func videoStitching(_ clips: [[Int]], _ T: Int) -> Int {
        let clips = clips.sorted { $0[0] < $1[0] || ($0[0] == $1[0] && $0[1] > $1[1]) }
        var end = -1, end2 = 0, res = 0
        
        for clip in clips {
            if end2 >= T || clip[0] > end2 {
                break
            } else if end < clip[0] && clip[0] <= end2 {
                res += 1
                end = end2
            }
            end2 = max(end2, clip[1])
        }
        return end2 >= T ? res : -1
    }
}

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

class Solution {
    func longestSubsequence(_ arr: [Int], _ difference: Int) -> Int {
        var dp = [Int: Int]()
        var answer = 1
        
        for a in arr {
            let beforeA = dp[a - difference, default: 0]
            dp[a] = beforeA + 1
            answer = max(answer, dp[a]!)
        }
        
        return answer
    }
}

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

class Solution {
    func advantageCount(_ A: [Int], _ B: [Int]) -> [Int] {
        let sortedA = A.sorted()
        let sortedB = B.enumerated().sorted { $0.element < $1.element }
        var assigned = [Int: [Int]]()
        var remaining = [Int]()
        
        var j = 0
        for a in sortedA {
            if a > sortedB[j].element {
                assigned[sortedB[j].element, default: []].append(a)
                j += 1
            } else {
                remaining.append(a)
            }
        }
        
        var result = [Int]()
        for b in B {
            if let val = assigned[b]?.popLast() {
                result.append(val)
            } else {
                result.append(remaining.popLast()!)
            }
        }
        return result
    }
}

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

class Solution {
    func minMalwareSpread(_ graph: [[Int]], _ initial: [Int]) -> Int {
        func dfs(_ node: Int, _ infected: inout Set<Int>) {
            for neighbor in 0..<graph.count {
                if graph[node][neighbor] == 1 && !infected.contains(neighbor) {
                    infected.insert(neighbor)
                    dfs(neighbor, &infected)
                }
            }
        }

        let n = graph.count
        var initialSet = Set(initial)
        let sortedInitial = initial.sorted()
        var minInfected = Int.max
        var bestNode = sortedInitial[0]
        
        for node in sortedInitial {
            var infected = initialSet
            infected.remove(node)
            for i in initialSet {
                if i != node {
                    dfs(i, &infected)
                }
            }
            if infected.count < minInfected {
                minInfected = infected.count
                bestNode = node
            }
        }
        
        return bestNode
    }
}

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

class Solution {
    func generate(_ numRows: Int) -> [[Int]] {
        var triangle = [[Int]]()

        for rowNum in 0..<numRows {
            var row = Array(repeating: 0, count: rowNum + 1)
            row[0] = 1
            row[row.count - 1] = 1

            for j in 1..<row.count - 1 {
                row[j] = triangle[rowNum - 1][j - 1] + triangle[rowNum - 1][j]
            }

            triangle.append(row)
        }

        return triangle
    }
}

Input: arr = [1,2]
Output: 2

func minMovesToDelete(_ arr: [Int]) -> Int {
    let n = arr.count
    var dp = Array(repeating: Array(repeating: 0, count: n), count: n)

    for i in 0..<n {
        dp[i][i] = 1
    }

    for length in 2...n {
        for i in 0...(n - length) {
            let j = i + length - 1
            if arr[i] == arr[j] {
                dp[i][j] = length > 2 ? dp[i + 1][j - 1] : 1
            } else {
                dp[i][j] = Int.max
                for k in i..<j {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
                }
            }
        }
    }

    return dp[0][n - 1]
}

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

import Foundation

class Solution {
    private var memo: [Int: Int] = [:]

    private func recursiveWithMemo(_ index: Int, _ s: String) -> Int {
        if index == s.count {
            return 1
        }

        let startIndex = s.index(s.startIndex, offsetBy: index)
        let firstChar = s[startIndex]

        if firstChar == "0" {
            return 0
        }

        if index == s.count - 1 {
            return 1
        }

        if let cachedResult = memo[index] {
            return cachedResult
        }

        let nextIndex = s.index(after: startIndex)
        var answer = recursiveWithMemo(index + 1, s)

        if index < s.count - 1 {
            let secondIndex = s.index(after: nextIndex)
            let range = startIndex..<secondIndex
            let number = Int(s[range])!

            if number <= 26 {
                answer += recursiveWithMemo(index + 2, s)
            }
        }

        memo[index] = answer
        return answer
    }

    func numDecodings(_ s: String) -> Int {
        return recursiveWithMemo(0, s)
    }
}

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

class Solution {
    func kWeakestRows(_ mat: [[Int]], _ k: Int) -> [Int] {
        let m = mat.count
        let n = mat[0].count

        var pairs = [(Int, Int)]()

        for i in 0..<m {
            var strength = 0
            for j in 0..<n {
                if mat[i][j] == 0 { break }
                strength += 1
            }
            pairs.append((strength, i))
        }

        pairs.sort { $0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0 }

        var indexes = [Int]()
        for i in 0..<k {
            indexes.append(pairs[i].1)
        }
        return indexes
    }
}

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

class Solution {
    func sortedListToBST(_ head: ListNode?) -> TreeNode? {
        if head == nil { return nil }
        var mid = findMiddleElement(head)
        var node = TreeNode(mid!.val)
        if head === mid { return node }
        node.left = sortedListToBST(head)
        node.right = sortedListToBST(mid?.next)
        return node
    }
    
    func findMiddleElement(_ head: ListNode?) -> ListNode? {
        var prevPtr: ListNode? = nil
        var slowPtr = head
        var fastPtr = head
        while fastPtr != nil && fastPtr!.next != nil {
            prevPtr = slowPtr
            slowPtr = slowPtr!.next
            fastPtr = fastPtr!.next!.next
        }
        if prevPtr != nil { prevPtr!.next = nil }
        return slowPtr
    }
}