# Grind 169
- [Grind75](https://www.techinterviewhandbook.org/grind75?grouping=weeks&order=topics&difficulty=Easy&difficulty=Medium&difficulty=Hard&weeks=26&hours=7#)
- [CodeForce educational course](https://codeforces.com/edu/course/2)
- [labuladong的演算法筆記](https://labuladong.github.io/algo/)
- [0到100的軟體工程師面試之路](https://ithelp.ithome.com.tw/users/20152262/ironman/5615)
- [Huifeng Guan](https://www.youtube.com/@wisdompeak)
- https://meet.google.com/sww-vxmx-kge
## Array
### [1. Two Sum](https://leetcode.com/problems/two-sum/)
```python=
# Time O(n)
# Space O(n)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
counter = 0
map = {}
for i in nums:
if (target - i in map) :
return [map[target-i], counter]
map[i] = counter
counter += 1
```
### [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
```cpp=
// Time complexity: O(N)
// Space complexity: O(N)
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> maxPrice(prices.size(), 0);
int ans = 0;
for (int i = prices.size() - 1; i >= 0; i--) {
if (i == (prices.size() - 1))
maxPrice[i] = prices[i];
else {
maxPrice[i] = max(maxPrice[i+1], prices[i+1]);
}
}
for (int i = 0; i < prices.size(); i++) {
ans = max(ans, maxPrice[i] - prices[i]);
}
return ans;
}
};
```
```python=
# Time O(n)
# Space O(1)
def maxProfit(self, prices):
curMin = prices[0]
maxVal = 0
for price in prices:
if price < curMin:
curMin = price
if (price - curMin) > maxVal:
maxVal = price - curMin
return maxVal
```
### [57. Insert Interval](https://leetcode.com/problems/insert-interval/)
```cpp=
// Time complexity: O(logN)
// Space complexity: O(N)
bool comp(vector<int>& interval, int val) {
return interval[1] < val;
}
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> ans;
auto lb = lower_bound(intervals.begin(), intervals.end(), newInterval[0], comp);
auto it = intervals.begin();
for (; it != lb; ++it) {
ans.push_back(*it);
}
for (; it != intervals.end(); ++it) {
vector<int>& interval = *it;
if (interval[0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], interval[0]);
newInterval[1] = max(newInterval[1], interval[1]);
}
else {
break;
}
}
ans.push_back(newInterval);
for (; it != intervals.end(); ++it) {
ans.push_back(*it);
}
return ans;
}
};
```
```cpp=
// Time complexity: O(N)
// Space complexity: O(1)
class Solution {
bool isOverlap(vector<int>& vec1, vector<int>& vec2) {
return !(vec1[1] < vec2[0] || vec2[1] < vec1[0]);
}
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> ans;
for (auto& interval : intervals) {
if (isOverlap(interval, newInterval)) {
newInterval[0] = min(interval[0], newInterval[0]);
newInterval[1] = max(interval[1], newInterval[1]);
} else {
if (interval[1] < newInterval[0]) {
ans.push_back(interval);
} else {
ans.push_back(newInterval);
ans.push_back(interval);
newInterval[0] = newInterval[1] = INT_MAX;
}
}
//cout << newInterval[0] << " " << newInterval[1] << endl;
}
if (newInterval[0] != INT_MAX) {
ans.push_back(newInterval);
}
return ans;
}
};
/*
## overlap
case 1
[ ]
[ ]
case 2
[ ]
[]
case 3
[ ]
[ ]
case 4
[ ]
[ ]
## non-overlap
case 1
[ ]
[]
case 2
[ ]
[]
demorgen
!(a || b)
0 0 1
1 0 0
0 1 0
1 1 0
(!a && !b)
0 0 1
*/
```
### [15. 3Sum](https://leetcode.com/problems/3sum/description/)
```cpp=
// Time complexity: O(N^2)
// Space complexity: O(N^2)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
if (nums[0] > 0) return {};
unordered_map<int, int> m;
int n = nums.size();
vector<vector<int>> ans;
for (int i = 0; i < n; i++) m[nums[i]] = i;
for (int i = 0; i < n-2; i++) {
if (i != 0 && nums[i] == nums[i-1]) continue; // skip the same number
if (nums[i] > 0) return ans;
for (int j = i + 1; j < n-1; j++) {
if (j != i+1 && nums[j] == nums[j-1]) continue; // skip the same number
int target = -nums[i] - nums[j];
if (m.find(target) != m.end() && m[target] > j)
ans.push_back({nums[i], nums[j], target});
}
}
return ans;
}
};
```
### [169. Majority Element](https://leetcode.com/problems/majority-element/description/)
```csharp=
//Time: O(n)
//Space: O(n)
var map = new Dictionary<int, int>();
foreach (var val in nums)
{
if (map.ContainsKey(val))
{
map[val]++;
}
else
{
map.Add(val, 1);
}
}
foreach (var val in nums)
{
if (map[val]>(nums.Length/2))
{
return val;
}
}
return 0;
```
```csharp=
//Time: O(n)
//Space: O(1)
var count = 0;
var ans = 0;
foreach (var num in nums)
{
if (count == 0)
{
ans = num;
}
if (num == ans)
{
count++;
}
else
{
count--;
}
}
return ans;
```
### [238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/description/)
```cpp=
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int size = nums.size(), mul = 1;
vector<int> ans(size, 1);
for (int i = 1; i < size; i++) {
mul *= nums[i-1];
ans[i] = mul;
}
for (int i = size-2, mul = 1; i >= 0; i--) {
mul *= nums[i+1];
ans[i] *= mul;
}
return ans;
}
};
/*
1 2 3
1 2
1
2 3 4
3 4
4
*/
```
### [39. Combination Sum](https://leetcode.com/problems/combination-sum/description/)
```cpp=
// Time complexity: O(N^(target/min(candidates)))
// Space complexity: O(N*(target/min(candidates)))
class Solution {
vector<vector<int>> ans;
int target_ = 0;
int size = 0;
public:
void bt(vector<int> choose, int sum, int idx, vector<int>& candidates) {
if (sum == target_) {
ans.push_back(choose);
return;
} else if (sum > target_) {
return;
}
for (int i = idx; i < size; i++) {
sum += candidates[i];
choose.push_back(candidates[i]);
bt(choose, sum, i, candidates);
sum -= candidates[i];
choose.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
target_ = target;
size = candidates.size();
bt({}, 0, 0, candidates);
return ans;
}
};
```
### [56. Merge Intervals](https://leetcode.com/problems/merge-intervals/)
```cpp=
class Solution {
// Assume a[0] < b[0]
bool isOverlap(vector<int>& a, vector<int>& b) {
return a[1] >= b[0];
}
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> ans;
vector<int> merged = intervals[0];
for (int i = 1; i < intervals.size(); i++) {
if (isOverlap(merged, intervals[i])) {
merged[0] = min(merged[0], intervals[i][0]);
merged[1] = max(merged[1], intervals[i][1]);
} else {
ans.push_back(merged);
merged = intervals[i];
}
}
ans.push_back(merged);
return ans;
}
};
```
```csharp=
//Time O(nlogn) sorting
//Space O(n)
public int[][] Merge(int[][] intervals)
{
Array.Sort(intervals, (x, y) => x[0].CompareTo(y[0]));
var ans = new List<int[]>() {
intervals[0]
};
int index = 0;
foreach (var interval in intervals)
{
if (interval[0] <= ans[index][1])
{
if (ans[index][1]<interval[1])
{
ans[index] = new[]
{
ans[index][0], interval[1]
};
}
}
else
{
ans.Add(interval);
index++;
}
}
return ans.ToArray();
}
```
### [75. Sort Colors](https://leetcode.com/problems/sort-colors/)
```csharp=
//space : O(1)
//time: O(n)
public class Solution {
public void SortColors(int[] nums)
{
var map = new Dictionary<int,int>()
{
[0] = 0,
[1] = 0,
[2] = 0
};
foreach (var num in nums)
{
map[num]++;
}
int index = 0;
for (int i = 0; i <= 2 ; i++)
{
for (int j = 0; j < map[i]; j++,index++)
{
nums[index] = i;
}
}
}
}
```
```csharp=
//using swap
//Time : O(n)
//Space: O(1)
public class Solution {
public void SortColors(int[] nums)
{
int left = 0;
int right = nums.Length;
for (int i = 0; i <= right;)
{
if (nums[i] == 2)
{
Swap(right, i);
right--;
}
else if (nums[i] == 0)
{
Swap(left,i);
left++;
i++;
}
else
{
i++;
}
void Swap(int j, int i)
{
var tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
}
```
### [217. Contains Duplicate](https://leetcode.com/problems/contains-duplicate/description/)
```cpp=
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> record;
for (int num : nums) {
if (record.count(num) > 0)
return true;
record.insert(num);
}
return false;
}
};
```
### [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/description/)
```cpp=
// Time complexity: O(N)
// Space complexity: O(N)
class Solution {
public:
int maxArea(vector<int>& height) {
deque<int> leftIdx, rightIdx;
leftIdx.push_back(0);
rightIdx.push_back(height.size()-1);
for (int i = 1; i < height.size(); i++) {
if (height[i] > height[leftIdx.back()])
leftIdx.push_back(i);
}
for (int i = height.size()-2; i >= 0; i--) {
if (height[i] > height[rightIdx.back()])
rightIdx.push_back(i);
}
int left = leftIdx.front();
leftIdx.pop_front();
int right = rightIdx.front();
rightIdx.pop_front();
int ans = area(height, left, right);
while (!leftIdx.empty() || !rightIdx.empty()) {
if (height[left] <= height[right] && !leftIdx.empty()) {
left = leftIdx.front();
leftIdx.pop_front();
} else if (height[right] <= height[left] && !rightIdx.empty()) {
right = rightIdx.front();
rightIdx.pop_front();
}
ans = max(ans, area(height, left, right));
}
return ans;
}
int area(vector<int>& height, int left, int right) {
return (right - left) * min(height[left], height[right]);
}
};
```
```cpp=
// Time complexity: O(N)
// Space complexity: O(1)
class Solution {
public:
int maxArea(vector<int>& height) {
int lptr = 0, rptr = height.size() - 1, ans = 0;
while (lptr < rptr) {
int area = (rptr - lptr) * min(height[lptr], height[rptr]);
ans = max(ans, area);
if (height[lptr] > height[rptr])
rptr--;
else
lptr++;
}
return ans;
}
};
```
### [134. Gas Station](https://leetcode.com/problems/gas-station/description/)
```csharp=
//Time : O(1)
//Space: O(n)
public int CanCompleteCircuit(int[] gas, int[] cost) {
if ( gas.Sum()-cost.Sum() < 0 )
{
return -1;
}
int remainSum = 0;
int starting = 0;
for (var i = 0; i < gas.Length;i++)
{
remainSum += gas[i]-cost[i];
if (remainSum < 0)
{
starting = i+1;
remainSum = 0;
}
}
return starting;
}
```
### [128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)
```cpp=
// Time complexity: O(N)
// Space complexity: O(N)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> idx;
UF uf(nums.size());
for (int i = 0; i < nums.size(); i++) {
idx[nums[i]] = i;
}
for (int num : nums) {
if (idx.count(num+1) > 0) {
uf.unionf(idx[num], idx[num+1]);
}
if (idx.count(num-1) > 0) {
uf.unionf(idx[num], idx[num-1]);
}
}
return uf.max_size();
}
class UF {
vector<int> parent;
vector<int> size;
int N = 0;
public:
UF(int n) : N(n) {
for (int i = 0; i < N; i++) {
parent.push_back(i);
size.push_back(1);
}
}
void unionf(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
if (size[rootP] < size[rootQ]) {
size[rootQ] += size[rootP];
parent[rootP] = rootQ;
} else {
size[rootP] += size[rootQ];
parent[rootQ] = rootP;
}
}
int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return parent[p];
}
int max_size() {
return N > 0 ? *max_element(size.begin(), size.end()) : 0;
}
};
};
```
```cpp=
// Time complexity: O(N)
// Space complexity: O(N)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> st(nums.begin(), nums.end());
int ans = 0;
for (int num : st) {
if (st.count(num-1) > 0)
continue;
int count = 0;
while (st.count(num+count) > 0) {
++count;
}
ans = max(ans, count);
}
return ans;
}
};
```
### [189. Rotate Array](https://leetcode.com/problems/rotate-array/description/)
```csharp=
//Time : O(n)
//Space: O(3)
public class Solution {
public void Rotate(int[] nums, int k) {
k = k % nums.Length;
Array.Reverse(nums);
Array.Reverse(nums, 0, k);
Array.Reverse(nums, k, nums.Length-k);
}
}
```
### [525. Contiguous Array](https://leetcode.com/problems/contiguous-array/)
```cpp=
// Time complexity: O(N)
// Space complexity: O(N)
class Solution {
public:
int findMaxLength(vector<int>& nums) {
// counter -> index
unordered_map<int, int> mp = {{0, -1}};
int counter = 0, ans = 0;
for (int i = 0; i < nums.size(); i++) {
counter += nums[i] == 0 ? -1 : 1;
if (mp.count(counter) > 0) {
ans = max(ans, i - mp[counter]);
} else {
mp[counter] = i;
}
}
return ans;
}
};
```
### [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/description/)
```cpp=
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int left = 0, right = 1;
while (right < nums.size()) {
while (left < nums.size() && nums[left] != 0)
++left;
while (right < nums.size() && (nums[right] == 0 || right <= left))
++right;
if (left < nums.size() && right < nums.size())
swap(nums[left], nums[right]);
}
}
};
```
### [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/description/)
```cpp=
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> record = {{0, 1}};
int ans = 0, sum = 0;
for (int num : nums) {
sum += num;
ans += record[sum - k];
record[sum]++;
}
return ans;
}
};
```
Sign in with Wallet
Connect another wallet