Linked list## 2864. Maximum Odd Binary Number (2024/03/01)
### Topic
Two pointers
### Solution
The last bit must be _1_ to make it odd.
1. Count the number of _1_ bits.
2. Generate a new string. Use _1s_ first, if there are remaining quota. And reserve one _1_ for the end of the string.
#### Better solution
This method is in-place.
1. Make sure the last bit is _1_ (swap from the start of the string).
2. Use two pointers start from both ends (exclude the last bit). Make sure to swap _1s_ to the left side.
### Code
```cpp=
class Solution {
public:
string maximumOddBinaryNumber(string s) {
int num_1 = 0;
int len_s = s.length();
for (auto c : s) {
if (c == '1') {
num_1++;
}
}
string res = "";
for (int i = 0; i < len_s - 1; i++) {
if (num_1 - 1) {
res += '1';
num_1--;
} else {
res += '0';
}
}
res += '1';
return res;
}
};
```
## 977. Squares of a Sorted Array (2024/03/02)
### Topic
Two pointers, Stack
### Solution
1. Store negated negative numbers in a stack.
2. Append the remaining numbers into a new array, but compare the inserting number with the top of the stack. If the top of the stack is smaller, then insert it first.
3. Flush the remaining numbers in the stack.
#### Simpler solution
1. Use two pointers and iterate from both sides of the _nums_.
2. Append the smaller number into the result array after square them till every number is checked.
### Code
```cpp=
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
stack<int> negatives;
vector<int> result;
int i = 0;
while (i < nums.size() && nums[i] < 0) {
nums[i] *= -1;
negatives.push(nums[i]);
i++;
}
while (i < nums.size()) {
if (!negatives.empty() && negatives.top() < nums[i]) {
auto negated = negatives.top();
result.push_back(negated * negated);
negatives.pop();
} else {
result.push_back(nums[i] * nums[i]);
i++;
}
}
while (!negatives.empty()) {
auto negated = negatives.top();
result.push_back(negated * negated);
negatives.pop();
}
return result;
}
};
```
## 19. Remove Nth Node From End of List (2024/03/03)
### Topic
Two pointers, Linked list
### Solution
1. Store the parent of each node and count the number of nodes through the first pass.
2. Calculate the node to remove.
#### Better solution
This method requires less memory.
1. Use two pointers that the second pointer is behind the first one by _n_.
2. Remove the Nth node while the first pointer hit the end.
### Code
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head->next) {
return (ListNode*)nullptr;
}
vector<ListNode*> parents;
auto iter = head;
int count = 0;
while (iter) {
count++;
parents.push_back(iter);
iter = iter->next;
}
auto remove_pos = count - n;
if (remove_pos > 0) {
parents[remove_pos-1]->next = parents[remove_pos]->next;
delete parents[remove_pos];
} else {
auto old_head = head;
head = head->next;
delete old_head;
}
return head;
}
};
```
## 948. Bag of Tokens (2024/03/04)
### Topic
Two pointers, Sorting, Greedy
### Solution
### Code
```cpp=
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
if (tokens.empty()) {
return 0;
}
sort(tokens.begin(), tokens.end());
auto front = tokens.cbegin();
auto tail = tokens.cend() - 1;
int score = 0;
int max_score = 0;
while (front <= tail) {
if (power >= *front) {
power -= *front;
front++;
score++;
max_score = max(score, max_score);
} else if (score > 0) {
score--;
power += *tail;
tail--;
} else {
break;
}
}
return max_score;
}
};
```
## 1750. Minimum Length of String After Deleting Similar Ends (2024/03/05)
### Topic
Two pointers
### Solution
Remove as many character as possible, while the character at the both ends are the same. Stop when the remaining string starts and ends with different characters.
#### Better solution
Use another while inside the main while loop the process the repeated characters faster.
## 141. Linked List Cycle (2024/03/06)
### Topic
Linked list, Two pointers
### Solution
Two runners with different but constant speed must meet each other some time.
### Code
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
auto slow = head;
auto fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
return true;
}
}
return false;
}
};
```
## 876. Middle of the Linked List (2024/03/07)
### Topic
Linked list, Two pointers
### Solution
The same as **141**.
### Code
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
auto fast = head;
auto slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
```
## 3005. Count Elements With Maximum Frequency (2024/03/08)
### Topic
Array, Hash table
### Solution
1. Take an array as a hash table and count the frequencies.
2. Iterate through the hash table and keep track of the highest frequency found and its sum.
#### Better solution
Use unordered_map instead of array could reduce memory use.
### Code
```cpp=
class Solution {
public:
int maxFrequencyElements(vector<int>& nums) {
array<int, 101> hash;
for (auto num : nums) {
hash[num]++;
}
int maxcount = 0;
int result = 0;
for (int i = 1; i < 101; i++) {
if (hash[i] > maxcount) {
maxcount = hash[i];
result = hash[i];
} else if (hash[i] == maxcount) {
result += hash[i];
}
}
return result;
}
};
```
## 2540. Minimum Common Value (2024/03/09)
### Topic
Array, Two pointers
### Solution
Compare between the pointer on each array.
### Code
```cpp=
class Solution {
public:
int getCommon(vector<int>& nums1, vector<int>& nums2) {
int i = 0;
int j = 0;
auto max_i = nums1.size();
auto max_j = nums2.size();
int result = -1;
while (i < max_i && j < max_j) {
if (nums1[i] == nums2[j]) {
result = nums1[i];
break;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
i++;
}
}
return result;
}
};
```
## 349. Intersection of Two Arrays (2024/03/10)
### Topic
Array, Two pointers
### Solution
Like 2540 but with one more condition on non-repeting results.
### Code
```cpp=
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
int i = 0;
int j = 0;
auto max_i = nums1.size();
auto max_j = nums2.size();
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> result;
while (i < max_i && j < max_j) {
if (nums1[i] == nums2[j]) {
if (result.empty() || result.back() != nums1[i]) {
result.push_back(nums1[i]);
} else {
i++;
j++;
}
} else if (nums1[i] > nums2[j]) {
j++;
} else {
i++;
}
}
return result;
}
};
```
## 791. Custom Sort String (2024/03/11)
### Topic
### Solution
### Code
```cpp=
class Solution {
public:
string customSortString(string order, string s) {
array<int, 26> hash;
string result = "";
for (char &c : s) {
hash[c-97]++;
}
for (char &rule : order) {
if (hash[rule-97] > 0) {
result += string(hash[rule-97], rule);
hash[rule-97] = 0;
}
}
for (int i = 0; i < 26; i++) {
if (hash[i] > 0) {
result += string(hash[i], i + 97);
}
}
return result;
}
};
```
## 1171. Remove Zero Sum Consecutive Nodes from Linked List (2024/03/12)
## 2485. Find the Pivot Integer (2024/03/13)
## 930. Binary Subarrays With Sum (2024/03/14)
## 238. Product of Array Except Self (2024/03/15)
### Topic
Prefix sum
### Solution
1. Calculate the prefix sum and the suffix sum of the input.
### Code
```cpp=
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> prefix(nums.size());
vector<int> suffix(nums.size());
prefix[0] = nums[0];
suffix[suffix.size()-1] = nums[nums.size()-1];
for (int i = 1; i < prefix.size(); i++) {
prefix[i] = prefix[i-1] * nums[i];
}
for (int i = suffix.size()-2; i >= 0; i--) {
suffix[i] = suffix[i+1] * nums[i];
}
vector<int> result(nums.size());
for (int i = 0; i < result.size(); i++) {
auto p = 1;
auto s = 1;
if (i - 1 >= 0) {
p = prefix[i-1];
}
if (i + 1 < result.size()) {
s = suffix[i+1];
}
result[i] = p * s;
}
return result;
}
};
```
## 525. Contiguous Array (2024/03/16)
## 57. Insert Interval (2024/03/17)
### Topic
Array
### Solution
1. Check for the edge cases: empty intervals, new interval is inserted at the front or at the end of the intervals.
2. Loop through the intervals. If the interval does not intersect with the new interval, append the interval to the output array. If the new interval is located between two contiguous intervals, append the new interval.
3. If the interval intersects with the new interval, extend the start or the end of the new interval.
#### Better solution
We can simplify the process into three stages:
1. Append the intervals before the new interval.
2. Merge the intersected intervals.
3. Append the intervals after the new interval.
### Code
```cpp=
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
if (intervals.empty()) {
result.push_back(newInterval);
return result;
}
if (newInterval[1] < intervals[0][0]) {
intervals.insert(intervals.begin(), newInterval);
return intervals;
}
if (newInterval[0] > intervals[intervals.size()-1][1]) {
intervals.push_back(newInterval);
return intervals;
}
for (int i = 0; i < intervals.size(); ++i) {
if (intervals[i][1] < newInterval[0] || intervals[i][0] > newInterval[1]) {
result.push_back(intervals[i]);
if (intervals[i][1] < newInterval[0] && i+1 < intervals.size() && intervals[i+1][0] > newInterval[1]) {
result.push_back(newInterval);
}
} else {
while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
if (intervals[i][0] < newInterval[0]) {
newInterval[0] = intervals[i][0];
}
if (intervals[i][1] > newInterval[1]) {
newInterval[1] = intervals[i][1];
}
i++;
}
result.push_back(newInterval);
if (i < intervals.size()) {
result.push_back(intervals[i]);
}
}
}
return result;
}
};
```
## 452. Minimum Number of Arrows to Burst Balloons (2024/03/18)
### Topic
Array, Greedy
### Solution
1. Sort the balloons by their start position.
2. Merge as many balloons as possible. While merging, the new balloon size shrinks according to the incoming balloons. Count the number of shrunk balloons at the same time.
### Code
```cpp=
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return a[0] < b[0];
});
array<int, 2> balloon = {points[0][0], points[0][1]};
int arrows = 1;
for (int i = 1; i < points.size(); i++) {
if (points[i][0] <= balloon[1]) {
balloon[0] = points[i][0];
if (points[i][1] < balloon[1]) {
balloon[1] = points[i][1];
}
} else {
balloon[0] = points[i][0];
balloon[1] = points[i][1];
arrows++;
}
}
return arrows;
}
};
```
## 1669. Merge In Between Linked Lists (2024/03/20)
### Topic
Linked list
### Solution
### Code
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
auto node_index = 0;
auto cur = list1;
while (node_index < a - 1) {
cur = cur->next;
node_index++;
}
auto to_delete = cur->next;
node_index++;
cur->next = list2;
while (cur->next) {
cur = cur->next;
}
while (node_index < b) {
to_delete = to_delete->next;
node_index++;
}
cur->next = to_delete->next;
return list1;
}
};
```
## 287. Find the Duplicate Number (2024/03/25)
### Topic
Two pointers
### Solution
#### Key
* Tortoise and hare algorithm [ref](https://chiafangsung.medium.com/%E6%89%BE%E5%87%BA%E9%87%8D%E8%A4%87%E6%95%B8%E5%AD%97-floyd-cycle-detection-algorithm-%E9%BE%9C%E5%85%94%E8%B3%BD%E8%B7%91%E6%BC%94%E7%AE%97%E6%B3%95-c7c2a0315f68)
* Use the value as the index to the next value
#### Follow up
1. Pigeonhole principle
2. Tortoise and hare algorithm
### Code
```cpp=
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0];
int fast = nums[0];
slow = nums[slow];
fast = nums[nums[fast]];
while (nums[fast] != nums[slow]) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
};
```
## 41. First Missing Positive (2024/03/26)
### Topic
Array, Hash table
### Solution
Key: Like _287_, use the array as a hash table.
1. Mark the negative and out-of-bound numbers as 0.
2. Iterate through the array and mark visited numbers as negative.
3. Find the first non-negative number and plus 1 is the answer. If there is no non-negative number in the array, array size plus 1 is the answer.
#### Better solution
* It is unnecessary to take care of positive out-of-bound numbers.
### Code
```cpp=
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for (auto &num : nums) {
if (num < 0 || num > nums.size()) {
num = 0;
}
}
for (auto num : nums) {
if (num != 0 && num != -nums.size() - 2) {
if (num < 0) {
num *= -1;
}
if (nums[num-1] > 0) {
nums[num-1] *= -1;
} else if (nums[num-1] == 0) {
nums[num-1] = -nums.size() - 2;
}
}
}
for (int i = 0; i < nums.size(); i++) {
if (nums[i] >= 0) {
return i + 1;
}
}
return nums.size() + 1;
}
};
```
## 713. Subarray Product Less Than K (2024/03/28)
### Topic
Sliding window
### Solution
According to the hint
> For each j, let opt(j) be the smallest i
> so that nums[i] * nums[i+1] * ... * nums[j] is less than k.
> opt is an increasing function.
>
For every number in the array, calculate how many number before it can form the valid subarray.
#### Alternative solution
While it depends on the distribution of the test cases. In the case, we can calculate the products reversely with division.
### Code
```cpp=
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
auto ans = 0;
for (int j = 0; j < nums.size(); j++) {
auto product = 1;
for (int i = j; i >= 0; i--) {
if (product * nums[i] < k) {
product *= nums[i];
ans++;
} else {
break;
}
}
}
return ans;
}
};
```
## 2958. Length of Longest Subarray With at Most K Frequency (2024/03/28)
### Topic
Sliding window
### Solution
Like _713_, we get the similar hint
> For each index i, find the rightmost index j >= i
> such that the frequency of each element in the subarray [i, j] is at most k.
For every number in the array, we start from it and count the frequencies of each number with a hash table.
#### Better solution
Sliding window
### Code
```cpp=
class Solution {
public:
int maxSubarrayLength(vector<int>& nums, int k) {
unordered_map<int, int> map;
int ans = 0;
auto length = 0;
int j = 0;
auto end = false;
for (int i = 0; i < nums.size(); i++) {
if (i - 1 >= 0) {
map[nums[i-1]]--;
length--;
}
for (; j < nums.size(); j++) {
if (map.find(nums[j]) == map.end()) {
map[nums[j]] = 1;
} else if (map[nums[j]] == k) {
break;
} else {
map[nums[j]]++;
if (j == nums.size()-1) {
end = true;
}
}
length++;
}
ans = max(ans, length);
if (end) {
break;
}
}
return ans;
}
};
```
## 992. Subarrays with K Different Integers (2024/03/30)
Sign in with Wallet
Connect another wallet