leetcode

commit 85455c7f3ed8fdfbce2a2bd5bbc3a25b20c8125c
parent d8f69f38f877dffd90f5a68c8ec20743a514e966
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  3 Feb 2023 14:36:38 +0100

Algorithm II: Day 1

Diffstat:
A
Problems/0033.cpp
 | 
24
++++++++++++++++++++++++
A
Problems/0034.cpp
 | 
20
++++++++++++++++++++
M
Problems/0074.cpp
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
M
README.md
 | 
2
++

4 files changed, 105 insertions(+), 2 deletions(-)
diff --git a/Problems/0033.cpp b/Problems/0033.cpp
@@ -0,0 +1,24 @@
+class Solution {
+  int binary_search(const vector<int>& nums, int target, int low, int high) {
+    while(low<=high){
+      int mid = low + (high-low)/2;
+      if(nums[mid]==target) return mid;
+      else if(nums[mid]>target) high = mid-1;
+      else low = mid + 1;
+    }
+    return -1;
+  }
+public:
+    int search(vector<int>& nums, int target) {
+      int pivot = -1;
+      for(int i=0; i<nums.size()-1; i++) {
+        if(nums[i] > nums[i+1]) {
+          pivot = i;
+          break;
+        }
+      }
+      if(pivot==-1) return binary_search(nums, target, 0, nums.size()-1);
+      if(nums[0]<=target) return binary_search(nums, target, 0, pivot);
+      else return binary_search(nums, target, pivot+1, nums.size()-1);
+    }
+};
diff --git a/Problems/0034.cpp b/Problems/0034.cpp
@@ -0,0 +1,20 @@
+class Solution {
+  int binary_search(const vector<int>& nums, int target) {
+    int low = 0, high = nums.size()-1;
+    while(low<=high){
+      int mid = low + (high-low)/2;
+      if(nums[mid]==target) return mid;
+      else if(nums[mid]>target) high = mid-1;
+      else low = mid + 1;
+    }
+    return -1;
+  }
+public:
+    vector<int> searchRange(vector<int>& nums, int target) {
+        int low, high;
+        low = high = binary_search(nums, target);
+        while(low-1>=0 && nums[low-1] == target) low--;
+        while(high+1<nums.size() && nums[high+1] == target) high++;
+        return {low, high};
+    }
+};
diff --git a/Problems/0074.cpp b/Problems/0074.cpp
@@ -1,2 +1,59 @@
-Formating: Problems/0036.cpp
-Formating: Problems/0074.cpp
+class Solution {
+public:
+  bool searchMatrix(vector<vector<int>> &matrix, int target) {
+    int n = matrix.size(), m = matrix[0].size(), row = n - 1;
+    for (int i = 0; i < n - 1; i++) {
+      if (matrix[i + 1][0] > target) {
+        row = i;
+        break;
+      }
+    }
+
+    int low = 0, high = m - 1;
+    while (low <= high) {
+      int mid = low + (high - low) / 2;
+      if (matrix[row][mid] == target)
+        return true;
+      else if (matrix[row][mid] < target)
+        low = mid + 1;
+      else
+        high = mid - 1;
+    }
+    return false;
+  }
+};
+
+// Treat the matrix as a sorted list
+class Solution {
+public:
+  bool searchMatrix(vector<vector<int>> &matrix, int target) {
+    int n = matrix.size(), m = matrix[0].size();
+    int low = 0, high = m * n - 1;
+    while (low <= high) {
+      int mid = low + (high - low) / 2;
+      if (matrix[mid / m][mid % m] == target) return true;
+      if (matrix[mid / m][mid % m] < target)
+        low = mid + 1;
+      else
+        high = mid - 1;
+    }
+    return false;
+  }
+};
+
+// Binary Search Tree
+class Solution {
+public:
+  bool searchMatrix(vector<vector<int>> &matrix, int target) {
+    int n = matrix.size(), m = matrix[0].size();
+    int row = 0, col = m - 1;
+			
+    while (row < n && col > -1) {
+        if (matrix[row][col] == target) return true;
+        if (target > matrix[row][col]) row++;
+        else col--;
+    }
+    return false;
+  }
+};
+
diff --git a/README.md b/README.md
@@ -42,6 +42,8 @@ for solving problems.
 |  0026  |    Easy    | [Remove Duplicates from Sorted Array](Problems/0026.cpp)                                         |
 |  0027  |    Easy    | [Remove Element](Problems/0027.cpp)                                                              |
 |  0028  |   Medium   | [Find the Index of the First Occurrence in a String](Problems/0028.cpp)                          |
+|  0033  |   Medium   | [Search in Rotated Sorted Array](Problems/0033.cpp)                                              |
+|  0034  |   Medium   | [Find First and Last Position of Element in Sorted Array](Problems/0034.cpp)                     |
 |  0035  |    Easy    | [Search Insert Position](Problems/0035.cpp)                                                      |
 |  0036  |   Medium   | [Valid Sudoku](Problems/0036.cpp)                                                                |
 |  0042  |   Medium   | [Trapping Rain Water](Problems/0011.cpp)                                                         |