Neetcode-150

Neetcode-150.swift

//
//  Solution.swift
//  DSA
//
//  Created by Abhishek kapoor on 10/03/24.
//
// MARK: TRACKER SHEET:- https://docs.google.com/spreadsheets/d/1IN_m4fnrid0mW3_5U6qdfdSaMSXH_mkC3ISf2SexhMA/edit#gid=0
// MARK: APP SHEET:- https://www.appsheet.com/start/183562bd-4784-467c-a879-949628acc5ed
// MARK: GSIT :- https://gist.github.com/theabhieye/205d1c4f01536a89815fe0b1356320d4
// MARK: Practice doc: - https://docs.google.com/document/d/1Zoyc57B485JA00Vwp9_GgXH2QoVGKKN3yqZjWCSHeV8/edit

import Foundation

final class Neetcode150 {
    
    private func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var freqDict:[Int:Int] = [:]
        for i in nums {
            freqDict[i, default:0] += 1
        }
        
        var countArr: Array<Set<Int>> = Array(repeating: Set<Int>(), count: nums.count + 1)
        for (key,value) in freqDict {
            countArr[value].insert(key)
        }
        var result: [Int] = []
        for i in countArr.indices.reversed() {
            if countArr[i].isEmpty == false {
                result.append(contentsOf: countArr[i])
                
            }
        }
        return Array(result.prefix(k))
    }
    
    private func characterReplacement(_ s: String, _ k: Int) -> Int {
        let arr = Array(s)
        var dict: [Character : Int] = [:]
        var left = 0
        var result = 0
        
        for right in arr.indices {
            dict[arr[right], default: 0] += 1
            
            while (right - left + 1) - dict.values.max()! > k {
                dict[arr[left]]! -= 1
                left += 1
            }
            result = max(result, right - left + 1)
        }
        
        return result
    }
    
    private func lengthOfLongestSubstring(_ s: String) -> Int {
        let arr = Array(s)
        var dict:[Character: Int] = [:]
        var left = 0,right = 0,result = 0
        
        while right < arr.count {
            let ch = arr[right]
            if let charIndex = dict[ch] {
                left = max(left, charIndex + 1)
            }
            dict[ch] = right
            result = max(result, right - left + 1 )
            right += 1
        }
        
        return result
    }
    
    private func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        
        let s1 = Array(s1.unicodeScalars)
        let s2 = Array(s2.unicodeScalars)
        
        var s1arr = Array(repeating: 0, count: 26)
        var s2arr = Array(repeating: 0, count: 26)
        
        for c in s1 {
            s1arr[Int(c.value - 97)] += 1
        }
        
        for i in 0..<s2.count {
            
            if i >= s1.count {
                s2arr[Int(s2[i - s1.count].value - 97)] -= 1
            }
            
            s2arr[Int(s2[i].value - 97)] += 1
            
            if s1arr == s2arr {
                return true
            }
        }
        return false
    }
    
    private func minWindow(_ s: String, _ t: String) -> String {
        if s.count < t.count {
            return ""
        }
        
        var freq = Array(repeating: 0, count: 129)
        let sArr = Array(s)
        let tArr = Array(t)
        
        for i in tArr.indices {
            freq[Int(tArr[i].asciiValue!)] += 1
        }
        
        let toFind = tArr.count
        var result = ""
        var left = 0, right = 0
        var minLength = Int.max
        var found = 0
        
        while right < sArr.count {
            freq[Int(sArr[right].asciiValue!)] -= 1
            if freq[Int(sArr[right].asciiValue!)] >= 0 {
                found += 1
            }
            
            while found == toFind {
                if minLength > (right - left + 1) {
                    minLength = right - left + 1
                    result = String(sArr[left...right])
                }
                freq[Int(sArr[left].asciiValue!)] += 1
                if freq[Int(sArr[left].asciiValue!)] > 0 {
                    found -= 1
                }
                
                left += 1
            }
            right += 1
        }
        
        return result
    }
    
    private func isValid1(_ s: String) -> Bool {
        var stack: [Character] = [Character]()
        
        for ch in s {
            if ch == "[" || ch == "(" || ch == "{" {
                stack.append(ch)
            } else {
                if stack.isEmpty {
                    return false
                }
                if  (ch == "]" && stack.last! == "[") ||
                        (ch == ")" && stack.last! == "(") ||
                        (ch == "}" && stack.last! == "{") {
                    stack.removeLast()
                } else {
                    return false
                }
            }
        }
        return stack.isEmpty
    }
    
    private func isValid(_ s: String) -> Bool {
        let map: [Character:Character] = ["{":"}","[":"]","(":")"]
        var stack: [Character] = []
        for ch in s {
            if map.keys.contains(ch) {
                stack.append(ch)
            } else if let top = stack.last, ch == map[top] {
                stack.removeLast()
            } else {
                return false
            }
        }
        return stack.isEmpty
    }
    
    private class MinStack {
        
        private var minStack: [Int]
        private var stack: [Int]
        
        init() {
            stack = [Int]()
            minStack = [Int]()
        }
        
        private func  push(_ val: Int) {
            if stack.isEmpty {
                stack.append(val)
                minStack.append(val)
            } else {
                stack.append(val)
                minStack.append(min(val, minStack.last!))
            }
        }
        
        private func  pop() {
            _ = stack.popLast()
            _ = minStack.popLast()
        }
        
        private func  top() -> Int {
            if let top = stack.last {
                return top
            }
            return Int.min
        }
        
        private func  getMin() -> Int {
            if let top = minStack.last {
                return top
            }
            return Int.min
        }
        
    }
    
    private func  evalRPN(_ tokens: [String]) -> Int {
        var st = [Int]()
        
        for ch in tokens {
            if ch == "+" {
                st.append(st.removeLast() + st.removeLast())
            } else if ch == "-" {
                let v1 = st.removeLast()
                let v2 = st.removeLast()
                st.append(v2-v1)
            } else if ch == "/" {
                let v1 = st.removeLast()
                let v2 = st.removeLast()
                st.append(Int(v2/v1))
            } else if ch == "*" {
                st.append(st.removeLast() * st.removeLast())
            } else {
                st.append(Int(ch)!)
            }
        }
        return st.last!
    }
    
    private func generateParenthesis(_ n: Int) -> [String] {
        var stack = [Character]()
        var result = [String]()
        
        func backtracking(_ openCount: Int, _ closeCount: Int) {
            if n == openCount && n == closeCount {
                result.append(String(stack))
                return
            }
            
            if openCount < n {
                stack.append("(")
                backtracking(openCount + 1, closeCount)
                _ = stack.popLast()
            }
            
            if closeCount < openCount {
                stack.append(")")
                backtracking(openCount, closeCount + 1)
                _ = stack.popLast()
            }
        }
        backtracking(0, 0)
        return result
    }
    
    private func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        var stack = [Int]()
        var result = Array(repeating: 0, count: temperatures.count)
        
        for (index, temperature) in temperatures.enumerated() {
            while let lastIndex = stack.last, temperature > temperatures[lastIndex] {
                stack.removeLast()
                result[lastIndex] = index - lastIndex
            }
            stack.append(index)
        }
        
        return result
    }
    
    private func dailyTemperatures1(_ nums: [Int]) -> [Int] {
        var st = [Int]()
        var result = Array(repeating: 0, count: nums.count)
        
        for index in nums.indices.reversed() {
            while let top = st.last,
                  nums[top] < nums[index] {
                st.removeLast()
            }
            if !st.isEmpty {
                result[index] = st.last! - index
            }
            st.append(index)
        }
        return result
    }
    
    private func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
        let zipped = zip(position, speed).sorted(by: { $0.0 > $1.0 })
        var fleets = 0
        var prevTime: Double = -1.0
        
        for (pos, spd) in zipped {
            let timeToReachDestination = Double(target - pos) / Double(spd)
            if timeToReachDestination > prevTime {
                fleets += 1
                prevTime = timeToReachDestination
            }
        }
        
        return fleets
    }
    
    private func largestRectangleArea(_ heights: [Int]) -> Int {
        func  prevSmall() -> [Int] {
            var ps = Array(repeating: -1, count: heights.count)
            var stack = [Int]()
            for i in heights.indices {
                while let lastIndex = stack.last, heights[lastIndex] >= heights[i] {
                    stack.removeLast()
                }
                if !stack.isEmpty {
                    ps[i] = stack.last!
                } else {
                    ps[i] = -1
                }
                stack.append(i)
            }
            
            return ps
        }
        
        func  nextSmallest() -> [Int] {
            var ns = Array(repeating: -1, count: heights.count)
            var stack = [Int]()
            for i in heights.indices.reversed() {
                while let topIndex = stack.last, heights[topIndex] >= heights[i] {
                    stack.removeLast()
                }
                if !stack.isEmpty {
                    ns[i] = stack.last!
                } else {
                    ns[i] = heights.count
                }
                stack.append(i)
            }
            
            return ns
        }
        
        let ns = nextSmallest()
        let ps = prevSmall()
        var res = Int.min
        
        for i in heights.indices {
            let width = ns[i] - ps[i] - 1
            let area = width * heights[i]
            res = max(res, area)
        }
        
        return res
    }
    
    private func search(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] == target {
                return mid
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return -1
    }
    
    private func nextGreaterOnRight(_ nums: [Int]) -> [Int] {
        var st = [Int]()
        var result = Array(repeating: 0, count: nums.count)
        
        for index in nums.indices.reversed() {
            while let top = st.last,
                  nums[top] < nums[index] {
                st.removeLast()
            }
            if !st.isEmpty {
                result[index] = st.last!
            }
            st.append(index)
        }
        return result
    }
    
    private func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        var potianalRow: Int?
        
        var low = 0
        var high = matrix.count - 1
        
        while low <= high {
            let mid = (low + high)/2
            if matrix[mid][0] <= target && matrix[mid][matrix[mid].count - 1] >= target {
                potianalRow = mid
                break
            } else if matrix[mid][0] < target  {
                low = mid + 1
            } else {
                high = mid - 1
            }
        }
        
        guard let potianalRow = potianalRow else {
            return false
        }
        
        func  searchRow(_ nums: [Int]) -> Bool {
            var left = 0
            var right = nums.count - 1
            
            while left <= right {
                let mid = (left + right) / 2
                if nums[mid] == target {
                    return true
                } else if nums[mid] < target {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
            
            return false
        }
        
        return searchRow(matrix[potianalRow])
    }
    
    private func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        var left = 1
        var right = piles.max() ?? 1
        
        func  getTarget(for value: Int) -> Int {
            var totalTimeTaken: Int = 0
            for i in piles {
                totalTimeTaken += Int(ceil(Double(i)/Double(value)))
            }
            return totalTimeTaken
        }
        
        while left < right {
            let mid = (left + right)/2
            let hours = getTarget(for: mid)
            if hours <= h {
                right = mid
            } else {
                left = mid + 1
            }
        }
        
        return right
    }
    
    private func findMin(_ nums: [Int]) -> Int {
        var minRes = Int.max
        var left = 0
        var right = nums.count - 1
        while left <= right {
            let mid = (left + right) / 2
            if nums[left] <= nums[mid] {
                minRes = min(nums[left],minRes)
                left = mid + 1
            } else {
                minRes = min(nums[mid],minRes)
                right = mid - 1
            }
        }
        return minRes
    }
    
    private func searchInRotated(_ nums: [Int], _ target: Int) -> Int {
        var l = 0, r = nums.count - 1
        while l <= r {
            let m = (l+r)/2
            if nums[m] == target {
                return m
            }
            
            if nums[l] <= nums[m] {
                if nums[l]...nums[m] ~= target {
                    r = m - 1
                } else {
                    l = m + 1
                }
            } else {
                if nums[m]...nums[r] ~= target {
                    l = m + 1
                } else {
                    r = m - 1
                }
            }
        }
        
        return -1
    }
    
    
    class TimeMap {
        
        private var dict: [String: [(Int, String)]]
        
        init() {
            dict = [String: [(Int, String)]]()
        }
        
        private func  set(_ key: String, _ value: String, _ timestamp: Int) {
            dict[key, default: []].append((timestamp, value))
        }
        
        private func  get(_ key: String, _ timestamp: Int) -> String {
            guard let pairList = dict[key] else { return "" }
            
            // All the timestamps timestamp of set are strictly increasing.
            var l = 0
            var r = pairList.count - 1
            var res = ""
            
            while l <= r {
                let m = (l+r)/2
                if pairList[m].0 <= timestamp {
                    res = pairList[m].1
                    l = m + 1
                } else {
                    r = m - 1
                }
            }
            return res
            
        }
    }
    
    // FIXME: - Not able to find issue in below code.
    private func  findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        var A: [Int] = nums2
        var B: [Int] = nums1
        
        if nums1.count > nums2.count {
            A = nums1
            B = nums2
        }
        
        let totalSize = nums1.count + nums2.count
        
        var left = 0, right = B.count
        
        while left <= right {
            let partitionA = (left + right) / 2
            let partitionB = (left + right + 1) / 2 - partitionA
            
            let minALeft: Int = partitionA == 0 ?  Int(-1e9) : A[partitionA - 1]
            let maxARight = partitionA == A.count ? Int.max: A[partitionA]
            
            let minBLeft = partitionB  == 0 ?  Int(-1e9) : B[partitionB]
            let maxBRight = partitionB == B.count ? Int.max : B[partitionB - 1]
            
            
            if minALeft <= maxBRight && minBLeft <= maxARight {
                // Get the answer
                if !totalSize.isMultiple(of: 2) {
                    return Double(min(minALeft, minBLeft))
                } else {
                    return Double(max(minALeft, minBLeft) +
                                  min(maxARight, maxBRight)) / 2.0
                }
            } else if minALeft > maxBRight {
                right = partitionA - 1
            } else {
                left = partitionA + 1
            }
        }
        return 0.0;
    }
    
    class ListNode {
        var val: Int
        var next: ListNode?
        
        convenience init(_ val: Int) {
            self.init(val: val, next: nil)
        }
        init(val: Int = 0, next: ListNode? = nil) {
            self.val = val
            self.next = next
        }
        
        var debugDescription: String {
            let  res = NSMutableString()
            var dummy: ListNode? = self
            while dummy != nil {
                res.append("\(dummy!.val) -> ")
                dummy = dummy?.next
            }
            
            return String(res)
        }
    }
    
    private func reverseList1(_ head: ListNode?) -> ListNode? {
        var prev: ListNode?
        var curr = head
        var next: ListNode? = curr?.next
        
        while curr != nil {
            curr?.next = prev
            prev = curr
            curr = next
            next = curr?.next
        }
        
        return prev
    }
    
    private func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        let rsof = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return rsof
    }
    
    private func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var list1 = l1
        var list2 = l2
        let dummy = ListNode()
        var curr: ListNode? = dummy
        
        while list1 != nil && list2 != nil {
            if list1!.val < list2!.val {
                curr!.next = list1
                list1 = list1!.next
            } else {
                curr!.next = list2
                list2 = list2?.next
            }
            curr = curr!.next
        }
        
        if list1 == nil {
            curr!.next = list2
        }
        
        if list2 == nil {
            curr!.next = list1
        }
        
        return dummy.next
    }
    
    private func getLinkedList(_ list:[Int]) -> ListNode? {
        if list.isEmpty { return nil }
        var dummy: ListNode? = ListNode()
        let head = dummy
        for i in list {
            dummy!.next = ListNode(val: i)
            dummy = dummy!.next
        }
        return head?.next
    }
    
    private func reorderList(_ head: ListNode?) {
        func getMid() -> ListNode? {
            var slow = head
            var fast = head?.next
            
            while fast != nil && fast?.next != nil {
                slow = slow?.next
                fast = fast?.next?.next
            }
            return slow
        }
        
        func rev(_ ll: ListNode?) -> ListNode? {
            var c: ListNode? = ll
            var p: ListNode? = nil
            var n: ListNode? = ll?.next
            
            while c != nil {
                c?.next = p
                p = c
                c = n
                n = c?.next
            }
            
            return p
        }
        
        let mid_1 = getMid()
        let mid = mid_1?.next
        mid_1?.next = nil
        let rev = rev(mid)
        
        let dummy = ListNode()
        var curr: ListNode? = dummy
        var l1 = head
        var l2 = rev
        var i = 0
        
        while l1 != nil && l2 != nil {
            if i.isMultiple(of: 2) {
                curr?.next = l1
                l1 = l1?.next
            } else {
                curr?.next = l2
                l2 = l2?.next
            }
            curr = curr?.next
            i += 1
        }
        
        if l1 == nil {
            curr?.next = l2
        }
        if l2 == nil {
            curr?.next = l1
        }
    }
    
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var fast = head
        for _ in 0...n {
            fast = fast?.next
        }
        if fast == nil {
            // In this case, we need to remove the head node
            return head?.next
        }
        var slow = head
        while fast?.next != nil {
            fast = fast?.next
            slow = slow?.next
        }
        slow?.next = slow?.next?.next
        return head
    }
    
    func copyRandomList(_ head: Node?) -> Node? {
        var dict: [Node?: Node?] = Dictionary()
        if head == nil {
            return nil
        }
        var curr = head
        
        while curr != nil {
            dict[curr] = Node(curr!.val)
            curr = curr?.next
        }
        
        curr = head
        while curr != nil {
            let copy: Node? = dict[curr]!
            if curr!.next != nil {
                copy?.next = dict[curr!.next]!
            }
            if curr!.random != nil {
                copy?.random = dict[curr!.random]!
            }
            curr = curr?.next
        }
        
        
        return dict[head]! ?? nil
    }
    
    func hasCycle(_ head: ListNode?) -> Bool {
        var slow = head, fast = head
        
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            // if we use ==  then we need to conform to `Equatable` protocol
            if slow === fast {
                return true
            }
        }
        return true
    }
    
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        if l1 == nil || l2 == nil {
            return l1
        }
       
        let dummy: ListNode? = ListNode()
        var curr: ListNode?
        curr = dummy
        
        var ll1 = l1
        var ll2 = l2
        var carry: Int? = nil
        
        while ll1 != nil || ll2 != nil {
            let i1 = ll1?.val ?? 0
            let i2 = ll2?.val ?? 0
            let c = carry ?? 0
            var sum = i1 + i2 + c
            
            if sum > 9 {
                carry = sum / 10
                sum = sum % 10
            } else {
                carry = nil
            }
            
            curr?.next = ListNode(val: sum)
            curr = curr?.next
            
            ll1 = ll1?.next
            ll2 = ll2?.next
        }
        
        if let carry {
            curr?.next = ListNode(val: carry)
        }
        
        return dummy?.next
    }
    
    class LRUCache {
        
        class DoublyLinkedList {
            var val: Int
            var key: Int
            // making next and prev weak so we don't end up with ref. cycle
            weak var next: DoublyLinkedList?
            weak var prev: DoublyLinkedList?
            
            init(val: Int, key: Int, next: DoublyLinkedList? = nil, prev: DoublyLinkedList? = nil) {
                self.val = val
                self.next = next
                self.prev = prev
                self.key = key
            }
            
            convenience init(_ val: Int,_ key: Int) {
                self.init(val: val, key: key)
            }
        }
        let capacity: Int
        var dict: [Int: DoublyLinkedList]
        var head: DoublyLinkedList
        var tail: DoublyLinkedList
        
        init(_ capacity: Int) {
            self.capacity = capacity
            self.dict = Dictionary(minimumCapacity: capacity)
            head = DoublyLinkedList(0,0)
            tail = DoublyLinkedList(0,0)
            head.next = tail
            tail.prev = head
        }
        
        func get(_ key: Int) -> Int {
            if var node = dict[key] {
                moveToFront(&node)
                return node.val
            }
            return -1
        }
        
        func put(_ key: Int, _ value: Int) {
            if var node = dict[key] {
                node.val = value
                moveToFront(&node)
            } else {
                // removing value for node
                if dict.count == capacity,
                   var prevNode = tail.prev {
                    dict[prevNode.key] = nil
                    removeNode(&prevNode)
                }
                var newNode = DoublyLinkedList(value, key)
                dict[key] = newNode
                addNode(&newNode)
            }
        }
        
        /// This method will add node in start of the list
        /// - Parameter node: ref of Doubly Linked List
        private func addNode(_ node: inout DoublyLinkedList) {
            let nbr = head.next
            
            node.next = nbr
            node.prev = head
            
            head.next = node
            nbr?.prev = node
        }
        
        private func removeNode(_ node: inout DoublyLinkedList) {
            // remove from tail
            
            let prevNbr = node.prev
            let nextNbr = node.next
            
            prevNbr?.next = nextNbr
            nextNbr?.prev = prevNbr
            
            node.next = nil
            node.prev = nil
        }
        
        private func moveToFront(_ node: inout DoublyLinkedList) {
            removeNode(&node)
            addNode(&node)
        }
        
        func printList() {
            var dummy: DoublyLinkedList? = head
            var res = ""
            while dummy != nil {
                res.append("{\(dummy!.key),\(dummy!.val)} -> ")
                dummy = dummy?.next
            }
            print(res)
        }
    }
    
    func getLength(_ head: ListNode?) -> Int {
        var curr = head
        var count = 0
        while curr != nil {
            count += 1
            curr = curr?.next
        }
        return count
    }
    
    func addFirst(_ node: inout ListNode?,
                  _ currentHead: inout ListNode?,
                  _ currentTail: inout ListNode?) {
        if currentHead == nil && currentTail == nil {
            currentHead = node
            currentTail = node
            node?.next = nil
        } else {
            node?.next = currentHead
            currentHead = node
        }
    }
    
    func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
        var listLength = getLength(head)
        var tempHead: ListNode?
        var tempTail: ListNode? = tempHead
        var orgTail: ListNode?
        var orgHead: ListNode?
        var curr = head
        var next: ListNode? = curr?.next
        
        while listLength >= k {
            for _ in 1...k {
                addFirst(&curr, &tempHead, &tempTail)
                curr = next
                next = curr?.next
            }
            if orgHead == nil && orgTail == nil {
                orgHead = tempHead
            } else {
                orgTail?.next = tempHead
            }
            orgTail = tempTail
            tempHead = nil
            tempTail = tempHead
            listLength -= k
        }
        
        if listLength != 0 {
            orgTail?.next = curr
        }
        return orgHead
    }
    
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else { return root }
        root.left =  invertTree(root.left)
        root.right = invertTree(root.right)
        (root.left, root.right) = (root.right, root.left)
        return root
    }
    
    func maxDepthDFS(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        return 1 + max(maxDepthDFS(root.left),maxDepthDFS(root.right))
    }
    
    // 2: BFS
    func maxDepthBFS(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        var queue: [TreeNode?] = [root]
        var level = 0
        
        while !queue.isEmpty {
            var size = queue.count
            while size > 0 {
                guard let top = queue.removeFirst() else {
                    fatalError("Invalid Queue")
                }
                if top.left != nil  {
                    queue.append(top.left)
                }
                
                if top.right != nil  {
                    queue.append(top.right)
                }
                size -= 1
            }
            level += 1
        }
        return level
    }
    
    // 3: Iterative DFS
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0}
        
        
        var stack: [(TreeNode?, Int)] = [(root, 1)]
        var maxLevel = 1
        
        while stack.isEmpty == false {
            let top = stack.removeLast()
            maxLevel = max(maxLevel, top.1)
            if top.0?.left != nil {
                stack.append((top.0?.left, top.1 + 1))
            }
            
            if top.0?.right != nil {
                stack.append((top.0?.right, top.1 + 1))
            }
        }
        
        return maxLevel
    }
    
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
         guard let root = root else { return 0 }
         var maxDepth = 0
        
        @discardableResult
        func diameter(_ curr: TreeNode?) -> Int{
             guard let curr = curr else { return -1 }
             let leftDia = diameter(curr.left)
             let rightDia = diameter(curr.right)
             maxDepth = max(maxDepth, leftDia + rightDia + 2)
             return max(leftDia, rightDia) + 1
         }
        
        diameter(root)
        return maxDepth
     }
    
    func diameterOfBinaryTree01(_ root: TreeNode?) -> Int {
         guard let root = root else { return 0 }
         var maxDepth = 0
        
        @discardableResult
        func diameter(_ curr: TreeNode?) -> Int{
             guard let curr = curr else { return 0 }
             let leftDia = diameter(curr.left)
             let rightDia = diameter(curr.right)
             maxDepth = max(maxDepth, leftDia + rightDia)
             return max(leftDia, rightDia) + 1
         }
        
        diameter(root)
        return maxDepth
     }
    
    func isBalanced(_ root: TreeNode?) -> Bool {
        guard let root = root else { return true }
        var result = true
        
        @discardableResult
        func height(_ curr: TreeNode?) -> Int {
            guard let curr = curr else { return 0}
            let leftHeight = height(curr.left)
            let rightHeight = height(curr.right)
            
            if abs(leftHeight - rightHeight) > 1 {
                result = false
            }
            return max(leftHeight, rightHeight) + 1
        }
        
        height(root)
        
        return result
    }
    
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        
        if p == nil || q == nil {
            return false
        }
        
        return p?.val == q?.val && 
                isSameTree(p?.left, q?.left) &&
                isSameTree(p?.right, q?.right)
    }
    
    func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
        func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
            if p == nil && q == nil {
                return true
            }
            
            if p == nil || q == nil {
                return false
            }
            
            return p?.val == q?.val &&
                    isSameTree(p?.left, q?.left) &&
                    isSameTree(p?.right, q?.right)
        }
        
        if isSameTree(root, subRoot) {
            return true
        }
        
        return  isSameTree(root?.left, subRoot) || isSameTree(root?.right, subRoot)
    }

    func lowestCommonAncestor1(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root = root, let p = p, let q = q else { return nil }
        
        var curr: TreeNode? = root
        while curr != nil {
            if p.val < curr!.val && q.val < curr!.val {
                curr = curr!.left
            } else if p.val > curr!.val && q.val > curr!.val {
                curr = curr!.right
            } else {
                return curr
            }
        }
        return root
    }
    
    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
        }
    }
    
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        var queue: [TreeNode?] = []
        queue.append(root)
        var result: [[Int]] = []
        while !queue.isEmpty {
            var size = queue.count
            result.append([Int]())
            while size > 0 {
                if let top = queue.removeFirst() {
                    result[result.count-1].append(top.val)
                    if let left = top.left {
                        queue.append(left)
                    }
                    if let right = top.right {
                        queue.append(right)
                    }
                }
                size -= 1
            }
        }
        return result
    }
    
    func levelOrder1(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else {
            return []
        }
        var queue: [TreeNode?] = []
        queue.append(root)
        var result: [[Int]] = []
        while !queue.isEmpty {
            var size = queue.count
            var res = [Int]()
            while size > 0 {
                if let top = queue.removeFirst() {
                    res.append(top.val)
                    if let left = top.left {
                        queue.append(left)
                    }
                    if let right = top.right {
                        queue.append(right)
                    }
                }
                size -= 1
            }
            result.append(res)
        }
        return result
    }
    
    func rightSideView(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        var queue = [TreeNode?]()
        var result = [Int]()
        queue.append(root)
        while !queue.isEmpty {
            var size = queue.count
            while size > 0 {
                if let top = queue.removeFirst() {
                    if let left = top.left {
                        queue.append(left)
                    }
                    if let right = top.right {
                        queue.append(right)
                    }
                    if size == 1 {
                        result.append(top.val)
                    }
                }
                size -= 1
            }
        }
        return result
    }
    
    class func main() {
        let solution = Neetcode150()
//        [4,2,7,1,3,6,9]
        let root = TreeNode(4)
        root.left = TreeNode(2)
        root.left?.left = TreeNode(1)
        root.left?.right = TreeNode(3)
        root.right = TreeNode(7)
        root.right?.left = TreeNode(6)
        root.right?.right = TreeNode(9)
        
//        var root = TreeNode(1)
//        root.left = TreeNode(2)
//        solution.invertTree(root)
//        print(solution.levelOrder1(root))
        print(solution.rightSideView(root))
        
    }
    
    class private func getBST() -> TreeNode {
        let root = TreeNode(2)
        root.left = TreeNode(1)
        return root
    }
}

public class Node {
    public var val: Int
    public var next: Node?
    public var random: Node?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
        self.random = nil
    }
}

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

extension Node: Hashable {
    public static func == (lhs: Node, rhs: Node) -> Bool {
        return lhs === rhs
    }
    
    public func hash(into hasher: inout Hasher) {
        hasher.combine(ObjectIdentifier(self))
    }
}