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

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

class Solution {
    let directions = [0, 1, 0, -1, 0]

    func getMaximumGold(_ grid: [[Int]]) -> Int {
        var grid = grid
        let rows = grid.count
        let cols = grid[0].count
        var maxGold = 0

        for row in 0..<rows {
            for col in 0..<cols {
                maxGold = max(maxGold, dfsBacktrack(&grid, rows, cols, row, col))
            }
        }
        return maxGold
    }

    func dfsBacktrack(_ grid: inout [[Int]], _ rows: Int, _ cols: Int, _ row: Int, _ col: Int) -> Int {
        if row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0 {
            return 0
        }
        let originalVal = grid[row][col]
        grid[row][col] = 0
        var maxGold = 0

        for i in 0..<4 {
            maxGold = max(maxGold, dfsBacktrack(&grid, rows, cols, row + directions[i], col + directions[i + 1]))
        }

        grid[row][col] = originalVal
        return maxGold + originalVal
    }
}

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

class Solution {
    func deleteTreeNodes(_ nodes: Int, _ parent: [Int], _ value: [Int]) -> Int {
        var tree = [Int: [Int]]()
        for i in 0..<nodes {
            tree[parent[i], default: []].append(i)
        }

        func dfs(_ node: Int) -> (Int, Int) {
            var totalSum = value[node]
            var totalCount = 1
            if let children = tree[node] {
                for child in children {
                    let (childSum, childCount) = dfs(child)
                    totalSum += childSum
                    totalCount += childCount
                }
            }
            return totalSum == 0 ? (0, 0) : (totalSum, totalCount)
        }

        return dfs(0).1
    }
}

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

class Solution {
    func validWordSquare(_ words: [String]) -> Bool {
        var cols = 0
        let rows = words.count
        var newWords = [String]()
        
        for word in words {
            cols = max(cols, word.count)
        }

        if cols != words[0].count || rows != cols {
            return false
        }

        for col in 0..<cols {
            var newWord = ""
            for row in 0..<rows {
                if col < words[row].count {
                    newWord.append(words[row][words[row].index(words[row].startIndex, offsetBy: col)])
                }
            }
            newWords.append(newWord)
        }

        return words == newWords
    }
}

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

class Solution {
    func balanceBST(_ root: TreeNode?) -> TreeNode? {
        if root == nil { return nil }

        let vineHead = TreeNode(0)
        vineHead.right = root
        var current: TreeNode? = vineHead

        while current?.right != nil {
            if current?.right?.left != nil {
                rightRotate(current, current?.right)
            } else {
                current = current?.right
            }
        }

        var nodeCount = 0
        current = vineHead.right
        while current != nil {
            nodeCount += 1
            current = current?.right
        }

        var m = Int(pow(2.0, floor(log2(Double(nodeCount + 1))))) - 1
        makeRotations(vineHead, nodeCount - m)
        while m > 1 {
            m /= 2
            makeRotations(vineHead, m)
        }

        let balancedRoot = vineHead.right
        return balancedRoot
    }

    private func rightRotate(_ parent: TreeNode?, _ node: TreeNode?) {
        let tmp = node?.left
        node?.left = tmp?.right
        tmp?.right = node
        parent?.right = tmp
    }

    private func leftRotate(_ parent: TreeNode?, _ node: TreeNode?) {
        let tmp = node?.right
        node?.right = tmp?.left
        tmp?.left = node
        parent?.right = tmp
    }

    private func makeRotations(_ vineHead: TreeNode?, _ count: Int) {
        var current = vineHead
        for _ in 0..<count {
            let tmp = current?.right
            leftRotate(current, tmp)
            current = current?.right
        }
    }
}

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

func largestRectangleArea(_ heights: [Int]) -> Int {
    var maxArea = 0
    for i in 0..<heights.count {
        for j in i..<heights.count {
            var minHeight = Int.max
            for k in i...j {
                minHeight = min(minHeight, heights[k])
            }
            maxArea = max(maxArea, minHeight * (j - i + 1))
        }
    }
    return maxArea
}

Input: n = 3, goal = 3, k = 1
Output: 6

class Solution {
    func minAddToMakeValid(_ s: String) -> Int {
        var openNeeded = 0
        var closeNeeded = 0
        
        for char in s {
            if char == "(" {
                openNeeded += 1
            } else if char == ")" {
                if openNeeded > 0 {
                    openNeeded -= 1
                } else {
                    closeNeeded += 1
                }
            }
        }
        return openNeeded + closeNeeded
    }
}

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

func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.isEmpty { return 0 }
    
    var k = 1
    
    for i in 1..<nums.count {
        if nums[i] != nums[k - 1] {
            nums[k] = nums[i]
            k += 1
        }
    }
    
    return k
}