commit 29b4ccbac9b809e267bdb349f454140b95f3b12f
parent bb947029b122a93387b985665fbd47717a2b8b3e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 23 Jan 2023 21:01:43 +0100
Array and Two Pointer Problems
Diffstat:
4 files changed, 67 insertions(+), 0 deletions(-)
diff --git a/Problems/0011.cpp b/Problems/0011.cpp
@@ -0,0 +1,16 @@
+class Solution {
+public:
+ int trap(vector<int> &height) {
+ int ans = 0, n = height.size(), maxi, m1, m2;
+ vector<int> mleft(n), mright(n);
+
+ m1 = m2 = INT_MIN;
+ for (int i = 0; i < n; i++) {
+ mleft[i] = m1 = max(m1, height[i]);
+ mright[n - i - 1] = m2 = max(m2, height[n - i - 1]);
+ }
+
+ for (int i = 1; i < n - 1; i++) ans += min(mleft[i], mright[i]) - height[i];
+ return ans;
+ }
+};
diff --git a/Problems/0015.cpp b/Problems/0015.cpp
@@ -0,0 +1,28 @@
+class Solution {
+public:
+ vector<vector<int>> threeSum(vector<int> &num) {
+ sort(num.begin(), num.end());
+
+ vector<vector<int>> res;
+ for (int i = 0; i < num.size();) {
+ int target = -num[i], start = i + 1, end = num.size() - 1;
+
+ while (start < end) {
+ int sum = num[start] + num[end];
+ if (sum < target)
+ start++;
+ else if (sum > target)
+ end--;
+ else {
+ res.push_back({num[i], num[start], num[end]});
+ while (start < end && num[start] == res.back()[1]) start++;
+ while (start < end && num[end] == res.back()[2]) end--;
+ }
+ }
+ for (i++; i < num.size() && num[i] == num[i - 1]; i++)
+ ;
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0128.cpp b/Problems/0128.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+ int longestConsecutive(vector<int> &nums) {
+ if (!nums.size()) return 0;
+
+ unordered_set<int> us(nums.begin(), nums.end());
+ int res = 0;
+
+ for (int num : us) {
+ if (!us.count(num - 1)) {
+ int crnt = num;
+ while (us.count(crnt + 1)) crnt += 1;
+ res = max(longestStreak, crnt - num);
+ }
+ }
+
+ return res + 1;
+ }
+};
diff --git a/README.md b/README.md
@@ -26,9 +26,11 @@ for solving problems.
| 0001 | Easy | [Two Sum](Problems/0001.cpp) |
| 0002 | Medium | [Add Two Numbers](Problems/0002.cpp) |
| 0003 | Medium | [Longest Substring Without Repeating Characters](Problems/0003.cpp) |
+| 0011 | Medium | [Container With Most Water](Problems/0011.cpp) |
| 0012 | Medium | [Integer to Roman](Problems/0012.cpp) |
| 0013 | Easy | [Roman to Integer](Problems/0013.cpp) |
| 0014 | Easy | [Longest Common Prefix](Problems/0014.cpp) |
+| 0015 | Medium | [3Sum](Problems/0015.cpp) |
| 0019 | Medium | [Remove Nth Node From the End of List](Problems/0019.cpp) |
| 0020 | Easy | [Valid Parentheses](Problems/0020.cpp) |
| 0021 | Easy | [Merge Two Sorted Lists](Problems/0021.cpp) |
@@ -40,6 +42,7 @@ for solving problems.
| 0028 | Medium | [Find the Index of the First Occurrence in a String](Problems/0028.cpp) |
| 0035 | Easy | [Search Insert Position](Problems/0035.cpp) |
| 0036 | Medium | [Valid Sudoku](Problems/0036.cpp) |
+| 0042 | Medium | [Trapping Rain Water](Problems/0011.cpp) |
| 0043 | Medium | [Multiply Strings](Problems/0043.cpp) |
| 0049 | Medium | [Group Anagrams](Problems/0049.cpp) |
| 0053 | Medium | [Maximum Subarray](Problems/0053.cpp) |
@@ -78,6 +81,7 @@ for solving problems.
| 0122 | Medium | [Best Time to Buy and Sell Stock II](Problems/0122.cpp) |
| 0124 | Hard | [Binary Tree Maximum Path Sum](Problems/0124.cpp) |
| 0125 | Easy | [Valid Palindrome](Problems/0125.cpp) |
+| 0128 | Medium | [Longest Consecutive Sequence](Problems/0128.cpp) |
| 0129 | Medium | [Sum Root to Leaf Numbers](Problems/0129.cpp) |
| 0131 | Medium | [Palindrome Partitioning](Problems/0131.cpp) |
| 0133 | Medium | [Clone Graph](Problems/0133.cpp) |
