Input: nums = [-1,2,1,-4], target = 1  
Output: 2  

class Solution {
    func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        let sorted = nums.sorted()
        let length = sorted.count
        var diff: Int = .max
        var result = 0

        for i in 0..<length - 2 {
            var n = i + 1, q = length - 1
            while n < q {
                let sum = sorted[i] + sorted[n] + sorted[q]
                sum > target ? (q -= 1) : (n += 1)
                let value = abs(sum - target)
                if value < diff {
                    diff = value
                    result = sum
                }
            }
        }
        return result
    }
}

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

class Solution {
    func minKBitFlips(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums
        var flips = 0
        var flip = 0
        var flipQueue = [Int](repeating: 0, count: nums.count)
        
        for i in 0..<nums.count {
            if i >= k {
                flip ^= flipQueue[i - k]
            }
            if nums[i] == flip {
                if i + k > nums.count {
                    return -1
                }
                flips += 1
                flip ^= 1
                flipQueue[i] = 1
            }
        }
        return flips
    }
}

Input: s = "the sky is blue"
Output: "blue is sky the"

import Foundation

class Solution {
    func reverseWords(_ s: String) -> String {
        let trimmed = s.trimmingCharacters(in: .whitespacesAndNewlines)
        let words = trimmed.split(separator: " ").reversed()
        return words.joined(separator: " ")
    }
}

Input: nums = [1,-2,3,-2]
Output: 3

class Solution {
    func maxSubarraySumCircular(_ nums: [Int]) -> Int {
        func kadane(_ arr: [Int]) -> Int {
            var currentSum = arr[0], maxSum = arr[0]
            for num in arr[1...] {
                currentSum = max(num, currentSum + num)
                maxSum = max(maxSum, currentSum)
            }
            return maxSum
        }

        let maxKadane = kadane(nums)
        let totalSum = nums.reduce(0, +)
        let minKadane = kadane(nums.map { -$0 })

        return max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane)
    }
}

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

class Solution {
    func destCity(_ paths: [[String]]) -> String {
        for path in paths {
            let candidate = path[1]
            var good = true
            for p in paths {
                if p[0] == candidate {
                    good = false
                    break
                }
            }
            if good {
                return candidate
            }
        }
        return ""
    }
}

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

func sortColors(_ nums: inout [Int]) {
    var p0 = 0, curr = 0
    var p2 = nums.count - 1
    while curr <= p2 {
        if nums[curr] == 0 {
            nums.swapAt(curr, p0)
            curr += 1
            p0 += 1
        } else if nums[curr] == 2 {
            nums.swapAt(curr, p2)
            p2 -= 1
        } else {
            curr += 1
        }
    }
}

Input: stones = [7,4,9]
Output: [1,2]

class Solution {
    func numMovesStonesII(_ stones: [Int]) -> [Int] {
        let sortedStones = stones.sorted()
        let n = sortedStones.count
        
        var maxMoves = sortedStones[n-1] - sortedStones[0] + 1 - n
        maxMoves -= min(sortedStones[1] - sortedStones[0] - 1, sortedStones[n-1] - sortedStones[n-2] - 1)

        var minMoves = Int.max
        var j = 0

        for i in 0..<n {
            while j < n && sortedStones[j] - sortedStones[i] + 1 <= n {
                j += 1
            }
            let alreadyInWindow = j - i
            if alreadyInWindow == n - 1 && sortedStones[j-1] - sortedStones[i] + 1 == n - 1 {
                minMoves = min(minMoves, 2)
            } else {
                minMoves = min(minMoves, n - alreadyInWindow)
            }
        }

        return [minMoves, maxMoves]
    }
}

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

class Solution {
    func minRemoveToMakeValid(_ s: String) -> String {
        var stack = [Int]()
        var s = Array(s)
        for i in 0..<s.count {
            if s[i] == "(" {
                stack.append(i)
            } else if s[i] == ")" {
                if !stack.isEmpty {
                    stack.removeLast()
                } else {
                    s[i] = "*"
                }
            }
        }
        while !stack.isEmpty {
            s[stack.removeLast()] = "*"
        }
        return String(s).replacingOccurrences(of: "*", with: "")
    }
}

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

class Solution {
    func relativeSortArray(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
        var countMap = [Int: Int]()
        var remaining = [Int]()
        var result = [Int]()

        for value in arr2 {
            countMap[value] = 0
        }

        for value in arr1 {
            if let _ = countMap[value] {
                countMap[value]! += 1
            } else {
                remaining.append(value)
            }
        }

        remaining.sort()

        for value in arr2 {
            if let count = countMap[value] {
                for _ in 0..<count {
                    result.append(value)
                }
            }
        }

        result.append(contentsOf: remaining)
        return result
    }
}

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

func minWindow(_ s: String, _ t: String) -> String {
    if s.isEmpty || t.isEmpty {
        return ""
    }

    var dictT = [Character: Int]()
    for char in t {
        dictT[char, default: 0] += 1
    }

    let required = dictT.count
    var l = 0
    var r = 0
    var formed = 0
    var windowCounts = [Character: Int]()
    var ans = (-1, 0, 0)
    
    let sChars = Array(s)
    
    while r < sChars.count {
        let c = sChars[r]
        windowCounts[c, default: 0] += 1

        if let tCount = dictT[c], windowCounts[c] == tCount {
            formed += 1
        }

        while l <= r && formed == required {
            let c = sChars[l]

            if ans.0 == -1 || r - l + 1 < ans.0 {
                ans = (r - l + 1, l, r)
            }

            windowCounts[c, default: 0] -= 1
            if let tCount = dictT[c], windowCounts[c] < tCount {
                formed -= 1
            }
            l += 1
        }
        r += 1
    }

    if ans.0 == -1 {
        return ""
    } else {
        let startIndex = s.index(s.startIndex, offsetBy: ans.1)
        let endIndex = s.index(s.startIndex, offsetBy: ans.2)
        return String(s[startIndex...endIndex])
    }
}

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

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

    func maxDistance(_ grid: [[Int]]) -> Int {
        var visited = grid
        var q = [(Int, Int)]()
        
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == 1 {
                    q.append((i, j))
                }
            }
        }
        
        var distance = -1
        while !q.isEmpty {
            let qSize = q.count
            for _ in 0..<qSize {
                let landCell = q.removeFirst()
                for dir in directions {
                    let x = landCell.0 + dir.0
                    let y = landCell.1 + dir.1
                    
                    if x >= 0 && y >= 0 && x < grid.count && y < grid[0].count && visited[x][y] == 0 {
                        visited[x][y] = 1
                        q.append((x, y))
                    }
                }
            }
            distance += 1
        }
        
        return distance == 0 ? -1 : distance
    }
}

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

class Solution {
    func maxPoints(_ points: [[Int]]) -> Int {
        let n = points.count
        if n == 1 {
            return 1
        }
        var result = 2
        for i in 0..<n {
            var cnt = [Double: Int]()
            for j in 0..<n {
                if j != i {
                    let dy = Double(points[j][1] - points[i][1])
                    let dx = Double(points[j][0] - points[i][0])
                    let angle = atan2(dy, dx)
                    cnt[angle, default: 0] += 1
                }
            }
            for (_, count) in cnt {
                result = max(result, count + 1)
            }
        }
        return result
    }
}

Input: nums = [3,6,9,12]
Output: 4

class Solution {
    func longestArithSeqLength(_ nums: [Int]) -> Int {
        if nums.isEmpty { return 0 }
        
        var dp = Array(repeating: [Int: Int](), count: nums.count)
        var max_length = 0
        
        for i in 0..<nums.count {
            for j in 0..<i {
                let diff = nums[i] - nums[j]
                if let length = dp[j][diff] {
                    dp[i][diff] = length + 1
                } else {
                    dp[i][diff] = 2 // Start a new sequence
                }
                max_length = max(max_length, dp[i][diff]!)
            }
        }
        
        return max_length
    }
}