Merge pull request soapyigu#360 from soapyigu/Sort

soapyigu · web-flow · commit f147478c926f · 2022-10-02T13:01:21.000-07:00
Add a solution to Range Module
diff --git a/Sort/RangeModule.swift b/Sort/RangeModule.swift
@@ -0,0 +1,100 @@
+/**
+ * Question Link: https://leetcode.com/problems/range-module/
+ * Primary idea: Sort ranges by left, query using binary search, remove to handle 4 cases separately.
+ * Time Complexity: add - O(nlogn), query - O(logn), remove - O(n), Space Complexity: O(n)
+ *
+ */
+
+class RangeModule {
+
+    var sortedRanges: [(Int, Int)]
+
+    init() {
+        sortedRanges = [(Int, Int)]()
+    }
+    
+    func addRange(_ left: Int, _ right: Int) {
+        sortRanges(for: (left, right))
+    }
+    
+    func queryRange(_ left: Int, _ right: Int) -> Bool {
+        // binary search
+        var l = 0, r = sortedRanges.count - 1
+
+        while l <= r {
+            let m = (r - l) / 2 + l
+
+            if sortedRanges[m].0 <= left && sortedRanges[m].1 >= right {
+                return true
+            } else {
+                if sortedRanges[m].0 > right {
+                    r = m - 1
+                } else if sortedRanges[m].1 < left {
+                    l = m + 1
+                } else {
+                    return false
+                }
+            }
+        }
+
+        return false
+    }
+    
+    func removeRange(_ left: Int, _ right: Int) {
+        var idx = 0
+    
+        while idx < sortedRanges.count {
+            let range = sortedRanges[idx]
+            
+            if isOverlap(range, (left, right)) {
+                if range.0 >= left && range.1 <= right {
+                    sortedRanges.remove(at: idx)
+                } else if range.0 < left && range.1 > right {
+                    sortedRanges.remove(at: idx)
+                    sortedRanges.insert((right, range.1), at: idx)
+                    sortedRanges.insert((range.0, left), at: idx)
+                    idx += 2
+                } else if range.1 <= right {
+                    sortedRanges[idx].1 = left
+                    idx += 1
+                } else {
+                    sortedRanges[idx].0 = right
+                    idx += 1
+                }
+            } else {
+                idx += 1
+            }
+        }
+    }
+    
+
+    private func sortRanges(for newRange: (Int, Int)) {
+        sortedRanges.append(newRange)
+        
+        sortedRanges.sort {
+            $0.0 < $1.0
+        }
+        
+        var res = [(Int, Int)]()
+        
+        for range in sortedRanges {
+            guard let last = res.last else {
+                res.append(range)
+                continue
+            }
+            
+            if range.0 > last.1 {
+                res.append(range)
+            } else {
+                res.removeLast()
+                res.append((last.0, max(last.1, range.1)))
+            }
+        }
+        
+        sortedRanges = res
+    }
+
+    private func isOverlap(_ l: (Int, Int), _ r: (Int, Int)) -> Bool {
+        return !(l.0 >= r.1 || r.0 >= l.1)
+    }
+}
