1️LeetCode
Here I list my solutions and note to avoid mistakes.
Array & Hashing
217 Contains Duplicate
Time complexity o(n). Storage complexity o(n)
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int, int> map;
for (auto num: nums){
if(map.find(num)==map.end()){
map[num] = 1;
}else{
map[num] += 1;
}
}
for (auto num : map ){
if (num.second>1){
return true;
}
}
return false;
}
};242 Valid Anagram
Time complexity o(n). Storage complexity o(n)
Initialization to zeros!
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for(int i=0; i<s.size(); i++){
record[s[i]-'a'] += 1;
}
for(int i=0; i<t.size(); i++){
record[t[i]-'a'] -= 1;
}
for(int i = 0; i < 26; i++){
if(record[i] != 0) return false;
}
return true;
}
};1 Two Sum
Time complexity o(n). Storage complexity o(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> record;
for(int i=0; i<nums.size(); i++){
int diff = target - nums[i];
if(record.count(diff) == 0){
record[nums[i]] = i;
} else {
return {record[diff], i};
}
}
return {};
}
};49 Group Anagrams
Solution 1
Time: O(n x l) -> n = length of strs, l = max length of a string in strs
Space: O(n x l)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> m;
vector<vector<string>> result;
for(int i=0; i<strs.size(); i++){
string key = getKey(strs[i]);
m[key].push_back(strs[i]);
}
for(auto it = m.begin(); it!=m.end(); it++){
result.push_back(it->second);
}
return result;
}
private:
string getKey(string str){
vector<int> counter(26, 0);
for(int j=0; j<str.size(); j++){
counter[str[j] - 'a'] += 1;
}
string key = "";
for(int j=0; j<counter.size(); j++){
key.append(to_string(counter[j]+'#'));
}
return key;
}
};Solution 2
Time: O(n x l) -> n = length of strs, l = max length of a string in strs
Space: O(n x l)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> m;
vector<vector<string>> result;
for(int i=0; i<strs.size(); i++){
string key = getKey(strs[i]);
m[key].push_back(strs[i]);
}
for(auto it = m.begin(); it!=m.end(); it++){
result.push_back(it->second);
}
return result;
}
private:
string getKey(string str){
vector<int> counter(26, 0);
for(int j=0; j<str.size(); j++){
counter[str[j] - 'a'] += 1;
}
string key = "";
for(int j=0; j<counter.size(); j++){
key.append(to_string(counter[j]+'#'));
}
return key;
}
};347 Top K Frequent Elements
Solution 1
Time o(n) Space o(n)
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> m;
for(int num : nums){
m[num] ++;
}
vector<vector<int>> freq(n+1);
for(auto it=m.begin(); it!=m.end(); it++){
freq[it->second].push_back(it->first);
}
vector<int> result;
for(int i=n; i>=0; i--){
if(result.size() >= k) {
break;
}
if(!freq[i].empty()){
result.insert(result.end(), freq[i].begin(), freq[i].end());
}
}
return result;
}
};Solution 2 Heap
Time: O(n log k) Space: O(n + k)
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i++) {
m[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int, int>>> pq;
for (auto it = m.begin(); it != m.end(); it++) {
pq.push({it->second, it->first});
if (pq.size() > k) {
pq.pop();
}
}
vector<int> result;
while (!pq.empty()) {
result.push_back(pq.top().second);
pq.pop();
}
return result;
}
};238 Product of Array Except Self
Solution 1
Time O(n) Space O(n)
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> result(nums.size(), 1);
vector<int> prefix(nums.size(), 1);
vector<int> suffix(nums.size(), 1);
for(int i=0; i<nums.size(); i++){
int j = nums.size() - i - 1;
if(i != 0){
prefix[i]= prefix[i-1]*nums[i-1];
}
if(j != nums.size()-1){
suffix[j]= suffix[j+1]*nums[j+1];
}
}
for(int i=0; i<nums.size(); i++){
result[i] = prefix[i]*suffix[i];
}
return result;
}
};Solution 2
Time O(n) Space O(1)
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int prefix = 1, suffix = 1;
vector<int> result(nums.size(), 1);
for(int i=1; i<nums.size(); i++){
prefix *= nums[i-1];
result[i] *= prefix;
}
for(int i=nums.size()-2; i>=0; i--){
suffix *= nums[i+1];
result[i] *= suffix;
}
return result;
}
};36 Valid Sudoku
Time O(cnt^2) Space O(cnt^2)
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
const int cnt = 9;
bool row[cnt][cnt] = {false};
bool col[cnt][cnt] = {false};
bool box[cnt][cnt] = {false};
for(int i=0; i<cnt; i++){
for(int j=0; j<cnt; j++){
if (board[i][j]=='.') continue;
int idx = board[i][j] - '0' - 1;
if(row[i][idx]) return false;
if(col[j][idx]) return false;
if(box[(i/3)*3+ j/3][idx]) return false;
row[i][idx] = true;
col[j][idx] = true;
box[(i/3)*3+ j/3][idx] = true;
}
}
return true;
}
};Encode and Decode Strings
Time O(n) Space O(1)
class Solution {
public:
// Encodes a list of strings to a single string.
string encode(vector<string>& strs) {
string result = "";
for (int i = 0; i < strs.size(); i++) {
string str = strs[i];
result += to_string(str.size()) + "#" + str;
}
return result;
}
// Decodes a single string to a list of strings.
vector<string> decode(string s) {
vector<string> result;
int i = 0;
while (i < s.size()) {
int j = i;
while (s[j] != '#') {
j++;
}
int length = stoi(s.substr(i, j - i));
string str = s.substr(j + 1, length);
result.push_back(str);
i = j + 1 + length;
}
return result;
}
};
128 Longest Consecutive Sequence
Time O(n), Space O(n)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int longest = 0;
for(auto &n:s){
if(!s.count(n-1)){
int length = 1;
while(s.count(n+length)){
length++;
}
longest = max(longest, length);
}
}
return longest;
}
};Two Pointers
15 3Sum
Time O(nlogn) + O(n^2) Space O(1)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for(int i=0; i<nums.size()-1; i++){
if(i>0 && nums[i] == nums[i-1]) continue;
if(nums[i]>0) continue;
int left = i+1, right = nums.size()-1;
while(left<right){
int val = nums[i] + nums[left] + nums[right];
if(val>0){
right -= 1;
} else if(val < 0) {
left += 1;
} else {
res.push_back({nums[i], nums[left], nums[right]});
while(left<right && nums[left] ==nums[left+1]) {left++;}
while(left<right && nums[right] ==nums[right-1]) {right--;}
left++;
right--;
}
}
}
return res;
}
};16 3Sum Closest
Time O(nlogn) + O(n^2) Space O(1)
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end()); //sort the vector
int n = nums.size();
int best = 1e7;
//define lambda function
auto update = [&best, target](int cur){
if(abs(cur - target) < abs(best - target)){
best = cur;
}
};
for(int i=0; i< n; i++){
//remove repetition
if(i>0 && nums[i] == nums[i-1]){
continue;
}
int j = i+1, k= n-1;
while(j<k){
int sum = nums[i] + nums[j] + nums[k];
if(sum == target){
return target;
}
update(sum);
if(sum > target){
int k0 = k -1;
while(j<k0 && nums[k0] == nums[k]){
--k0;
}
k = k0;
} else {
int j0 = j+1;
while(j0 < k && nums[j0] == nums[j]) {
j0++;
}
j = j0;
}
}
}
return best;
}
};167 Two Sum II - Input Array Is Sorted
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size()-1;
int curSum;
while(left < right) {
curSum = numbers[left] + numbers[right];
if(curSum == target) return {left+1, right+1};
if(curSum > target) {right = right - 1;}
if(curSum < target) {left = left + 1;}
}
return {};
}
};Time Complexity o(n). Storage Complexity o(1)
125 Valid Palindrome
Time O(|s|) Space O(|s|)
class Solution {
public:
string preprocess(string s){
string ans;
for(char ch: s){
if(isalnum(ch)){
ans += tolower(ch);
}
}
return ans;
}
bool isPalindrome(string s) {
string s1 = preprocess(s);
if(!s1.size()) return true;
int left = 0, right = s1.size() - 1;
while(left < right){
if(s1[left] != s1[right]){
return false;
}
left++;
right--;
}
return true;
}
};11 Container With Most Water
Time O(n), space O(1)
class Solution {
public:
int maxArea(vector<int>& height) {
int best = 0;
int left = 0, right = height.size()-1;
while(left < right){
int area = (right - left)*min(height[left], height[right]);
best = max(best, area);
if(height[left]>height[right]){
right--;
} else if(height[left]<height[right]){
left++;
} else {
left++;
}
}
return best;
}
};Sliding Window
53 Maximum Subarray
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSub = nums[0];
int curSum = 0;
for(int num : nums){
if(curSum < 0) curSum = 0;
curSum += num;
maxSub = max(maxSub, curSum);
}
return maxSub;
}
};
// maxSub initializes as the first element of the vector.
// Time complexity o(n). Storage complexity o(n);
3 Longest Substring Without Repeating Characters
Time: O(n) Space: O(n)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
unordered_set<char> set;
int maxlen = 0, left = 0;
for(int i=0; i<s.size(); i++){
while(set.find(s[i]) != set.end()){
set.erase(s[left]);
left++;
}
maxlen = max(maxlen, i - left + 1);
set.insert(s[i]);
}
return maxlen;
}
};424 Longest Repeating Character Replacement
Time: O(n) Space: O(26)
class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> cnt(26);
int result = 0, maxCount = 0;
int i = 0, j = 0;
while(j < s.length()){
cnt[s[j] - 'A'] += 1;
maxCount = max(maxCount, cnt[s[j] - 'A']);
if(j - i + 1- maxCount > k){
cnt[s[i] - 'A'] -= 1;
i++;
}
result = max(result, j - i + 1);
j++;
}
return result;
}
};567 Permutation In String
Time: O(n) Space: O(1)
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n = s1.size(), m = s2.size();
if (n > m) return false;
vector<int> v1(26, 0), v2(26, 0);
for(int i=0; i<n; i++){
v1[s1[i] - 'a'] ++;
v2[s2[i] - 'a'] ++;
}
if(v1 == v2) return true;
for(int i=n; i<m; i++){
v2[s2[i] - 'a'] ++;
v2[s2[i -n] - 'a'] --;
if(v1 == v2) return true;
}
return false;
}
};76 Minimum Window Substring
Time: O(m + n) Space: O(m + n)
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> map;
for(int i=0; i<t.size(); i++){
map[t[i]] ++;
}
int counter = t.size();
int minStart = 0;
int minLength = INT_MAX;
int left = 0, right = 0; // two sides of the sliding window
while(right < s.size()){
if(map[s[right]] > 0) {
counter --;
}
map[s[right]] --;
right ++;
while(counter == 0){
if(right - left < minLength) {
minStart = left;
minLength = right - left;
}
map[s[left]]++;
if(map[s[left]] > 0) {
counter ++;
}
left++;
}
}
return minLength!=INT_MAX? s.substr(minStart, minLength) : "";
}
};239 Sliding Window Maximum
Time: O(n) Space: O(n)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> result;
int i = 0;
int j = 0;
while( j < nums.size()) {
while (!dq.empty() && nums[dq.back()] < nums[j]) {
dq.pop_back();
}
dq.push_back(j);
if(i > dq.front()) {
dq.pop_front();
}
if(j+1 >= k) {
result.push_back(nums[dq.front()]);
i++;
}
j++;
}
return result;
}
};Brute Force
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res(n-k+1);
for(int i=0; i<n-k+1; i++){
vector<int> subvec = {nums.begin() + i, nums.begin() + i + k};
sort(subvec.begin(), subvec.end());
res[i] = subvec[k-1];
}
return res;
}
};Stack
20 Valid Parentheses
Time O(n) Space O(n)
class Solution {
public:
bool isValid(string s) {
if(!s.size()) return true;
stack<char> st;
for(char ch: s){
if(ch == '('|| ch == '{' || ch == '['){
st.push(ch);
} else {
if(st.empty()) return false;
char tmp = st.top();
if(ch == ')' && tmp != '(') return false;
if(ch == '}' && tmp != '{') return false;
if(ch == ']' && tmp != '[') return false;
st.pop();
}
}
return st.empty()? true : false;
}
};155 Min Stack
Time: O(1) Space: O(n)
class MinStack {
private:
stack<pair<int, int>> st;
public:
MinStack() {
}
void push(int val) {
if(st.empty()) {
st.push({val, val});
} else {
st.push({val, min(val, st.top().second)});
}
}
void pop() {
st.pop();
}
int top() {
return st.top().first;
}
int getMin() {
return st.top().second;
}
};150 Evaluate Reverse Polish Notation
Time: O(n) Space: O(n)
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(int i=0; i<tokens.size(); i++){
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
int right = st.top();
st.pop();
int left = st.top();
st.pop();
if(tokens[i] == "+") st.push(left + right);
if(tokens[i] == "-") st.push(left - right);
if(tokens[i] == "*") st.push(left * right);
if(tokens[i] == "/") st.push(left / right);
} else {
st.push(atoi(tokens[i].c_str()));
}
}
return st.top();
}
};22 Generate Parentheses
Time: O(2^n) Space: O(n)
class Solution {
public:
vector<string> generateParenthesis(int n) {
getParenthesis("", n, n);
return res;
}
private:
vector<string> res;
void getParenthesis(string str, int left, int right){
if(left == 0 && right == 0) {
res.push_back(str);
return;
}
if(left == right) {
getParenthesis(str + "(", left-1, right);
} else if (left < right) {
if(left > 0) {
getParenthesis(str + "(", left-1, right);
}
getParenthesis(str + ")", left, right-1);
}
}
};739 Daily Temperatures (to do)
Time: O(n) Space: O(n)
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
// pair: [index, temp]
stack<pair<int, int>> stk;
vector<int> result(n);
for (int i = 0; i < n; i++) {
int currDay = i;
int currTemp = temperatures[i];
while (!stk.empty() && stk.top().second < currTemp) {
int prevDay = stk.top().first;
int prevTemp = stk.top().second;
stk.pop();
result[prevDay] = currDay - prevDay;
}
stk.push({currDay, currTemp});
}
return result;
}
};Binary Search
704 Binary Search
Time: O(log n)
Space: O(1)
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while(left<=right){
int mid = left + (right-left)*0.5;
if(nums[mid] > target) {
right = mid-1;
} else if (nums[mid] < target) {
left = mid+1;
} else {
return mid;
}
}
return -1;
}
};74 Search a 2D Matrix
Time: O(log m + log n)
Space: O(1)
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int lowRow = 0;
int highRow = matrix.size() - 1;
while (lowRow < highRow) {
int mid = lowRow + (highRow - lowRow) / 2;
if (matrix[mid][0] == target) {
return true;
}
if (matrix[mid][0] < target && target < matrix[mid + 1][0]) {
lowRow = mid;
break;
}
if (matrix[mid][0] < target) {
lowRow = mid + 1;
} else {
highRow = mid - 1;
}
}
int lowCol = 0;
int highCol = matrix[0].size() - 1;
while (lowCol <= highCol) {
int mid = lowCol + (highCol - lowCol) / 2;
if (matrix[lowRow][mid] == target) {
return true;
}
if (matrix[lowRow][mid] < target) {
lowCol = mid + 1;
} else {
highCol = mid - 1;
}
}
return false;
}
};875 Koko Eating Bananas
Time: O(n x log m) -> n = # of piles, m = max # in a pile Space: O(1)
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int low = 1;
int high = 0;
for(int pile : piles) {
high = max(high, pile);
}
int k = high;
while(low < high) {
int speed = (high - low) /2 + low;
long time = getTime(piles, speed);
if(time <= h) {
k = speed;
high = speed;
} else {
low = speed + 1;
}
}
return k;
}
long getTime(vector<int> piles, int speed){
long time = 0;
for( int pile : piles){
int curTime = (pile + speed - 1)/speed;
time += curTime;
}
return time;
}
};153 Find Minimum in Rotated Sorted Array
Time O(logn) Space O(1)
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size()-1;
int res = nums[0];
while(left <= right) {
if(nums[left] < nums[right]) {
res = min(res, nums[left]);
}
int mid = (right - left) /2 + left;
res = min(res, nums[mid]);
if(nums[mid] >= nums[left]){
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
};33 Search in Rotated Sorted Array
Time: O(log n) Space: O(1)
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while(l <= r) {
int mid = (r - l) /2 + l;
if(nums[mid] == target) {
return mid;
}
if(nums[mid] >= nums[l]){
if(nums[l] <= target && target <= nums[mid]){
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if(target < nums[r] && target >= nums[mid]){
l = mid +1;
} else {
r = mid - 1;
}
}
}
return -1;
}
};981 Time Based Key Value Store
Time: O(log n) Space: O(n)
class TimeMap {
public:
TimeMap() {
}
void set(string key, string value, int timestamp) {
m[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
if(m.find(key) == m.end()){
return "";
}
int low = 0;
int high = m[key].size() - 1;
while( low <= high) {
int mid = low + (high - low) /2;
if (m[key][mid].first < timestamp) {
low = mid + 1;
} else if (m[key][mid].first > timestamp) {
high = mid - 1;
} else {
return m[key][mid].second;
}
}
if(high >= 0) {
return m[key][high].second;
}
return "";
}
private:
unordered_map<string, vector<pair<int, string>>> m;
};Binary Tree
226 Invert Binary Tree
Time: O(n) Space: O(n)
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL) return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};104 Maximum Depth of Binary Tree
Time: O(n) Space: O(n)
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return max(left, right) + 1;
}
};543 Diameter of Binary Tree
Time: O(n) Space: O(n)
class Solution {
public:
int dfs(TreeNode* node, int& result){
if(node == nullptr) return 0;
int left = dfs(node->left, result);
int right = dfs(node->right, result);
result = max(result, left+right);
return 1+max(left, right);
}
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
dfs(root, ans);
return ans;
}
};110 Balanced Binary Tree
Time: O(n) Space: O(n)
class Solution {
public:
int dfs(TreeNode* node, bool& flag){
if(node == nullptr) return 0;
int left = dfs(node->left, flag);
int right = dfs(node->right, flag);
flag = flag && (abs(left - right) <= 1);
return 1 + max(left, right);
}
bool isBalanced(TreeNode* root) {
bool flag = true;
dfs(root, flag);
return flag;
}
};100 Same Tree
Time: O(n) Space: O(n)
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) return true;
else if (!p || !q) return false;
bool left = isSameTree(p->left, q->left);
bool right = isSameTree(p->right, q->right);
return (p->val == q->val) && left && right;
}
};572 Subtree of Another Tree
Time: O(m x n) Space: O(m)
class Solution {
public:
bool isSametree(TreeNode* p, TreeNode* q){
if(!p && !q) return true;
else if(!p || !q) return false;
bool left = isSametree(p->left, q->left);
bool right = isSametree(p->right, q->right);
return (p->val == q->val) && left && right;
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (root == nullptr) return false;
if (isSametree(root, subRoot)) {
return true;
}
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};235 Lowest Common Ancestor of a Binary Search Tree
Time: O(n) Space: O(n)
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) return NULL;
if(p->val > root->val && q->val > root->val) {
return lowestCommonAncestor(root->right, p, q);
} else if (p->val < root->val && q->val < root->val) {
return lowestCommonAncestor(root->left, p, q);
} else {
return root;
}
}
};236 Lowest Common Ancestor of a Binary Tree
Time: O(n) Space: O(n)
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL) return NULL;
if( root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;
else if( left) return left;
else if (right) return right;
else return NULL;
}
};102 Binary Tree Level Order Traversal
Time: O(n) Space: O(n)
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
vector<int> t;
if(!root) return {};
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n= q.size();
t.clear();
for(int i=0; i<n; i++){
TreeNode* node = q.front();
q.pop();
t.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
ans.push_back(t);
}
return ans;
}
};938 Range Sum of BST
Time O(n) Space O(n)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* node, int& sum, int low, int high){
if(node == nullptr) return;
if(node->val > high) {
dfs(node->left, sum, low, high);
} else if(node->val < low){
dfs(node->right, sum, low, high);
} else {
sum += node->val;
dfs(node->left, sum, low, high);
dfs(node->right, sum, low, high);
}
}
int rangeSumBST(TreeNode* root, int low, int high) {
int sum = 0;
dfs(root, sum, low, high);
return sum;
}
};Linked List
206 Reverse Linked List
Time: O(n) Space: O(1)
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL) return NULL;
ListNode* prev = NULL;
ListNode* cur = head;
while(cur){
ListNode* tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
};21 Merge Two Sorted Lists
Time: O(m + n) Space: O(1)
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == NULL) return list2;
if(list2 == NULL) return list1;
if(list1->val<list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};142 Reorder List
Time: O(n) Space: O(1)
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
}
ListNode* mid = slow->next;
slow->next = NULL;
ListNode* rev = reverseList(mid);
while(rev) {
ListNode* tmp1 = head->next;
ListNode* tmp2 = rev->next;
rev->next = tmp1;
head->next = rev;
rev = tmp2;
head = tmp1;
}
}
//reverse linked list
ListNode* reverseList(ListNode* node){
ListNode* prev = NULL;
ListNode* cur = node;
while(cur){
ListNode* tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
};19 Remove Nth Node From End of List
Time: O(n) Space: O(1)
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
for (int i =0; i<n; i++){
fast = fast->next;
}
while(fast->next){
slow = slow->next;
fast = fast->next;
}
ListNode* tmp = slow->next->next;
slow->next = tmp;
return dummy->next;
}
};138 Copy List with Random Pointer
Time: O(n) Space: O(n)
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> map;
Node* h = head;
while(h){
map[h] = new Node(h->val);
h=h->next;
}
h = head;
while(h){
map[h]->next = map[h->next];
map[h]->random = map[h->random];
h = h->next;
}
return map[head];
}
};2 Add Two Numbers
Time: O(max(m, n)) Space: O(max(m, n))
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
int carry = 0;
ListNode* cur = dummy;
int sum = 0;
while(l1 != NULL || l2 != NULL){
sum = 0;
if(l1 != NULL) sum += l1->val;
if(l2 != NULL) sum += l2->val;
sum += carry;
cur->next = new ListNode(sum % 10);
cur = cur->next;
carry = sum / 10;
if(l1 != NULL) l1 = l1->next;
if(l2 != NULL) l2 = l2->next;
}
if(carry==1) {
cur->next = new ListNode(1);
}
return dummy->next;
}
};141 Linked List Cycle
Time: O(n) Space: O(1)
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL) return false;
ListNode* fast = head;
ListNode* slow = head;
while(fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
return true;
}
}
return false;
}
};142 Linked List Cycle II
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL || head->next == NULL) return NULL;
ListNode* slow = head;
ListNode* fast = head;
while(fast!=NULL && fast->next!=NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
ListNode* node1 = head;
ListNode* node2 = fast;
while(node1!=node2){
node1 = node1->next;
node2 = node2->next;
}
return node1;
}
}
return NULL;
}
};287 Find the Duplicate Number
Time: O(n) Space: O(1)
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int fast = nums[nums[0]];
int slow = nums[0];
while(fast != slow){
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while(fast != slow){
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
};146 LRU Cache
Time: O(1) Space: O(capacity)
struct Node{
int k;
int val;
Node* prev;
Node* next;
Node(int key_, int val_): k(key_), val(val_), prev(nullptr), next(nullptr){};
};
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
left = new Node(0, 0);
right = new Node(0, 0);
left->next = right;
right->prev = left;
}
int get(int key) {
if(cache.find(key) != cache.end()){
remove(cache[key]);
insert(cache[key]);
return cache[key]->val;
}
return -1;
}
void put(int key, int value) {
if(cache.find(key)!=cache.end()){
remove(cache[key]);
delete cache[key];
}
cache[key] = new Node(key, value);
insert(cache[key]);
if(cache.size() > cap) {
Node* ln = left->next;
remove(ln);
cache.erase(ln->k);
delete ln;
}
}
private:
int cap;
unordered_map<int, Node*> cache;
Node* left;
Node* right;
void remove(Node* node){
Node* prev = node->prev;
Node* next = node->next;
prev->next = next;
next->prev = prev;
}
void insert(Node* node){
Node* prev = right->prev;
prev->next = node;
node->next = right;
node->prev = prev;
right->prev = node;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/Heap / Priority Queue
703 Kth Largest Element in a Stream
Time: O(n log n + m log k) -> n = length of nums, m = add calls Space: O(n)
class KthLargest {
private:
priority_queue<int, vector<int>, greater<int>> pq;
int k_;
public:
KthLargest(int k, vector<int>& nums) {
k_ = k;
for(int num : nums) {
pq.push(num);
if(pq.size() > k_) {
pq.pop();
}
}
}
int add(int val) {
pq.push(val);
if(pq.size() > k_) {
pq.pop();
}
return pq.top();
}
};
215 Kth Largest Element in an Array
Time: O(n) -> optimized from O(n log k) min heap solution Space: O(1)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for(int num : nums) {
pq.push(num);
if(pq.size() > k) pq.pop();
}
return pq.top();
}
};Backtracking
78 Subsets
Solution 1
Time O(n*2^n) Space O(n)
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> t;
vector<vector<int>> ans;
int n = nums.size();
for(int mask=0; mask< (1<<n); mask++){
t.clear();
for(int i=0; i<n; i++){
if(mask & (1<<i)) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};Solution 1
Time O(n*2^n) Space O(n)
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
void dfs(int cur, vector<int>& nums){
if(cur == nums.size()) {
ans.push_back(t);
return;
}
t.push_back(nums[cur]);
dfs(cur+1,nums);
t.pop_back();
dfs(cur+1,nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(0, nums);
return ans;
}
};90 Subsets II
Time O(n*2^n) Space O(n)
class Solution {
public:
vector<vector<int>> ans;
vector<int> t;
void dfs(int cur, vector<int>& nums){
if(cur == nums.size()){
ans.push_back(t);
return;
}
t.push_back(nums[cur]);
dfs(cur+1, nums);
t.pop_back();
while(cur+1 <nums.size() && nums[cur+1] == nums[cur]) {
cur++;
}
dfs(cur+1, nums);
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(0, nums);
return ans;
}
};39 Combination Sum
Time: O(2^target) Space: O(target)
class Solution {
public:
vector<vector<int>> ans;
vector<int> t;
int sum = 0;
void dfs(int startIdx, vector<int>& candidates, int target){
if(sum == target) {
ans.push_back(t);
return;
}
if( sum > target) {
return;
}
for(int i = startIdx; i < candidates.size(); i++){
t.push_back(candidates[i]);
sum += t.back();
dfs(i, candidates, target);
sum -= t.back();
t.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(0, candidates, target);
return ans;
}
};40 Combination Sum II
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> curr;
vector<vector<int>> result;
dfs(candidates, target, 0, 0, curr, result);
return result;
}
private:
void dfs(vector<int>& candidates, int target, int sum, int start, vector<int>& curr, vector<vector<int>>& result) {
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(curr);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
curr.push_back(candidates[i]);
dfs(candidates, target, sum + candidates[i], i + 1, curr, result);
curr.pop_back();
}
}
};46 Permutations
Time: O(n x n!) Space: O(n!)
class Solution {
public:
vector<vector<int>> ans;
vector<int> t;
void dfs(vector<int>& nums, vector<int>& subset) {
if(subset.size() == 0) {
ans.push_back(t);
return;
}
for(int i=0; i<subset.size(); i++){
int val = subset[i];
t.push_back(val);
subset.erase(subset.begin() + i);
dfs(nums, subset);
t.pop_back();
subset.insert(subset.begin() + i, val);
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, nums);
return ans;
}
};79 Word Search
Time: O(n x 3^l) -> n = # of cells, l = length of word Space: O(l)
class Solution {
public:
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
bool dfs(vector<vector<char>>& board, string word, int total, int x, int y){
if(board[x][y] != word[total]) return false;
if(total == word.size()-1) return true;
char t = board[x][y];
board[x][y]='.'; //block revisit temporarily
//visit neighors
for(int i=0; i<4; i++){
int nx = x+dx[i], ny = y + dy[i];
if(nx<0 || nx>=board.size() || ny <0 || ny>=board[0].size() || board[nx][ny] != word[total+1]) continue;
if(dfs(board, word, total+1, nx, ny)) return true;
}
//reset the map
board[x][y] = t;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
for(int i=0; i<board.size(); i++){
for (int j=0; j<board[0].size(); j++){
if(dfs(board, word, 0, i, j)) return true;
}
}
return false;
}
};Trie
208 Implement Trie (Prefix Tree)
Time: O(n) insert, O(n) search, O(n) startsWith
Space: O(n) insert, O(1) search, O(1) startsWith
class TrieNode{
public:
TrieNode* children[26];
bool isWord;
TrieNode() {
for(int i=0; i<26; i++){
children[i] = NULL;
}
isWord = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
int curr = 0;
for(int i = 0; i< word.size(); i++){
curr = word[i] - 'a';
if(node->children[curr] == NULL){
node->children[curr] = new TrieNode();
}
node = node->children[curr];
}
node->isWord = true;
}
bool search(string word) {
TrieNode* node = root;
int curr = 0;
for(int i = 0; i < word.size(); i++){
curr = word[i] - 'a';
if(node->children[curr] == NULL){
return false;
}
node = node->children[curr];
}
return node->isWord;
}
bool startsWith(string prefix) {
TrieNode* node = root;
int curr = 0;
for(int i=0; i< prefix.size(); i++){
curr = prefix[i] - 'a';
if(node->children[curr] == NULL) {
return false;
}
node = node->children[curr];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/211 Design Add and Search Words Data Structure
Time: O(m x 26^n) -> m = # of words, n = length of words
Space: O(n)
class TrieNode {
public:
TrieNode* children[26];
bool isWord;
TrieNode() {
for(int i=0; i<26; i++){
children[i] = NULL;
}
isWord = false;
}
};
class WordDictionary {
private:
TrieNode* root;
bool searchInNode(string& word, int i, TrieNode* node){
if(node == NULL){
return false;
}
if( i == word.size()){
return node->isWord;
}
if(word[i] != '.') {
return searchInNode(word, i+1, node->children[word[i] - 'a']);
}
for (int j=0; j<26; j++){
if(searchInNode(word, i+1, node->children[j])) {
return true;
}
}
return false;
}
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* node = root;
int curr = 0;
for(int i = 0; i< word.size(); i++){
curr = word[i] - 'a';
if( node->children[curr] == NULL) {
node->children[curr] = new TrieNode();
}
node = node->children[curr];
}
node->isWord = true;
}
bool search(string word) {
TrieNode* node = root;
return searchInNode(word, 0, node);
}
};Graphs
200 Number of Islands
Time: O(m x n) Space: O(m x n)
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int result = 0;
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j] == '1' && !visited[i][j]){
result+=1;
dfs(grid, visited, i, j, m, n);
}
}
}
return result;
}
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y, int m, int n){
if(x < 0 || x >= m || y<0 || y>=n || visited[x][y]) return;
visited[x][y] = true;
if(grid[x][y] == '1') {
grid[x][y] = '0';
dfs(grid, visited, x+1, y, m, n);
dfs(grid, visited, x-1, y, m, n);
dfs(grid, visited, x, y+1, m, n);
dfs(grid, visited, x, y-1, m, n);
}
return;
}
};695 Max Area of Island
Time: O(m x n) Space: O(m x n)
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int area = 0;
int m = grid.size(), n = grid[0].size();
int maxArea = 0;
vector<vector<bool>> visited(m, vector<bool>(n, false));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
area = 0;
if(grid[i][j] == 1 && !visited[i][j]){
dfs(grid, visited, i, j, m, n, area);
maxArea = max(maxArea, area);
}
}
}
return maxArea;
}
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int m, int n, int& area){
if(x<0 || x >=m || y <0 || y>= n || visited[x][y]) return;
visited[x][y] = true;
if(grid[x][y] == 1){
area += 1;
grid[x][y] = 0;
dfs(grid, visited, x+1, y, m, n, area);
dfs(grid, visited, x-1, y, m, n, area);
dfs(grid, visited, x, y+1, m, n, area);
dfs(grid, visited, x, y-1, m, n, area);
}
return;
}
};133 Clone Graph
Time: O(m + n) Space: O(n)
DFS
class Solution {
public:
unordered_map<Node*, Node*> map;
Node* cloneGraph(Node* node) {
if(node == NULL) return NULL;
Node* newNode = new Node(node->val);
map[node] = newNode;
queue<Node*> q;
q.push(node);
while(!q.empty()){
Node* cur = q.front();
q.pop();
for(int i=0; i< cur->neighbors.size(); i++){
Node* neighbor = cur->neighbors[i];
if(map.find(neighbor) == map.end()){
map[neighbor] = new Node(neighbor->val);
q.push(neighbor);
}
map[cur]->neighbors.push_back(map[neighbor]);
}
}
return newNode;
}
};
BFS
994 Rotting Oranges
Time: O(m x n) Space: O(m x n)
class Solution {
public:
vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
for(int i=0; i <m; i++){
for(int j=0; j<n; j++){
if(grid[i][j] == 2){
q.push({i,j});
} else if(grid[i][j] == 1){
fresh++;
}
}
}
q.push({-1, -1});
int result = -1;
while(!q.empty()){
int row = q.front().first;
int col = q.front().second;
q.pop();
if(row==-1){
result++;
if(!q.empty()){
q.push({-1, -1});
}
} else {
for (int i = 0; i < dirs.size(); i++) {
int x = row + dirs[i][0];
int y = col + dirs[i][1];
if (x < 0 || x >= m || y < 0 || y >= n) {
continue;
}
if (grid[x][y] == 1) {
// contaminate
grid[x][y] = 2;
fresh--;
// this orange will now contaminate others
q.push({x, y});
}
}
}
}
if (fresh == 0) {
return result;
}
return -1;
}
};207 Course Schedule
Time: O(V + E) Space: O(V + E)
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edges;
vector<int> deg;
edges.resize(numCourses);
deg.resize(numCourses);
for(auto info : prerequisites){
edges[info[1]].push_back(info[0]);
deg[info[0]] ++;
}
queue<int> q;
for(int i=0; i<numCourses; i++){
if(deg[i] == 0) {
q.push(i);
}
}
int visited = 0;
while(!q.empty()){
int cur = q.front();
q.pop();
visited += 1;
for(auto next : edges[cur]){
deg[next] --;
if(deg[next] ==0) {
q.push(next);
}
}
}
return visited == numCourses;
}
};210 Course Schedule II
Time: O(V + E) Space: O(V + E)
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edges;
vector<int> deg;
vector<int> path;
edges.resize(numCourses);
deg.resize(numCourses);
for(auto info : prerequisites){
edges[info[1]].push_back(info[0]);
deg[info[0]] ++;
}
queue<int> q;
for(int i=0; i<numCourses; i++){
if(deg[i] == 0) {
q.push(i);
}
}
int visited = 0;
while(!q.empty()){
int cur = q.front();
q.pop();
path.push_back(cur);
visited += 1;
if(visited == numCourses){
return path;
}
for(auto next : edges[cur]){
deg[next] --;
if(deg[next] ==0) {
q.push(next);
}
}
}
return {};
}
};Intervals
57 Insert Interval
Time: O(n) Space: O(n)
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n = intervals.size();
vector<vector<int>> result;
int newStart = newInterval[0];
int newEnd = newInterval[1];
int i=0;
while(i<n && intervals[i][1] < newInterval[0]){
result.push_back(intervals[i]);
i++;
}
while(i<n && intervals[i][0] <= newInterval[1]) {
newStart = min(newStart, intervals[i][0]);
newEnd = max(newEnd, intervals[i][1]);
i++;
}
result.push_back({newStart, newEnd});
while(i<n) {
result.push_back(intervals[i]);
i++;
}
return result;
}
};56 Merge Intervals
Time: O(n log n) Space: O(n)
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto&b){
return a[0] < b[0];});
int n = intervals.size();
if(n == 1) return intervals;
vector<vector<int>> results;
int i = 0;
int left = intervals[i][0], right = intervals[i][1];
while(i < n-1){
if(intervals[i+1][0] > right) {
// no overlap
results.push_back({left, right});
left = intervals[i+1][0];
right = intervals[i+1][1];
i++;
} else {
// overlap exists
left = min(left, intervals[i+1][0]);
right = max(right, intervals[i+1][1]);
i++;
}
}
results.push_back({left, right});
return results;
}
};435 Non Overlapping Intervals
Time: O(n log n) Space: O(1)
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() == 0) return 0;
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
return a[1] < b[1];
});
int end = intervals[0][1];
int count = 1;
for(int i=1; i< intervals.size(); i++){
if(intervals[i][0] >= end){
count++;
end = intervals[i][1];
}
}
return intervals.size() - count;
}
};252 Meeting Rooms
Time: O(n log n) Space: O(1)
class Solution {
public:
bool canAttendMeetings(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto&b) {
return a[0] < b[0];
});
for(int i=1; i< intervals.size(); i++){
if(intervals[i][0] < intervals[i-1][1]) {
return false;
}
}
return true;
}
};253 Meeting Rooms II
Time: O(n log n) Space: O(n)
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b){
return a[0] < b[0];
});
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(intervals[0][1]);
for(int i=1; i < intervals.size(); i++){
if(intervals[i][0] >= pq.top()){
pq.pop();
}
pq.push(intervals[i][1]);
}
return pq.size();
}
};Greedy
53 Maximum Subarray
Time: O(n) Space: O(1)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = nums[0];
int sum = 0;
for(int i=0; i<nums.size(); i++){
if(sum <0) sum = 0;
sum = sum += nums[i];
result = max(result, sum);
}
return result;
}
};55 Jump Game
Time: O(n) Space: O(1)
class Solution {
public:
bool canJump(vector<int>& nums) {
int reachable = 0;
for(int i=0; i<nums.size(); i++){
if(reachable < i) return false;
reachable = max(reachable, i+nums[i]);
if(reachable >= nums.size() -1) return true;
}
return true;
}
};45 Jump Game II
Time: O(n) Space: O(1)
class Solution {
public:
int jump(vector<int>& nums) {
int i = 0;
int result = 0;
while(i < nums.size()-1){
if(i+nums[i] >= nums.size()-1){
result++;
break;
}
int bestIdx = i+1;
int bestValue = 0;
for(int j = i+1; j <= i+nums[i]; j++){
if(j + nums[j] > bestValue){
bestIdx = j;
bestValue = j + nums[j];
}
}
i = bestIdx;
result++;
}
return result;
}
};Bit Manipulation
136 Single Number
Time O(n) Space O(1)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int val = nums[0];
for(int i=1; i<nums.size(); i++){
val^=nums[i];
}
return val;
}
};191 Number of 1 Bits
Time O(1) Space O(1)
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while(n){
ans += n%2;
n = n>>1;
}
return ans;
}
};338 Counting Bits
Time O(n) Space O(1)
class Solution {
public:
vector<int> countBits(int n) {
vector<int> dp(n+1, 0);
int offset = 1;
for(int i=1; i<=n; i++){
if(offset * 2 == i) offset = i;
dp[i] = 1 + dp[i - offset];
}
return dp;
}
};190 Reverse Bits
Time O(1) Space O(1)
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
for(int i=0; i<32; i++){
ans <<= 1;
ans |= n&1;
n >>= 1;
}
return ans;
}
};268 Missing Number
Solution 1
Time O(n) Space O(n)
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
unordered_set<int> hash;
for(int i=0; i<n; i++){
hash.insert(nums[i]);
}
int missing = -1;
for(int i=0; i<=n; i++){
if(!hash.count(i)) {
missing = i;
break;
}
}
return missing;
}
};Solution 2
Time O(n) Space O(1)
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int ans = 0;
for(int i=0; i<n; i++){
ans ^= (i+1);
ans ^= nums[i];
}
return ans;
}
};371 Sum of Two Integers
Time O(n) Space O(1)
class Solution {
public:
int getSum(int a, int b) {
while(b != 0){
int carry = a & b;
a = a^b;
b= (unsigned) carry << 1;
}
return a;
}
};1-D Dynamic Programming
198 House Robber
class Solution {
public:
int rob(vector<int>& nums) {
//[rob1, rob2, n, n+1, ...]
int rob1 = 0, rob2 = 0;
int tmp;
//[rob1, rob2, n, n+1, ...]
for(int n: nums){
tmp = max(rob1 + n, rob2);
rob1 = rob2;
rob2 = tmp;
}
return rob2;
}
};Time Complexity o(n), Storage Complexity o(1)
300 Longest Increasing Subsequence
Time: O(n^2) Space: O(n)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n,1);
int result = 1;
for(int i=1; i < n; i++){
for(int j=0; j < i; j++){
if(nums[j] < nums[i]){
dp[i] = max(dp[i], dp[j]+1);
}
}
result = max(result, dp[i]);
}
return result;
}
};647 Palindromic Substrings [todo]
Time: O(n^2) Space: O(1)
class Solution {
public:
int countSubstrings(string s) {
int result = 0;
for(int i=0; i<s.size(); i++){
helper(s, i, i, result);
helper(s, i, i+1, result);
}
return result;
}
void helper(string s, int i, int j, int& result) {
while(i>=0 && j < s.size() && s[i] == s[j]){
result ++ ;
i --;
j ++;
}
}
};2-D Dynamic Programming
121 Best Time to Buy and Sell Stock
Time O(n) Space O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp[n][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1; i<n; i++){
dp[i][0] = max(-prices[i], dp[i-1][0]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
}
return dp[n-1][1];
}
};122 Best Time to Buy and Sell Stock II
Time O(n) Space O(1)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for(int i=1; i<prices.size(); i++){
if(prices[i]-prices[i-1] > 0){
profit += prices[i]-prices[i-1];
}
}
return profit;
}
};123 Best Time to Buy and Sell Stock III
Time O(n) Space O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
// five states: 0) buy nothing, 1) first buy, 2) first sell, 3) second buy, 4) second sell
int n = prices.size();
vector<vector<int>> dp(n+1, vector<int> (5));
dp[0][1] = -prices[0];
dp[0][2] = 0 ;
dp[0][3] = -prices[0];
dp[0][4] = 0;
for( int i=1; i < n; i++) {
dp[i][0] = dp[i-1][0];
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]);
dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i]);
dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]);
}
return max(max(dp[n-1][0], dp[n-1][2]), dp[n-1][4]);
}
};Last updated