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
    }
}

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

class Solution {
    func cellsToBitmap(_ cells: [Int]) -> Int {
        var stateBitmap = 0
        for cell in cells {
            stateBitmap = (stateBitmap << 1) | cell
        }
        return stateBitmap
    }

    func nextDay(_ cells: [Int]) -> [Int] {
        var newCells = Array(repeating: 0, count: cells.count)
        for i in 1..<cells.count-1 {
            newCells[i] = (cells[i-1] == cells[i+1]) ? 1 : 0
        }
        return newCells
    }

    func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
        var cells = cells
        var N = N
        var seen = [Int: Int]()
        var isFastForwarded = false

        while N > 0 {
            if !isFastForwarded {
                let stateBitmap = cellsToBitmap(cells)
                if let cycleLength = seen[stateBitmap] {
                    N %= cycleLength - N
                    isFastForwarded = true
                } else {
                    seen[stateBitmap] = N
                }
            }

            if N > 0 {
                N -= 1
                cells = nextDay(cells)
            }
        }
        return cells
    }
}

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

func trailingZeroes(_ n: Int) -> Int {
    var nFactorial = 1
    for i in 2...n {
        nFactorial *= i
    }

    var zeroCount = 0
    var nFactorialBigInt = nFactorial

    while nFactorialBigInt % 10 == 0 {
        nFactorialBigInt /= 10
        zeroCount += 1
    }

    return zeroCount
}

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

class Solution {
    func uniqueOccurrences(_ arr: [Int]) -> Bool {
        var freq: [Int: Int] = [:]
        for num in arr {
            freq[num, default: 0] += 1
        }
        let freqSet = Set(freq.values)
        return freq.count == freqSet.count
    }
}