Leetcode solutions in C++
Last updated on
54 min read
Table of Contents
- Alternating Groups I
- Asteroid Collision
- Backspace String Compare
- Balanced Binary Tree
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock
- Binary Search
- Binary Tree Level Order Traversal
- Binary Tree Preorder Traversal
- Binary Tree Right Side View
- Binary Level Order Traversal
- Car Pooling
- Check Balanced String
- Climbing Stairs
- Clone Graph
- Coin Change
- Combination Sum II
- Conbination Sum
- Contains Duplicate
- Contiguous Array
- Convert Sorted Array to Binary Search Tree
- Course Schedule II
- Course Schedule
- Day of the year
- Defanding an IP Address
- Design Add and Search Words Data Structure
- Evaluate Reverse Polish Notation
- Fibonacci Number
- Final Array State After K Multiplication Operations I
- Find Center of Star Graph
- Find Median from Data Stream
- Find Players with Zero or One Losses
- Find the Highest Altitude
- Find the Minimum Area to Cover All Ones I
- Find the Winning Player in a Coin Game
- First Bad Version
- Gas Station
- Generate Parentheses
- Group Anagrams
- House Robber
- Implement Queue using Stacks
- Implement Trie (Prefix Tree)
- Insert Delete GetRandom O(1)
- Insert Interval
- Insert into a Binary Search Tree
- Invert Binary Tree
- Is Subsequence
- K Closest Points to Origin
- Kth Largest Element in a Stream
- Kth Largest Element in an Array
- Kth Smallest Element in a BST
- Largest Number
- Linked List Cycle
- Longest Common Prefix
- Longest Consecutive Sequence
- Longest Increasing Subsequence
- Longest Palindrome
- Longest Substring Without Repeating Characters
- Lowest Common Ancestor of a Binary Search Tree
- Lowest Common Ancestor of a Binary Tree
- Majority Element
- Make Array Zero by Subtracting Equal Amounts
- Max Area of Island
- Maximum Bags With Full Capacity of Rocks
- Maximum Depth of Binary Tree
- Maximum Energy Boost From Two Drinks
- Maximum Number of Words you Can Type
- Maximum Product of Two Elements in an Array
- Maximum Prduct Subarray
- Maximum Subarray
- Maximum Units on a Truck
- Merge Intervals
- Merge Two Sorted Lists
- Middle of the Linked List
- Min Cost Climbing Stairs
- Min Stack
- Minimum Average of Smallest and Largest Elements
- Minimum Height Trees
- Minimum Length of String After Operations
- Minimum Number of Operations to Convert Time
- Move Zeroes
- Network delay Time
- Non-overlapping Intervals
- Number of Islands
- Number of Operations to make Network Connected
- Palindromic Linked List
- Pascal’s Triangle
- Permutations
- Product of Array Except Self
- Range Sum Query 2D - Immutable
- Range Sum Query - Immutable
- Ransom Note
- Redundant Connection
- Remove Nth Node From End of List
- Reverse Linked List
- Rotate Array
- Rotate Image
- Rotting Oranges
- Same Tree
- Search in a Binary Search Tree
- Search in a Rotated Sorted Array
- Set Matrix Zeroes
- Snake in Matrix
- Subsets
- Subtree of Another Tree
- Sum of Left Leaves
- Surface Area of 3D Shapes
- Symmetric Tree
- Throne Inheritance
- Time based Key-Value Store
- Top K Frequent Elements
- Trapping Rain Water
- Two Sum
- Unique Paths
- Valid Anagram
- Valid Palindrome
- Valid Parentheses
- Valid Sudoku
- Validate Binary Search Tree
- Vowels Game in a String
Alternating Groups I
Link: https://leetcode.com/problems/alternating-groups-i
// Naive Solution
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors) {
int n = colors.size();
int output = 0;
for(int i = 0; i < n; i++){
if(i == 0){
if(colors[n-1] != colors[i] && colors[i] != colors[i+1]){
output++;
}
}
else if(i == n-1){
if(colors[i-1] != colors[i] && colors[i] != colors[0]){
output++;
}
}
else{
if(colors[i-1] != colors[i] && colors[i] != colors[i+1]){
output++;
}
}
}
return output;
}
};Asteroid Collision
Link: https://leetcode.com/problems/asteroid-collision
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
stack<int> st;
for(int asteroid: asteroids){
bool isAlive = true;
while(!st.empty() && asteroid < 0 && st.top() > 0){
if(st.top() < -asteroid){
st.pop();
continue;
}
else if(st.top() == -asteroid){
st.pop();
}
isAlive = false;
break;
}
if(isAlive){
st.push(asteroid);
}
}
vector<int> output;
while(!st.empty()){
output.push_back(st.top());
st.pop();
}
reverse(output.begin(), output.end());
return output;
}
};Backspace String Compare
Link: https://leetcode.com/problems/backspace-string-compare
//Using Stack
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> stacks;
stack<char> stackt;
for(char c: s){
if(c == '#'){
if(!stacks.empty()){
stacks.pop();
}
}
else{
stacks.push(c);
}
}
for(char c: t){
if(c == '#'){
if(!stackt.empty()){
stackt.pop();
}
}
else{
stackt.push(c);
}
}
while(!stacks.empty() && !stackt.empty()){
if(stacks.top() != stackt.top()){
return false;
}
stacks.pop();
stackt.pop();
}
return stacks.size() == 0 && stackt.size() == 0;
}
};Balanced Binary Tree
Link: https://leetcode.com/problems/balanced-binary-tree/
// Depth First Search
class Solution {
public:
bool isbalanced = true;
bool isBalanced(TreeNode* root) {
if(!root){
return true;
}
depth(root);
return isbalanced;
}
int depth(TreeNode* root){
if(!root){
return 0;
}
int left = depth(root->left);
int right = depth(root->right);
if(abs(left - right) > 1){
isbalanced = false;
return -1;
}
return 1 + max(left, right);
}
};Best Time to Buy and Sell Stock II
Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
// Greedy Approach
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n < 2){
return 0;
}
int maxProfit = 0;
int currMin = prices[0];
for(int i = 1; i < n; i++){
if(prices[i] > currMin){
maxProfit += prices[i] - currMin;
currMin = prices[i];
}
else{
currMin = prices[i];
}
}
return maxProfit;
}
};Best Time to Buy and Sell Stock
Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock
class Solution {
public:
int maxProfit(vector<int>& prices) {
int lowestSoFar = prices[0];
int maxSoFar = 0;
for(int i = 1; i < prices.size(); i++){
lowestSoFar = min(lowestSoFar, prices[i]);
maxSoFar = max(maxSoFar, prices[i] - lowestSoFar);
}
return maxSoFar;
}
};Binary Search
Link: https://leetcode.com/problems/binary-search/
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0;
int high = nums.size()-1;
while(low <= high){
int mid = low + ((high-low)/2);
if(target == nums[mid]){
return mid;
}
else if(target < nums[mid]){
high = mid-1;
}
else {
low = mid+1;
}
}
return -1;
}
};Binary Tree Level Order Traversal
Link: https://leetcode.com/problems/binary-tree-level-order-traversal/
// Breadth First Search Approach
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> output;
if(!root){
return output;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int size = q.size();
vector<int> level;
while(size > 0){
TreeNode* temp = q.front();
q.pop();
if(temp->left){
q.push(temp->left);
}
if(temp->right){
q.push(temp->right);
}
level.push_back(temp->val);
size--;
}
output.push_back(level);
}
return output;
}
};
// Depth First Search
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> output;
if(!root){
return output;
}
levelOrder(output, root, 0);
return output;
}
void levelOrder(vector<vector<int>>& output, TreeNode* root, int height){
if(!root){
return;
}
if(height == output.size()){
output.push_back(vector<int>{root->val});
}
else{
output[height].push_back(root->val);
}
levelOrder(output, root->left, height+1);
levelOrder(output, root->right, height+1);
}
};Binary Tree Preorder Traversal
Link: https://leetcode.com/problems/binary-tree-preorder-traversal/
class Solution {
public:
vector<int> output;
vector<int> preorderTraversal(TreeNode* root) {
preorder(root);
return output;
}
void preorder(TreeNode* root){
if(!root){
return;
}
output.push_back(root->val);
preorder(root->left);
preorder(root->right);
}
};Binary Tree Right Side View
Link: https://leetcode.com/problems/binary-tree-right-side-view/
//Breadth First Search
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> output;
if(!root){
return output;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int count = q.size();
while(count > 0){
TreeNode* temp = q.front();
q.pop();
if(temp->left){
q.push(temp->left);
}
if(temp->right){
q.push(temp->right);
}
if(count == 1){
output.push_back(temp->val);
}
count--;
}
}
return output;
}
};Binary Level Order Traversal
Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
// Using Breadth First Search
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> output;
if(!root){
return output;
}
queue<TreeNode*> q;
q.push(root);
bool flag = true;
while(!q.empty()){
int count = q.size();
vector<int> level;
for(int i = 0; i < count; i++){
TreeNode* temp = q.front();
q.pop();
level.push_back(temp->val);
if(temp->left){
q.push(temp->left);
}
if(temp->right){
q.push(temp->right);
}
}
flag = !flag;
if(flag){
reverse(level.begin(), level.end());
}
output.push_back(level);
}
return output;
}
};Car Pooling
Link: https://leetcode.com/problems/car-pooling
// Naive Approach
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
int maxDistance = 0;
vector<int> cap(1000+1);
for(vector<int> trip: trips){
int numPassengers = trip[0];
int from = trip[1];
int to = trip[2];
for(int i = from; i < to; i++){
cap[i] += numPassengers;
if(cap[i] > capacity){
return false;
}
}
}
return true;
}
};
// Sweep Line Algorithm
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> cap(1001);
for(vector<int> trip: trips){
int numPassengers = trip[0];
int from = trip[1];
int to = trip[2];
cap[from] += numPassengers;
cap[to] -= numPassengers;
}
for(int item: cap){
capacity -= item;
if(capacity < 0){
return false;
}
}
return true;
}
};
Check Balanced String
Link: https://leetcode.com/problems/check-balanced-string
class Solution {
public:
bool isBalanced(string num) {
int oddSum = 0;
int evenSum = 0;
for(int i = 0; i < num.size(); i++){
if(i%2 == 0){
evenSum += int(num[i] - '0');
}
else{
oddSum += int(num[i] - '0');
}
}
return oddSum == evenSum;
}
};
class Solution {
public:
bool check(vector<int>& nums) {
int count = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
if(nums[i] > nums[(i+1)%n]){
count++;
}
if(count > 1){
return false;
}
}
return true;
}
};
Climbing Stairs
Link: https://leetcode.com/problems/climbing-stairs
// Recursion using Memoization
class Solution {
public:
int climbStairs(int n, unordered_map<int,int>& memo) {
if(n == 0 || n == 1){
return 1;
}
if(memo.find(n) == memo.end()){
memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo);
}
return memo[n];
}
int climbStairs(int n){
unordered_map<int, int> memo;
return climbStairs(n, memo);
}
};Clone Graph
Link: https://leetcode.com/problems/clone-graph/
// Using Depth First Search
class Solution {
public:
Node* cloneGraph(Node* node) {
if(!node){
return NULL;
}
unordered_map<Node*, Node*> map;
dfs(map, node);
return map[node];
}
void dfs(unordered_map<Node*, Node*>& map, Node* node){
Node* copyNode = new Node(node->val);
map[node] = copyNode;
for(Node* n: node->neighbors){
if(map.find(n) == map.end()){
dfs(map, n);
}
copyNode->neighbors.push_back(map[n]);
}
}
};Coin Change
Link: https://leetcode.com/problems/coin-change
// DP Top Down Approach using Memoization (Uses unordered_map) (Time Limit Exceeded)
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
unordered_map<string, int> map;
int output = coinChange(coins, 0, amount, map);
return output == INT_MAX - 1 ? -1 : output;
}
int coinChange(vector<int>& coins, int curr, int amount, unordered_map<string, int>& map){
if(curr >= coins.size() || amount < 0){
return INT_MAX - 1;
}
if(amount == 0){
return 0;
}
string key = to_string(curr) + '$' + to_string(amount);
if(map.find(key) != map.end()){
return map[key];
}
int output = -1;
if(coins[curr] > amount){
int dontTakeCoin = coinChange(coins, curr+1, amount, map);
output = dontTakeCoin;
}
else{
int takeCoin = 1 + coinChange(coins, curr, amount - coins[curr], map);
int dontTakeCoin = coinChange(coins, curr+1, amount, map);
output = min(takeCoin, dontTakeCoin);
}
map[key] = output;
return output;
}
};
// DP Top Down Approach using Memoization (Uses static array)
class Solution {
public:
int dp[13][10001];
int coinChange(vector<int>& coins, int amount) {
memset(dp, -1, sizeof(dp));
int output = coinChange(coins, 0, amount);
return output == INT_MAX - 1 ? -1 : output;
}
int coinChange(vector<int>& coins, int curr, int amount){
if(curr >= coins.size() || amount < 0){
return INT_MAX - 1;
}
if(amount == 0){
return 0;
}
if(dp[curr][amount] != -1){
return dp[curr][amount];
}
int output = -1;
if(coins[curr] > amount){
int dontTakeCoin = coinChange(coins, curr+1, amount);
output = dontTakeCoin;
}
else{
int takeCoin = 1 + coinChange(coins, curr, amount - coins[curr]);
int dontTakeCoin = coinChange(coins, curr+1, amount);
output = min(takeCoin, dontTakeCoin);
}
dp[curr][amount] = output;
return dp[curr][amount];
}
};Combination Sum II
Link: https://leetcode.com/problems/combination-sum-ii/
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end(), [](int a, int b){
return a < b;
});
vector<vector<int>> output;
vector<int> tempList;
backtrack(output, tempList, candidates, 0, target);
return output;
}
void backtrack(vector<vector<int>> &output, vector<int> &tempList, vector<int> &candidates, int i, int target){
if(target == 0){
output.push_back(tempList);
return;
}
if (target < 0){
return;
}
for(int a = i; a < candidates.size(); a++){
if(i != a && candidates[a] == candidates[a-1]){
continue;
}
tempList.push_back(candidates[a]);
backtrack(output, tempList, candidates, a+1, target - candidates[a]);
tempList.pop_back();
}
}
};Conbination Sum
Link: https://leetcode.com/problems/combination-sum/
// Backtracking Approach
class Solution {
private:
void combinationSum(vector<int>& candidates, int target, int index, vector<vector<int>>& output, vector<int>& temp){
if(target < 0){
return;
}
if(target == 0){
output.push_back(temp);
return;
}
for(int i = index; i < candidates.size(); i++){
temp.push_back(candidates[i]);
combinationSum(candidates, target - candidates[i], i, output, temp);
temp.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> output;
vector<int> temp;
combinationSum(candidates, target, 0, output, temp);
return output;
}
};Contains Duplicate
Link: https://leetcode.com/problems/contains-duplicate/
// Using Set
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> duplicate;
for(int val : nums){
if(duplicate.find(val) != duplicate.end()){
return true;
}
else{
duplicate.insert(val);
}
}
return false;
}
};
// Using Sorting
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
int temp = nums[0];
for(int i = 1; i < nums.size(); i++){
if(temp == nums[i]){
return true;
}
else{
temp = nums[i];
}
}
return false;
}
};Contiguous Array
Link: https://leetcode.com/problems/contiguous-array/
// Prefix sum + Hashmap
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int n = nums.size();
int output = 0;
int sum = 0;
unordered_map<int,int> map;
for(int i = 0; i < n; i++){
if(nums[i] == 0){
sum--;
}
else{
sum++;
}
if(sum == 0){
output = i + 1;
}
if(map.find(sum) == map.end()){
map[sum] = i;
}
else{
output = max(output, i - map[sum]);
}
}
return output;
}
};Convert Sorted Array to Binary Search Tree
Link: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree
// Recursive Solution
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return createBST(nums, 0, nums.size()-1);
}
TreeNode* createBST(vector<int>& nums, int start, int end){
int mid = (start + end)/ 2;
TreeNode* midNode = new TreeNode(nums[mid]);
if(start != end){
if(start < mid){
midNode->left = createBST(nums, start, mid-1);
}
if(mid < end){
midNode->right = createBST(nums, mid+1, end);
}
}
return midNode;
}
};
class Solution {
public:
int numberOfSubstrings(string s, int k) {
int output = 0;
int left = 0;
unordered_map<char, int> map;
for(char c: s){
map[c]++;
while(map[c] == k){
map[s[left]]--;
left++;
}
output += left;
}
return output;
}
};Course Schedule II
Link: https://leetcode.com/problems/course-schedule-ii
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> indegree(numCourses, 0);
unordered_map<int, vector<int>> map;
for(vector<int> preq: prerequisites){
int start = preq[1];
int end = preq[0];
indegree[end]++;
map[start].push_back(end);
}
queue<int> bfs;
vector<int> output;
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0){
bfs.push(i);
output.push_back(i);
}
}
while(bfs.size() > 0){
int curr = bfs.front();
bfs.pop();
for(int item: map[curr]){
indegree[item]--;
if(indegree[item] == 0){
bfs.push(item);
output.push_back(item);
}
}
}
return output.size() == numCourses ? output : vector<int>();
}
};Course Schedule
Link: https://leetcode.com/problems/course-schedule/
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> indegree(numCourses);
unordered_map<int, vector<int>> adj;
// Create adjacency list
// Also update indegree array to keep a count of number of edges coming towards an node
for(auto preq: prerequisites){
int a = preq[0];
int b = preq[1];
indegree[a]++;
adj[b].push_back(a);
}
queue<int> q;
// Put all the nodes with in degree 0 to the queue, since those courses are not dependent on any other
for(int i = 0; i < indegree.size(); i++){
if(indegree[i] == 0){
q.push(i);
}
}
int visited = 0;
while(!q.empty()){
int course = q.front();
q.pop();
visited++;
// As you loop though the neighbours of a node decrease it's in degrees. If a indegree becomes 0 then push it to the queue
for(int edge: adj[course]){
indegree[edge]--;
if(indegree[edge] == 0){
q.push(edge);
}
}
}
// If all indegrees are 0 then all courses can be taken else it means there are circular dependencies
return visited == numCourses;
}
};Day of the year
Link: https://leetcode.com/problems/day-of-the-year
class Solution {
private:
int isLeapYear(int year){
if(year % 400 == 0){
return true;
}
else if(year % 100 == 0){
return false;
}
else if(year % 4 == 0){
return true;
}
else{
return false;
}
}
public:
int dayOfYear(string date) {
int yy = stoi(date.substr(0, 4));
int mm = stoi(date.substr(5, 2));
int dd = stoi(date.substr(8, 2));
int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int output = 0;
for(int i = 0; i < mm; i++){
if(i == mm-1){// if it is the current month
output += dd;
break;
}
if(i == 1){
output += isLeapYear(yy) ? 29 : 28;
}
else{
output += days[i];
}
}
return output;
}
};Defanding an IP Address
Link: https://leetcode.com/problems/defanging-an-ip-address/description/
// String replacement
class Solution {
public:
string defangIPaddr(string address) {
string output;
for(int i = 0; i < address.size(); i++){
if(address[i] == '.'){
output += "[.]";
}
else{
output += address[i];
}
}
return output;
}
};
Design Add and Search Words Data Structure
Link: https://leetcode.com/problems/design-add-and-search-words-data-structure/
struct TrieNode{
TrieNode* children[26];
bool isWord;
TrieNode(){
isWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class WordDictionary {
private:
TrieNode* root;
bool searchHelper(TrieNode* node, string word, int i){
if(i == word.size()){
return node->isWord;
}
char c = word[i];
if(c == '.'){
for(int j = 0; j < 26; j++){
if(node->children[j] != NULL && searchHelper(node->children[j], word, i+1)){
return true;
}
}
return false;
}
else{
if(node->children[c-'a'] != nullptr){
return searchHelper(node->children[c-'a'], word, i+1);
}
else{
return false;
}
}
}
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* tempRoot = root;
for(char c: word){
if(tempRoot->children[c-'a'] == NULL){
tempRoot->children[c-'a'] = new TrieNode();
}
tempRoot = tempRoot->children[c-'a'];
}
tempRoot->isWord = true;
}
bool search(string word) {
TrieNode* tempRoot = root;
return searchHelper(tempRoot, word, 0);
}
};Evaluate Reverse Polish Notation
Link: https://leetcode.com/problems/evaluate-reverse-polish-notation
Using stack
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(string token: tokens){
if(token == "+" || token == "-" || token == "*" || token == "/"){
int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();
int eval;
if(token == "+"){
eval = num1 + num2;
}
else if(token == "-"){
eval = num2 - num1;
}
else if(token == "*"){
eval = num1 * num2;
}
else if(token == "/"){
eval = num2 / num1;
}
st.push(eval);
}
else{
st.push(stoi(token));
}
}
return st.top();
}
};Fibonacci Number
Link: https://leetcode.com/problems/fibonacci-number
class Solution {
public:
int fib2(int n, vector<int>& memo){
if(memo[n] != -1){
return memo[n];
}
else{
return fib2(n-1, memo) + fib2(n-2, memo);
}
}
int fib(int n) {
if(n < 2){
return n;
}
vector<int> memo(n+1, -1);
memo[0] = 0;
memo[1] = 1;
return fib2(n, memo);
}
};Final Array State After K Multiplication Operations I
Link: https://leetcode.com/problems/final-array-state-after-k-multiplication-operations-i/
class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
int n = nums.size();
while(k > 0){
int smallestIndex = 0;
int smallestNum = nums[0];
for(int i = 1; i < n; i++){
if(nums[i] < smallestNum){
smallestNum = nums[i];
smallestIndex = i;
}
}
nums[smallestIndex] *= multiplier;
k--;
}
return nums;
}
};Find Center of Star Graph
Link: https://leetcode.com/problems/find-center-of-star-graph/
class Solution {
public:
int findCenter(vector<vector<int>>& edges) {
unordered_set<int> set;
int u1 = edges[0][0];
int v1 = edges[0][1];
int u2 = edges[1][0];
int v2 = edges[1][1];
set.insert(u1);
set.insert(v1);
if(set.find(u2) != set.end()){
return u2;
}
if(set.find(v2) != set.end()){
return v2;
}
return 0;
}
};Find Median from Data Stream
Link: https://leetcode.com/problems/find-median-from-data-stream
// Using Two Priority Queues
class MedianFinder {
private:
priority_queue<int> leftPQ; // Max Heap
priority_queue<int, vector<int>, greater<int>> rightPQ; // Min Heap
public:
MedianFinder() {}
void addNum(int num) {
// When a new number needs to be pushed, push it to left heap and then pop the top number from left and push it to right
// If right heap is greater then pop top number from right and put it to left
// Basically left heap will always be equal to right heap or left heap will be one greater than the right heap
leftPQ.push(num);
rightPQ.push(leftPQ.top());
leftPQ.pop();
if(rightPQ.size() > leftPQ.size()){
leftPQ.push(rightPQ.top());
rightPQ.pop();
}
}
double findMedian() {
if(leftPQ.size() > rightPQ.size()){
return leftPQ.top();
}
else{
return ((leftPQ.top() + rightPQ.top())/ 2.0);
}
}
};
class Solution {
public:
int maxFreqSum(string s) {
unordered_map<char, int> vowelFreq;
unordered_map<char, int> consonantFreq;
for(char c : s) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
vowelFreq[c]++;
} else {
consonantFreq[c]++;
}
}
int output = 0;
int maxSoFar = 0;
for (auto item : vowelFreq) {
maxSoFar = max(maxSoFar, item.second);
}
output += maxSoFar;
maxSoFar = 0;
for (auto item : consonantFreq) {
maxSoFar = max(maxSoFar, item.second);
}
return output + maxSoFar;
}
};Find Players with Zero or One Losses
Link: https://leetcode.com/problems/find-players-with-zero-or-one-losses
class Solution {
public:
vector<vector<int>> findWinners(vector<vector<int>>& matches) {
map<int, int> map;
for(int i = 0; i < matches.size(); i++){
int winner = matches[i][0];
int loser = matches[i][1];
map.insert({winner, 0});
map.insert({loser, 0});
}
for(int i = 0; i < matches.size(); i++){
int loser = matches[i][1];
map[loser] += 1;
}
vector<int> answer0;
vector<int> answer1;
for(auto item: map){
if(item.second == 0){
answer0.push_back(item.first);
}
else if(item.second == 1){
answer1.push_back(item.first);
}
}
return vector<vector<int>> {answer0, answer1};
}
};Find the Highest Altitude
Link: https://leetcode.com/problems/find-the-highest-altitude
class Solution {
public:
int largestAltitude(vector<int>& gain) {
int output = 0;
int curr = 0;
for(int item : gain){
curr += item;
output = max(output, curr);
}
return output;
}
};Find the Minimum Area to Cover All Ones I
Link: https://leetcode.com/problems/find-the-minimum-area-to-cover-all-ones-i
class Solution {
public:
int minimumArea(vector<vector<int>>& grid) {
int rowCount = grid.size();
int colCount = grid[0].size();
int left = INT_MAX;
int right = INT_MIN;
int top = INT_MAX;
int down = INT_MIN;
for(int i = 0; i < rowCount; i++){
for(int j = 0; j < colCount; j++){
if(grid[i][j] == 1){
left = min(left, i);
right = max(right, i);
top = min(top, j);
down = max(down, j);
}
}
}
return (right - left + 1) * (down - top + 1);
}
};
class Solution {
public:
vector<string> stringSequence(string target) {
vector<string> output;
if(target == ""){
return output;
}
int N = target.size();
for(int i = 0; i < N; i++){
string startString;
if(i == 0){
startString = "";
}
else{
startString = output[output.size()-1];
}
int currentChar = int('a');
int requiredChar = int(target[i]);
while(currentChar <= requiredChar){
output.push_back(startString + char(currentChar));
currentChar++;
}
}
return output;
}
};Find the Winning Player in a Coin Game
Link: https://leetcode.com/problems/find-the-winning-player-in-coin-game
// Recursive Solution
class Solution {
public:
string losingPlayer(int x, int y) {
bool isAliceTurn = true;
while(x >= 1 && y >= 4){
x -= 1;
y -= 4;
isAliceTurn = !isAliceTurn;
}
return isAliceTurn ? "Bob" : "Alice";
}
};First Bad Version
Link: https://leetcode.com/problems/first-bad-version
class Solution {
public:
int firstBadVersion(int n) {
int low = 0;
int high = n;
int output = n;
while(low <= high){
int mid = low + (high - low) / 2;
if(isBadVersion(mid)){
output = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
return output;
}
};Gas Station
Link: https://leetcode.com/problems/gas-station/
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int totalRemGas = 0;
int tank = 0;
int output = 0;
for(int i = 0; i < n; i++){
totalRemGas += gas[i] - cost[i];
tank += gas[i] - cost[i];
if(tank < 0){
tank = 0;
output = i+1;
}
}
return totalRemGas < 0 ? -1 : output;
}
};Generate Parentheses
Link: https://leetcode.com/problems/generate-parentheses
// Using Backtracking
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> output;
backtrack(output, "", n, 0, 0);
return output;
}
void backtrack(vector<string> &output, string tempString, int n, int openCount, int closeCount){
if(tempString.size() == 2*n){
output.push_back(tempString);
return;
}
if(openCount < n){
backtrack(output, tempString+'(', n, openCount+1, closeCount);
}
if(closeCount < openCount){
backtrack(output, tempString+')', n, openCount, closeCount+1);
}
}
};Group Anagrams
Link: https://leetcode.com/problems/group-anagrams
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for(string str: strs){
string copy = str;
sort(copy.begin(), copy.end());
if(map.find(copy) == map.end()){
map[copy] = vector<string>();
}
map[copy].push_back(str);
}
vector<vector<string>> output;
for(auto item: map){
output.push_back(item.second);
}
return output;
}
};House Robber
Link: https://leetcode.com/problems/house-robber/
// Top Down Approach
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size(), -1);
return rob(nums, dp, nums.size() - 1);
}
int rob(vector<int>& nums, vector<int>& dp, int i){
if(i < 0){
return 0;
}
if(dp[i] >= 0){
return dp[i];
}
dp[i] = max(rob(nums, dp, i-2) + nums[i], rob(nums, dp, i-1));
return dp[i];
}
};Implement Queue using Stacks
Link: https://leetcode.com/problems/implement-queue-using-stacks/
class MyQueue {
private:
stack<int> st1;
stack<int> st2;
public:
MyQueue() {
}
void push(int x) {
st1.push(x);
}
int pop() {
if(st2.empty()){
while(!st1.empty()){
int top = st1.top();
st1.pop();
st2.push(top);
}
}
int top = st2.top();
st2.pop();
return top;
}
int peek() {
if(st2.empty()){
while(!st1.empty()){
int top = st1.top();
st1.pop();
st2.push(top);
}
}
return st2.top();
}
bool empty() {
return st1.size() + st2.size() == 0;
}
};Implement Trie (Prefix Tree)
Link: https://leetcode.com/problems/implement-trie-prefix-tree
class Node{
public:
bool isEnd;
Node* values[26] = {NULL};
Node(){
isEnd = false;
}
};
class Trie {
private:
Node* root;
public:
Trie() {
root = new Node();
}
void insert(string word) {
Node* tempNode = root;
for(char c: word){
if(tempNode->values[c - 'a'] == NULL){
tempNode->values[c - 'a'] = new Node();;
}
tempNode = tempNode->values[c - 'a'];
}
tempNode->isEnd = true;
}
bool search(string word) {
Node* tempNode = root;
for(char c: word){
if(tempNode->values[c - 'a'] == NULL){
return false;
}
tempNode = tempNode->values[c - 'a'];
}
return tempNode->isEnd;
}
bool startsWith(string prefix) {
Node* tempNode = root;
for(char c: prefix){
if(tempNode->values[c - 'a'] == NULL){
return false;
}
tempNode = tempNode->values[c - 'a'];
}
return true;
}
};
Insert Delete GetRandom O(1)
Link: https://leetcode.com/problems/insert-delete-getrandom-o1/
class RandomizedSet {
private:
unordered_map<int,int> map;
vector<int> arr;
public:
RandomizedSet() {
}
bool insert(int val) {
if(map.find(val) == map.end()){
int index = arr.size();
arr.push_back(val);
map[val] = index;
return true;
}
else{
return false;
}
}
bool remove(int val) {
if(map.find(val) == map.end()){
return false;
}
else{
int index = map[val];
map.erase(val);
// if not last item
if(index != arr.size() - 1){
int lastitem = arr[arr.size()-1];
arr[index] = lastitem;
map[lastitem] = index;
}
arr.pop_back();
return true;
}
}
int getRandom() {
int random = rand() % arr.size();
return arr[random];
}
};Insert Interval
Link: https://leetcode.com/problems/insert-interval
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
intervals.push_back(vector<int>{newInterval[0], newInterval[1]});
if(intervals.size() < 2){
return intervals;
}
sort(intervals.begin(), intervals.end(), [](vector<int> vect1, vector<int> vect2){
return vect1[0] < vect2[0];
});
int start = intervals[0][0];
int end = intervals[0][1];
vector<vector<int>> output;
for(int i = 1; i < intervals.size(); i++){
if(end >= intervals[i][0]){
end = max(end, intervals[i][1]);
}
else{
output.push_back(vector<int>{start, end});
start = intervals[i][0];
end = intervals[i][1];
}
}
output.push_back(vector<int>{start, end});
return output;
}
};
Insert into a Binary Search Tree
Link: https://leetcode.com/problems/insert-into-a-binary-search-tree
// Iterative Approach
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode* newNode = new TreeNode(val);
if(root == NULL){
return newNode;
}
TreeNode* current = root;
TreeNode* parent = NULL;
while(current != NULL){
parent = current;
if(val < current->val){
current = current->left;
}
else{
current = current->right;
}
}
if(val < parent->val){
parent->left = newNode;
}
else{
parent->right = newNode;
}
return root;
}
};
// Recursive Approach
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root == NULL){
return new TreeNode(val);
}
else if(val < root->val){
root->left = insertIntoBST(root->left, val);
}
else{
root->right = insertIntoBST(root->right, val);
}
return root;
}
};Invert Binary Tree
Link: https://leetcode.com/problems/invert-binary-tree/
// Recursive Solution
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL){
return NULL;
}
TreeNode* temp = invertTree(root->left);
root->left = invertTree(root->right);
root->right = temp;
return root;
}
};Is Subsequence
Link: https://leetcode.com/problems/is-subsequence
class Solution {
public:
bool isSubsequence(string s, string t) {
int sIndex = 0;
int tIndex = 0;
while(sIndex < s.size() && tIndex < t.size()){
if(s[sIndex] == t[tIndex]){
sIndex++;
tIndex++;
}
else{
tIndex++;
}
}
return sIndex == s.size();
}
};K Closest Points to Origin
Link: https://leetcode.com/problems/k-closest-points-to-origin
// Using Priority Queue
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
for(auto point: points){
int x = point[0];
int y = point[1];
int distance = pow(x, 2) + pow(y, 2);
pq.push({distance, {x, y}});
}
vector<vector<int>> output;
while(k > 0){
auto item = pq.top();
pq.pop();
int x = item.second.first;
int y = item.second.second;
output.push_back(vector<int>{x, y});
k--;
}
return output;
}
};Kth Largest Element in a Stream
Link: https://leetcode.com/problems/kth-largest-element-in-a-stream/
class KthLargest {
private:
priority_queue<int, vector<int>, greater<int>> pq;
int size;
public:
KthLargest(int k, vector<int>& nums) {
size = k;
for(int num: nums){
pq.push(num);
if(pq.size() > k){
pq.pop();
}
}
}
int add(int val) {
pq.push(val);
if(pq.size() > size){
pq.pop();
}
return pq.top();
}
};Kth Largest Element in an Array
Link: https://leetcode.com/problems/kth-largest-element-in-an-array/
// Using sorting
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), [](int i, int j){
return i > j;
});
return nums[k-1];
}
};
// Using Priority Queue
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq;
for(int num: nums){
pq.push(num);
}
int output;
while(k > 0){
output = pq.top();
pq.pop();
k--;
}
return output;
}
};Kth Smallest Element in a BST
Link: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
// Recursive Approach
class Solution {
int count = 0;
int output = 0;
public:
int kthSmallest(TreeNode* root, int k) {
count = k;
smallest(root);
return output;
}
void smallest(TreeNode* root){
if(root->left != NULL){
smallest(root->left);
}
count--;
if(count == 0){
output = root->val;
}
if(root->right != NULL){
smallest(root->right);
}
}
};Largest Number
Link: https://leetcode.com/problems/largest-number/
class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b){
string sa = to_string(a);
string sb = to_string(b);
return sa + sb > sb + sa;
});
string output = "";
for(int num: nums){
output += to_string(num);
}
while(output[0] == '0' && output.size() > 1){
output.erase(0,1);
}
return output;
}
};Linked List Cycle
Link: https://leetcode.com/problems/linked-list-cycle/
// Tortoise and Hare Algorithm
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL){
return false;
}
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
return true;
}
}
return false;
}
};Longest Common Prefix
Link: https://leetcode.com/problems/longest-common-prefix
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size();
if(n == 1){
return strs[0];
}
string output = "";
string curr = strs[0];
for(int i = 0; i < curr.size(); i++){
bool flag = true;
for(int j = 1; j < n; j++){
if(i < strs[j].size() && strs[j][i] == curr[i]){
continue;
}
else{
flag = false;
break;
}
}
if(flag){
output += curr[i];
}
else{
break;
}
}
return output;
}
};Longest Consecutive Sequence
Link: https://leetcode.com/problems/longest-consecutive-sequence
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> s(nums.begin(), nums.end());
int output = 0;
for(int start: s){
if(s.find(start-1) == s.end()){
int end = start + 1;
while(s.find(end) != s.end()){
end++;
}
output = max(output, end - start);
}
}
return output;
}
};Longest Increasing Subsequence
Link: https://leetcode.com/problems/longest-increasing-subsequence
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = max(dp[i], 1 + dp[j]);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};Longest Palindrome
Link: https://leetcode.com/problems/longest-palindrome/
// Using Hashmap
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> mapper;
for(char c: s){
if(mapper.find(c) != mapper.end()){
mapper[c]++;
}
else{
mapper[c] = 1;
}
}
bool oddFlag = false;
int result = 0;
for(auto item: mapper){
if(item.second % 2 == 0){
result += item.second;
}
else{
result += (item.second / 2) * 2;
oddFlag = true;
}
}
if(oddFlag){
result++;
}
return result;
}
};Longest Substring Without Repeating Characters
Link: https://leetcode.com/problems/longest-substring-without-repeating-characters
// Using set
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int N = s.size();
if(N < 2){
return N;
}
int maxSoFar = 0;
int i = 0;
int j = 0;
unordered_set<char> set;
while(i < N && j < N){
if(set.find(s[j]) != set.end()){
set.erase(s[i]);
i++;
}
else {
set.insert(s[j]);
maxSoFar = max(maxSoFar, j - i + 1);
j++;
}
}
return maxSoFar;
}
};Lowest Common Ancestor of a Binary Search Tree
Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root != NULL){
if(p->val < root->val && q->val < root->val){
root = root->left;
}
else if(p->val > root->val && q->val > root->val){
root = root->right;
}
else{
break;
}
}
return root;
}
};Lowest Common Ancestor of a Binary Tree
Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> pTraversal;
stack<TreeNode*> qTraversal;
traversalPath(root, p->val, pTraversal);
traversalPath(root, q->val, qTraversal);
TreeNode* output = root;
int psize = pTraversal.size();
int qsize = qTraversal.size();
int i = min(psize, qsize);
while(i > 0){
if(pTraversal.top() == qTraversal.top()){
output = pTraversal.top();
pTraversal.pop();
qTraversal.pop();
}
else{
break;
}
i--;
}
return output;
}
bool traversalPath(TreeNode* curr, int target, stack<TreeNode*>& path){
if(!curr){
return false;
}
if(curr->val == target){
return true;
}
if(traversalPath(curr->left, target, path)){
path.push(curr->left);
return true;
}
if(traversalPath(curr->right, target, path)){
path.push(curr->right);
return true;
}
return false;
}
};Majority Element
Link: https://leetcode.com/problems/majority-element
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size() <= 2){
return nums[0];
}
sort(nums.begin(), nums.end());
int result = nums[0];
int count = 1;
for(int i = 1; i < nums.size(); i++){
if(nums[i] == result){
count++;
}
else{
if(count > nums.size()/2){
break;
}
result = nums[i];
count = 1;
}
}
return result;
}
};Make Array Zero by Subtracting Equal Amounts
Link: https://leetcode.com/problems/make-array-zero-by-subtracting-equal-amounts
class Solution {
public:
int minimumOperations(vector<int>& nums) {
int count = 0;
unordered_set<int> set;
for(int i = 0; i < nums.size(); i++){
if(nums[i] != 0){
set.insert(nums[i]);
}
}
return size(set);
}
};Max Area of Island
Link: https://leetcode.com/problems/max-area-of-island/
// Using Depth First search
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int maxSoFar = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
int count = maxArea(grid, i, j, m, n);
cout << count << endl;
maxSoFar = max(maxSoFar, count);
}
}
}
return maxSoFar;
}
int maxArea(vector<vector<int>>& grid, int i, int j, int m, int n){
if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0){
return 0;
}
int count = 1;
grid[i][j] = 0;
count += maxArea(grid, i-1, j, m, n);
count += maxArea(grid, i+1, j, m, n);
count += maxArea(grid, i, j-1, m, n);
count += maxArea(grid, i, j+1, m, n);
return count;
}
};
class Solution {
public:
long long maximumTotalSum(vector<int>& maximumHeight) {
sort(maximumHeight.begin(), maximumHeight.end(), [](int val1, int val2){
return val1 > val2;
});
int currHeight = maximumHeight[0];
long output = 0;
for(int height: maximumHeight){
if(currHeight <= 0){
return -1;
}
currHeight = min(currHeight, height);
output += currHeight;
currHeight--;
}
return output;
}
};
// Convert to string and replace
class Solution {
public:
int maximum69Number (int num) {
string numString = to_string(num);
for(int i = 0; i < numString.size(); i++){
if(numString[i] == '6'){
numString[i] = '9';
break;
}
}
return stoi(numString);
}
};Maximum Bags With Full Capacity of Rocks
Link: https://leetcode.com/problems/maximum-bags-with-full-capacity-of-rocks/
class Solution {
public:
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
int count = 0;
int n = size(capacity);
vector<int> diff(n);
for(int i = 0; i < size(capacity); i++){
diff[i] = capacity[i] - rocks[i];
}
sort(diff.begin(), diff.end());
for(int i = 0; i < n; i++){
if(additionalRocks >= diff[i]){
count++;
additionalRocks -= diff[i];
}
else{
break;
}
}
return count;
}
};Maximum Depth of Binary Tree
Link: https://leetcode.com/problems/maximum-depth-of-binary-tree/
// Recursive appraoch
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root){
return 0;
}
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};
// Breadth First Search
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root){
return 0;
}
queue<TreeNode*> bfsQueue;
bfsQueue.push(root);
int depth = 0;
while(!bfsQueue.empty()){
int count = bfsQueue.size();
depth++;
while(count > 0){
TreeNode* temp = bfsQueue.front();
bfsQueue.pop();
if(temp->left){
bfsQueue.push(temp->left);
}
if(temp->right){
bfsQueue.push(temp->right);
}
count--;
}
}
return depth;
}
};Maximum Energy Boost From Two Drinks
Link: https://leetcode.com/problems/maximum-energy-boost-from-two-drinks
Using Dynamic Programming
class Solution {
public:
long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
long n = energyDrinkA.size();
vector<long long> dpA(n, 0);
vector<long long> dpB(n, 0);
dpA[0] = energyDrinkA[0];
dpB[0] = energyDrinkB[0];
for(long i = 1; i < n; i++){
dpA[i] = max(dpA[i-1], i > 1 ? dpB[i-2] : 0) + energyDrinkA[i];
dpB[i] = max(dpB[i-1], i > 1 ? dpA[i-2] : 0) + energyDrinkB[i];
}
return max(dpA[n-1], dpB[n-1]);
}
};Maximum Number of Words you Can Type
Link: https://leetcode.com/problems/maximum-number-of-words-you-can-type
class Solution {
private:
vector<string> split(string input, char c){
vector<string> output;
int j = 0;
for(int i = 0; i < input.size(); i++){
if(input[i] == c){
output.push_back(input.substr(j, i - j));
j = i+1;
}
}
output.push_back(input.substr(j, input.size() - j));
return output;
}
public:
int canBeTypedWords(string text, string brokenLetters) {
set<char> set;
for(char c: brokenLetters){
set.insert(c);
}
vector<string> split_text = split(text, ' ');
int count = 0;
for(int i = 0; i < split_text.size(); i++){
bool flag = true;
for(int j = 0; j < split_text[i].size(); j++){
if(set.find(split_text[i][j]) != set.end()){
flag = false;
break;
}
}
if (flag == true){
count++;
}
}
return count;
}
};Maximum Product of Two Elements in an Array
Link: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array
// Using Priority Queue
class Solution {
public:
int maxProduct(vector<int>& nums) {
priority_queue<int> pq;
for(int num: nums){
pq.push(num);
}
int num1 = pq.top();
pq.pop();
int num2 = pq.top();
return (num1 - 1) * (num2 - 1);
}
};
// Using Partial Sort
class Solution {
public:
int maxProduct(vector<int>& nums) {
partial_sort(nums.begin(), nums.begin()+2, nums.end(), greater<int>());
return (nums[0] - 1) * (nums[1] - 1);
}
};Maximum Prduct Subarray
Link: https://leetcode.com/problems/maximum-product-subarray/
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int minimum = nums[0];
int maximum = nums[0];
int maxSoFar = nums[0];
for(int i = 1; i < n; i++){
if(nums[i] < 0){
swap(minimum, maximum);
}
minimum = min(nums[i], nums[i] * minimum);
maximum = max(nums[i], nums[i] * maximum);
maxSoFar = max(maxSoFar, maximum);
}
return maxSoFar;
}
};Maximum Subarray
Link: https://leetcode.com/problems/maximum-subarray
// Using Dynamic Programming
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = nums[0];
for(int i = 1; i < n; i++){
dp[i] = max(nums[i], dp[i-1] + nums[i]);
}
int output = dp[0];
for(int i = 1; i < n; i++){
output = max(output, dp[i]);
}
return output;
}
};
// Using Kadane's Algorithm
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
int maxSoFar = nums[0];
int currSum = nums[0];
for(int i = 1; i < n; i++){
currSum = max(nums[i], currSum + nums[i]);
maxSoFar = max(maxSoFar, currSum);
}
return maxSoFar;
}
};Maximum Units on a Truck
Link: https://leetcode.com/problems/maximum-units-on-a-truck
// Greedy Approach
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(boxTypes.begin(), boxTypes.end(), [](vector<int> a, vector<int> b){
return a[1] > b[1];
});
int maxUnits = 0;
int i = 0;
while(truckSize > 0 && i < boxTypes.size()){
int numOfBoxes = boxTypes[i][0];
int numOfUnits = boxTypes[i][1];
int boxesTaken = min(truckSize, numOfBoxes);
maxUnits += (boxesTaken * numOfUnits);
truckSize -= boxesTaken;
i++;
}
return maxUnits;
}
};Merge Intervals
Link: https://leetcode.com/problems/merge-intervals/solutions/
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
if(n < 2){
return intervals;
}
sort(intervals.begin(), intervals.end(), [](vector<int> interval1, vector<int> interval2){
return interval1[0] < interval2[0];
});
int start = intervals[0][0];
int end = intervals[0][1];
vector<vector<int>> output;
for(int i = 1; i < n; i++){
int newStart = intervals[i][0];
int newEnd = intervals[i][1];
if(newStart <= end){
start = min(start, newStart);
end = max(end, newEnd);
}
else{
output.push_back(vector<int>{start, end});
start = newStart;
end = newEnd;
}
}
output.push_back(vector<int>{start, end});
return output;
}
};Merge Two Sorted Lists
Link: https://leetcode.com/problems/merge-two-sorted-lists
// Recursive
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == NULL){
return list2;
}
else 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;
}
}
};
// Iterative
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == NULL){
return list2;
}
if(list2 == NULL){
return list1;
}
ListNode* head;
if(list1->val < list2->val){
head = list1;
list1 = list1->next;
}
else{
head = list2;
list2 = list2->next;
}
ListNode* temp = head;
while(list1 != NULL && list2 != NULL){
if(list1->val < list2->val){
temp->next = list1;
list1 = list1->next;
}
else{
temp->next = list2;
list2 = list2->next;
}
temp = temp->next;
}
if(list1 == NULL){
temp->next = list2;
}
else{
temp->next = list1;
}
return head;
}
};Middle of the Linked List
Link: https://leetcode.com/problems/middle-of-the-linked-list/
// Naive Approach
class Solution {
public:
ListNode* middleNode(ListNode* head) {
if(head == NULL || head->next == NULL){
return head;
}
ListNode* temp = head;
int N = 0;
while(temp){
temp = temp->next;
N++;
}
int count = N/2;
while(count > 0){
head = head->next;
count--;
}
return head;
}
};
// Slow and Fast pointer approach
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};Min Cost Climbing Stairs
Link: https://leetcode.com/problems/min-cost-climbing-stairs
// DP + Memoization
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
if(n == 2){
return min(cost[0], cost[1]);
}
vector<int> dp(n);
dp[0] = cost[0];
dp[1] = cost[1];
for(int i = 2; i < n; i++){
dp[i] = cost[i] + min(dp[i-1], dp[i-2]);
}
return min(dp[n-1], dp[n-2]);
}
};
// Improved
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
if(n == 2){
return min(cost[0], cost[1]);
}
int prev = cost[0];
int curr = cost[1];
for(int i = 2; i < n; i++){
int temp = cost[i] + min(prev, curr);
prev = curr;
curr = temp;
}
return min(prev, curr);
}
};Min Stack
Link: https://leetcode.com/problems/min-stack
class MinStack {
public:
stack<int> originalStack;
stack<int> minStack;
MinStack() {
}
void push(int val) {
if(minStack.empty()){
minStack.push(val);
}
else{
minStack.push(min(val, minStack.top()));
}
originalStack.push(val);
}
void pop() {
minStack.pop();
originalStack.pop();
}
int top() {
return originalStack.top();
}
int getMin() {
return minStack.top();
}
};
Minimum Average of Smallest and Largest Elements
Link: https://leetcode.com/problems/minimum-average-of-smallest-and-largest-elements
// Sort and two pointers
class Solution {
public:
double minimumAverage(vector<int>& nums) {
sort(nums.begin(), nums.end());
int N = nums.size();
double minSoFar = INT_MAX;
for(int i = 0; i < N; i++){
double first = double(nums[i]);
double second = double(nums[N - i - 1]);
minSoFar = min(minSoFar, (first + second)/2);
}
return minSoFar;
}
};
class Solution {
private:
int getSum(int num){
int output = 0;
while(num > 0){
output += (num % 10);
num /= 10;
}
return output;
}
public:
int minElement(vector<int>& nums) {
int result = INT_MAX;
for(int num: nums){
result = min(result, getSum(num));
}
return result;
}
};
Minimum Height Trees
Link: https://leetcode.com/problems/minimum-height-trees
// Using Naive Approach (TLE error)
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
unordered_map<int, vector<int>> adj;
for(vector<int> edge: edges){
int a = edge[0];
int b = edge[1];
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> heights(n);
for(int i = 0; i < n; i++){
unordered_set<int> visited;
heights[i] = maxHeight(adj, visited, i);
}
int minHeight = INT_MAX;
for(int i = 0; i < n; i++){
minHeight = min(minHeight, heights[i]);
}
vector<int> output;
for(int i = 0; i < n; i++){
if(heights[i] == minHeight){
output.push_back(i);
}
}
return output;
}
int maxHeight(unordered_map<int, vector<int>>& adj, unordered_set<int> visited, int node){
if(visited.find(node) != visited.end()){
return 0;
}
visited.insert(node);
int maxSoFar = 0;
for(int edge: adj[node]){
maxSoFar = max(maxSoFar, 1 + maxHeight(adj, visited, edge));
}
return maxSoFar;
}
};
// Using Topological Sorting
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if(n == 1){
return {0};
}
unordered_map<int, vector<int>> adj;
vector<int> indegree(n);
// Forming adjacency list along with indegree count
for(vector<int> edge: edges){
int a = edge[0];
int b = edge[1];
adj[a].push_back(b);
adj[b].push_back(a);
indegree[a]++;
indegree[b]++;
}
queue<int> q;
// Push all the nodes with indegree 1 to the queue since they will be the leaf nodes and leaf nodes can't form the minimum height tree
for(int i = 0; i < n; i++){
if(indegree[i] == 1){
q.push(i);
indegree[i]--;
}
}
vector<int> output;
while(!q.empty()){
int count = q.size();
// If the queue is not empty then clear output since there is still a better answer with even lesser height
output.clear();
// Loop through all the leaf nodes and check the neighbours of those whose degree is 1
while(count > 0){
int curr = q.front();
q.pop();
output.push_back(curr);
for(int edge: adj[curr]){
indegree[edge]--;
if(indegree[edge] == 1){
q.push(edge);
}
}
count--;
}
}
return output;
}
};Minimum Length of String After Operations
Link: https://leetcode.com/problems/minimum-length-of-string-after-operations
// Greedy Solution
class Solution {
public:
int minimumLength(string s) {
unordered_map<char, int> map;
for(char c: s){
map[c]++;
}
int output = 0;
for(auto c: map){
int count = c.second;
if(count >= 3){
count = count % 2 == 0 ? 2 : 1;
}
output += count;
}
return output;
}
};Minimum Number of Operations to Convert Time
Link: https://leetcode.com/problems/minimum-number-of-operations-to-convert-time/description/
class Solution {
public:
vector<string> split(string str, char delim){
vector<string> output;
int len = str.size();
int start = 0;
int end = str.find(delim);
while(end != -1){
output.push_back(str.substr(start, end - start));
start = end + 1;
end = str.find(delim, start);
}
output.push_back(str.substr(start));
return output;
}
int convertTime(string current, string correct) {
vector<string> curr = split(current, ':');
vector<string> corr = split(correct, ':');
int currMins = (60 * stoi(curr[0])) + stoi(curr[1]);
int corrMins = (60 * stoi(corr[0])) + stoi(corr[1]);
int minMins = abs(currMins - corrMins);
int output = 0;
output += minMins / 60;
minMins = minMins % 60;
output += minMins / 15;
minMins = minMins % 15;
output += minMins / 5;
minMins = minMins % 5;
output += minMins;
return output;
}
};Move Zeroes
Link: https://leetcode.com/problems/move-zeroes/
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int zeroPointer = 0;
for(int i = 0; i < n; i++){
if(nums[i] != 0){
nums[zeroPointer] = nums[i];
zeroPointer++;
}
}
for(; zeroPointer < n; zeroPointer++){
nums[zeroPointer] = 0;
}
}
};Network delay Time
Link: https://leetcode.com/problems/network-delay-time/
//Using Dijkstra's Algorithm with Priority Queue and Adjacency List
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
unordered_map<int, vector<pair<int, int>>> adj;
// Convert given data to adjacency list
for(auto time: times){
int u = time[0];
int v = time[1];
int w = time[2];
adj[u].push_back(pair<int, int>{v, w});
}
unordered_set<int> visited;
//Use min heap to pop the smallest element
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
vector<int> weights(n, INT_MAX);
// Insert the source node to priority queue
pq.push(make_pair(0, k));
weights[k-1] = 0;
while(!pq.empty()){
// Pop the node with least weight
auto temp = pq.top();
pq.pop();
int node = temp.second;
int weight = temp.first;
// If the node has been visited then ignore else mark it as visited
if(visited.find(node) != visited.end()){
continue;
}
visited.insert(node);
// Loop though the neighbors and put them into the queue along with updating the weights
for(auto neighbor: adj[node]){
int adjnode = neighbor.first;
int adjweight = neighbor.second;
weights[adjnode-1] = min(weights[adjnode-1], weights[node-1] + adjweight);
pq.push(make_pair(weights[adjnode-1], adjnode));
}
}
int minTime = 0;
for(int w: weights){
if(w == INT_MAX){
return -1;
}
else{
minTime = max(minTime, w);
}
}
return minTime;
}
};
// Using Bellman Ford Algorithm
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
unordered_map<int, vector<pair<int,int>>> adj;
// Construct the adjaceny list
for(auto time: times){
int u = time[0];
int v = time[1];
int w = time[2];
adj[u].push_back({v, w});
}
// Create a wieghts array witn default value as infinity and source value as 0
vector<int> weights(n, INT_MAX);
weights[k-1] = 0;
// Push the source node t oqueue
queue<int> q;
q.push(k);
while(!q.empty()){
// Pop the node from the queue
int currnode = q.front();
q.pop();
int currweight = weights[currnode-1];
// Check all the neighbors of the popped node
for(pair<int, int> neighbor: adj[currnode]){
int neighnode = neighbor.first;
int neighweight = neighbor.second;
// If the neighbor node distance is greater than the popped node ditance + edge value from popped node to neighbor node then update the weight and also push it into the queue again for updating the subsequent set of values again
if(currweight + neighweight < weights[neighnode-1]){
weights[neighnode-1] = currweight + neighweight;
q.push(neighnode);
}
}
}
int minTime = 0;
for(int w: weights){
if(w == INT_MAX){
return -1;
}
else{
minTime = max(minTime, w);
}
}
return minTime;
}
};Non-overlapping Intervals
Link: https://leetcode.com/problems/non-overlapping-intervals
// Sort the array in ascending order of end times
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int n = intervals.size();
if(n <= 1){
return 0;
}
sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b){
return a[1] < b[1];
});
int output = 0;
int start = intervals[0][0];
int end = intervals[0][1];
for(int i = 1; i < n; i++){
int tempStart = intervals[i][0];
int tempEnd = intervals[i][1];
if(tempStart >= end){
start = tempStart;
end = tempEnd;
}
else{
output++;
}
}
return output;
}
};Number of Islands
Link: https://leetcode.com/problems/number-of-islands/
// Using Depth First Search
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int islands = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
islands++;
dfs(grid, i, j, m, n);
}
}
}
return islands;
}
void dfs(vector<vector<char>>& grid, int i, int j, int m, int n){
if(i >= m || j >= n || i < 0 || j < 0 || grid[i][j] == '0'){
return;
}
int moves[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
grid[i][j] = '0';
for(auto move: moves){
int newI = i + move[0];
int newJ = j + move[1];
dfs(grid, newI, newJ, m, n);
}
}
};Number of Operations to make Network Connected
Link: https://leetcode.com/problems/number-of-operations-to-make-network-connected/
// Using union find with path compression and union by rank size
class UnionFind{
public:
int componentCount;
vector<int> parent;
vector<int> size;
UnionFind(int n){
componentCount = n;
parent = vector<int>(n);
size = vector<int>(n);
// Initially set the parent of all the nodes to itslef
// Set the size of the nodes to 1
for(int i = 0; i < n; i++){
parent[i] = i;
size[i] = 1;
}
}
int Find(int node){
int root = node;
// Find the parent of node until you find a node whose parent is itself
while(root != parent[root]){
root = parent[root];
}
// Applying Path Compression
// Update the parent of all the nodes to the root node that was found
while(node != root){
int temp = parent[node];
parent[node] = root;
node = temp;
}
return node;
}
void Union(int x, int y){
int parentX = Find(x);
int parentY = Find(y);
// If both have same parent, then do nothing
if(parentX == parentY){
return;
}
// Applying Union By Rank Approach
if(size[parentX] > size[parentY]){
parent[parentY] = parentX;
size[parentX] += size[parentY];
}
else{
parent[parentX] = parentY;
size[parentY] += size[parentX];
}
// Everytime a new union is made the connected component count reduces
componentCount--;
}
};
class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
// You need atleast n-1 edges available to make connection with all the nodes
if(connections.size() < n-1){
return -1;
}
UnionFind uf(n);
for(auto edge: connections){
uf.Union(edge[0], edge[1]);
}
// If there are x number of connected components, then you need x-1 edges to connect them
return uf.componentCount - 1;
}
};Palindromic Linked List
Link: https://leetcode.com/problems/palindrome-linked-list
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> nums;
while(head != NULL){
nums.push_back(head->val);
head = head->next;
}
int n = nums.size();
for(int i = 0; i < n/2; i++){
if(nums[i] != nums[n-i-1]){
return false;
}
}
return true;
}
};Pascal’s Triangle
Link: https://leetcode.com/problems/pascals-triangle
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> output;
for(int i = 0; i < numRows; i++){
vector<int> temp;
if(i == 0){
temp = {1};
}
else if(i == 1){
temp = {1, 1};
}
else{
temp.push_back(1);
for(int j = 0; j < output[i-1].size()-1; j++){
temp.push_back(output[i-1][j] + output[i-1][j+1]);
}
temp.push_back(1);
}
output.push_back(temp);
}
return output;
}
};Permutations
Link: https://leetcode.com/problems/permutations/
// Using backtracking
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> output;
vector<int> tempList;
backtrack(output, tempList, nums);
return output;
}
void backtrack(vector<vector<int>> &output, vector<int> &tempList, vector<int> &nums){
if(tempList.size() == nums.size()){
output.push_back(tempList);
return;
}
else{
for(int i = 0; i < nums.size(); i++){
if(count(tempList.begin(), tempList.end(), nums[i]) > 0){
continue;
}
tempList.push_back(nums[i]);
backtrack(output, tempList, nums);
tempList.pop_back();
}
}
}
};Product of Array Except Self
Link: https://leetcode.com/problems/product-of-array-except-self
//Using Prefix and Sufix Array
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> prefix(n);
vector<int> suffix(n);
prefix[0] = 1;
suffix[n-1] = 1;
for(int i = 1; i < n; i++){
prefix[i] = prefix[i-1] * nums[i-1];
}
for(int i = n-2; i >= 0; i--){
suffix[i] = suffix[i+1] * nums[i+1];
}
vector<int> output(n);
for(int i = 0; i < n; i++){
output[i] = prefix[i] * suffix[i];
}
return output;
}
};
// Using Prefix and Suffix array by using output array itself instead of extra space
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> output(n, 1);
for(int i = 1; i < n; i++){
output[i] = output[i-1] * nums[i-1];
}
int curr = 1;
for(int i = n-1; i >= 0; i--){
output[i] = output[i] * curr;
curr *= nums[i];
}
return output;
}
};Range Sum Query 2D - Immutable
Link: https://leetcode.com/problems/range-sum-query-2d-immutable/
// Using 2 Dimensional Prefix Sum
class NumMatrix {
private:
vector<vector<int>> prefixSum;
public:
NumMatrix(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = rows > 0 ? matrix[0].size() : 0;
this->prefixSum = vector<vector<int>>(rows+1, vector<int>(cols+1, 0));
for(int i = 1; i <= rows; i++){
for(int j = 1; j <= cols; j++){
this->prefixSum[i][j] = matrix[i-1][j-1] + this->prefixSum[i-1][j] + this->prefixSum[i][j-1] - this->prefixSum[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return this->prefixSum[row2+1][col2+1] - this->prefixSum[row2+1][col1] - this->prefixSum[row1][col2+1] + this->prefixSum[row1][col1];
}
};Range Sum Query - Immutable
Link: https://leetcode.com/problems/range-sum-query-immutable
// Using Prefix Sum
class NumArray {
private:
vector<int> rangeSum;
public:
NumArray(vector<int>& nums) {
int n = nums.size();
this->rangeSum.push_back(nums[0]);
for(int i = 1; i < n; i++){
this->rangeSum.push_back(this->rangeSum[i-1] + nums[i]);
}
}
int sumRange(int left, int right) {
if(left == 0){
return this->rangeSum[right];
}
else{
return this->rangeSum[right] - this->rangeSum[left-1];
}
}
};Ransom Note
Link: https://leetcode.com/problems/ransom-note/
// Using Hashmap
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if(ransomNote.size() > magazine.size()){
return false;
}
unordered_map<char,int> freq;
for(char c: magazine){
if(freq.find(c) != freq.end()){
freq[c]++;
}
else{
freq[c] = 1;
}
}
for(char c: ransomNote){
if(freq.find(c) == freq.end()){
return false;
}
else{
if(freq[c] == 1){
freq.erase(c);
}
else{
freq[c]--;
}
}
}
return true;
}
};Redundant Connection
Link: https://leetcode.com/problems/redundant-connection
// Using Union Find
class UnionFind{
public:
vector<int> parent;
UnionFind(int n){
parent = vector<int>(n);
for(int i = 0; i < n; i++){
parent[i] = i;
}
}
int Find(int node){
while(node != parent[node]){
node = parent[node];
}
return node;
}
bool UnionizeIfDifferentParent(int x, int y){
int px = Find(x);
int py = Find(y);
if(px == py){
return false;
}
parent[px] = py;
return true;
}
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = 0;
for(auto edge: edges){
n = max({n, edge[0], edge[1]});
}
UnionFind uf(n+1);
for(auto edge: edges){
// If two nodes have same parent then that's the edge which is converting it to a graph
if(!uf.UnionizeIfDifferentParent(edge[0], edge[1])){
return edge;
}
}
return {0, 0};
}
};Remove Nth Node From End of List
Link: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* slow = head;
ListNode* fast = head;
while(n > 0){
fast = fast->next;
n--;
}
if(fast == NULL){
return head->next;
}
while(fast->next != NULL){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
};Reverse Linked List
Link: https://leetcode.com/problems/reverse-linked-list/
// Iterative Solution
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
ListNode* next;
while(curr != NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};Rotate Array
Link: https://leetcode.com/problems/rotate-array/
// Interesting Solution
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};Rotate Image
Link: https://leetcode.com/problems/rotate-image
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i = 0; i < n/2; i++){
for(int j = i; j < n - i - 1; j++){
int temp = matrix[n-j-1][i];
matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
matrix[j][n-i-1] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
};Rotting Oranges
Link: https://leetcode.com/problems/rotting-oranges
// Using Breadth First Search
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int 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});
}
if(grid[i][j] == 1){
fresh++;
}
}
}
int minutes = 0;
int moves[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while(!q.empty() && fresh != 0){
int count = q.size();
while(count > 0){
pair<int, int> temp = q.front();
q.pop();
int x = temp.first;
int y = temp.second;
for(auto move: moves){
int newI = x + move[0];
int newJ = y + move[1];
if(newI < 0 || newI >= m || newJ < 0 || newJ >= n || grid[newI][newJ] != 1){
continue;
}
grid[newI][newJ] = 2;
fresh--;
q.push({newI, newJ});
}
count--;
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
};Same Tree
Link: https://leetcode.com/problems/same-tree/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q == NULL){
return true;
}
else if(p == NULL || q == NULL){
return false;
}
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};Search in a Binary Search Tree
Link: https://leetcode.com/problems/search-in-a-binary-search-tree
// Using Recursion
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(!root){
return nullptr;
}
if(root->val == val){
return root;
}
else if(root->val > val){
return searchBST(root->left, val);
}
else{
return searchBST(root->right, val);
}
}
};Search in a Rotated Sorted Array
Link: https://leetcode.com/problems/search-in-rotated-sorted-array
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int low = 0;
int high = n-1;
while(low <= high){
int mid = (low + high)/2;
if(target == nums[mid]){
return mid;
}
if(nums[low] <= nums[mid]){ // Check Left portion
if(target > nums[mid] || target < nums[low]){
low = mid+1;
}
else{
high = mid-1;
}
}
else{ // Check Right portion
if(target < nums[mid] || target > nums[high]){
high = mid-1;
}
else{
low = mid+1;
}
}
}
return -1;
}
};Set Matrix Zeroes
Link: https://leetcode.com/problems/set-matrix-zeroes
// Using O(m+n) space
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
std::vector<int> M(m, 1);
std::vector<int> N(n, 1);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == 0){
M[i] = 0;
N[j] = 0;
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(M[i] == 0 || N[j] == 0){
matrix[i][j] = 0;
}
}
}
}
};Snake in Matrix
Link: https://leetcode.com/problems/snake-in-matrix/
class Solution {
public:
int finalPositionOfSnake(int n, vector<string>& commands) {
int x = 0;
int y = 0;
for(string command: commands){
if(command == "LEFT"){
x--;
}
else if(command == "RIGHT"){
x++;
}
else if(command == "UP"){
y--;
}
else if(command == "DOWN"){
y++;
}
}
return (y * n) + x;
}
};
class Solution {
public:
int balancedStringSplit(string s) {
int output = 0;
int count = 0;
for(int i = 0; i < s.size(); i++){
count += s[i] == 'L' ? 1 : -1;
if(count == 0){
output++;
}
}
return output;
}
};
// Naive
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> output(nums.size());
for(int i = 0; i < nums.size(); i++){
output.push_back(nums[i] * nums[i]);
}
sort(output.begin(), output.end());
return output;
}
};
// Two pointer approach
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int N = nums.size();
vector<int> output(N);
int a = 0;
int b = N-1;
for(int i = N-1; i >= 0; i--){
if(abs(nums[a]) > abs(nums[b])){
output[i] = nums[a] * nums[a];
a++;
}
else{
output[i] = nums[b] * nums[b];
b--;
}
}
return output;
}
};Subsets
Link: https://leetcode.com/problems/subsets/
// Using Backtracking
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> output;
vector<int> tempList;
backtrack(output, tempList, nums, 0);
return output;
}
void backtrack(vector<vector<int>> &output, vector<int> &tempList, vector<int> &nums, int start){
output.push_back(tempList);
for(int i = start; i < nums.size(); i++){
tempList.push_back(nums[i]);
backtrack(output, tempList, nums, i+1);
tempList.pop_back();
}
}
};Subtree of Another Tree
Link: https://leetcode.com/problems/subtree-of-another-tree
class Solution {
private:
bool isSametree(TreeNode* root, TreeNode* subRoot){
if(root == NULL && subRoot == NULL){
return true;
}
if(root == NULL || subRoot == NULL){
return false;
}
if(root->val == subRoot->val){
return isSametree(root->left, subRoot->left) && isSametree(root->right, subRoot->right);
}
else{
return false;
}
}
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root == NULL){
return false;
}
if(isSametree(root, subRoot)){
return true;
}
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};Sum of Left Leaves
Link: https://leetcode.com/problems/sum-of-left-leaves/
// Using Depth First Search
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
return sum(root, false);
}
int sum(TreeNode* root, bool isLeft){
if(!root){
return 0;
}
if(root->left == NULL && root->right == NULL && isLeft){
return root->val;
}
return sum(root->left, true) + sum(root->right, false);
}
};Surface Area of 3D Shapes
Link: https://leetcode.com/problems/surface-area-of-3d-shapes
class Solution {
public:
int surfaceArea(vector<vector<int>>& grid) {
int output = 0;
int n = grid.size();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] != 0){
output += (grid[i][j] * 4) + 2;
}
if(i != 0){
output -= min(grid[i][j], grid[i-1][j]) * 2;
}
if(j != 0){
output -= min(grid[i][j], grid[i][j-1]) * 2;
}
}
}
return output;
}
};Symmetric Tree
Link: https://leetcode.com/problems/symmetric-tree/
// Recursive
class Solution {
private:
bool isSymmetric(TreeNode* left, TreeNode* right){
if(left == NULL && right == NULL){
return true;
}
else if(left == NULL || right == NULL){
return false;
}
return left->val == right->val && isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
}
public:
bool isSymmetric(TreeNode* root) {
return isSymmetric(root->left, root->right);
}
};Throne Inheritance
Link: https://leetcode.com/problems/throne-inheritance/
// Using BFS Algorithm (Time Limit Exceeded)
class Tree{
public:
bool isAlive;
string name;
vector<Tree*> children;
Tree(string n){
isAlive = true;
name = n;
}
};
class ThroneInheritance {
private:
Tree* root;
public:
ThroneInheritance(string kingName) {
root = new Tree(kingName);
}
void birth(string parentName, string childName) {
Tree* curr = root;
queue<Tree*> q;
q.push(curr);
while(q.size() != 0){
Tree* temp = q.front();
q.pop();
if(temp->name == parentName){
Tree* newChild = new Tree(childName);
temp->children.push_back(newChild);
return;
}
else{
for(auto child: temp->children){
q.push(child);
}
}
}
}
void death(string name) {
Tree* curr = root;
queue<Tree*> q;
q.push(curr);
while(q.size() != 0){
Tree* temp = q.front();
q.pop();
if(temp->name == name){
temp->isAlive = false;
return;
}
for(auto child: temp->children){
q.push(child);
}
}
}
vector<string> getInheritanceOrder() {
vector<string> output;
Tree* curr = root;
PreOrderTraversal(curr, output);
return output;
}
void PreOrderTraversal(Tree* curr, vector<string>& output){
if(curr == NULL){
return;
}
if(curr->isAlive){
output.push_back(curr->name);
}
for(auto child: curr->children){
PreOrderTraversal(child, output);
}
}
};
// Using Unordered map
class Tree{
public:
string name;
vector<Tree*> children;
Tree(string n){
name = n;
}
};
class ThroneInheritance {
private:
Tree* root;
unordered_map<string, Tree*> map;
public:
ThroneInheritance(string kingName) {
root = new Tree(kingName);
map[kingName] = root;
}
void birth(string parentName, string childName) {
Tree* newChild = new Tree(childName);
map[parentName]->children.push_back(newChild);
map[childName] = newChild;
}
void death(string name) {
if(map.find(name) != map.end()){
map[name] = NULL;
}
}
vector<string> getInheritanceOrder() {
vector<string> output;
Tree* curr = root;
PreOrderTraversal(curr, output);
return output;
}
void PreOrderTraversal(Tree* curr, vector<string>& output){
if(curr == NULL){
return;
}
if(map[curr->name] != NULL){
output.push_back(curr->name);
}
for(auto child: curr->children){
PreOrderTraversal(child, output);
}
}
};
Time based Key-Value Store
Link: https://leetcode.com/problems/time-based-key-value-store
class TimeMap {
public:
unordered_map<string, vector<pair<int, string>>> map;
TimeMap() {
}
void set(string key, string value, int timestamp) {
map[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
if(map.find(key) == map.end()){
return "";
}
int low = 0;
int high = map[key].size() - 1;
string result = "";
while(low <= high){
int mid = low + ((high-low)/2);
if(map[key][mid].first <= timestamp){
result = map[key][mid].second;
low = mid + 1;
}
else{
high = mid - 1;
}
}
return result;
}
};Top K Frequent Elements
Link: https://leetcode.com/problems/top-k-frequent-elements
// Using Priority Queue
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for(int num: nums){
map[num]++;
}
priority_queue<pair<int, int>> pq;
for(auto item: map){
pq.push(make_pair(item.second, item.first));
}
vector<int> output;
while(k > 0 && !pq.empty()){
pair<int, int> temp = pq.top();
pq.pop();
output.push_back(temp.second);
k--;
}
return output;
}
};Trapping Rain Water
Link: https://leetcode.com/problems/trapping-rain-water
//Best link for explanation - https://leetcode.com/problems/trapping-rain-water/solutions/1374608/c-java-python-maxleft-maxright-so-far-with-picture-o-1-space-clean-concise
// Using DP
class Solution {
public:
int trap(vector<int>& height) {
int N = height.size();
if(N <= 2){
return 0;
}
vector<int> left(N);
vector<int> right(N);
left[0] = height[0];
right[N-1] = height[N-1];
for(int i = 1; i < N; i++){
left[i] = max(height[i], left[i-1]);
}
for(int i = N-2; i >= 0; i--){
right[i] = max(height[i], right[i+1]);
}
int maxWater = 0;
for(int i = 0; i < N; i++){
maxWater += min(left[i], right[i]) - height[i];
}
return maxWater;
}
};
// Two Pointer Approach
class Solution {
public:
int trap(vector<int>& height) {
int N = height.size();
if(N <= 2){
return 0;
}
int left = 1;
int right = N-2;
int maxLeft = height[0];
int maxRight = height[N-1];
int maxWater = 0;
while(left <= right){
if(maxLeft < maxRight){
if(height[left] < maxLeft){
maxWater += maxLeft - height[left];
}
else{
maxLeft = height[left];
}
left++;
}
else{
if(height[right] < maxRight){
maxWater += maxRight - height[right];
}
else{
maxRight = height[right];
}
right--;
}
}
return maxWater;
}
};Two Sum
Link: https://leetcode.com/problems/two-sum/
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> map;
vector<int> output;
for(int i = 0; i < nums.size(); i++){
if(map.find(target - nums[i]) != map.end()){
output.push_back(i);
output.push_back(map[target-nums[i]]);
break;
}
else{
map[nums[i]] = i;
}
}
return output;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> map;
for(int i = 0; i < nums.size(); i++){
map[nums[i]] = i;
}
vector<int> output;
for(int i = 0; i < nums.size(); i++){
int req = target - nums[i];
if(map.find(req) != map.end()){
if(map[req] != i){
output.push_back(i);
output.push_back(map[req]);
break;
}
}
}
return output;
}
};Unique Paths
Link: https://leetcode.com/problems/unique-paths
// Tabulation
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(i == 0 || j == 0){
dp[i][j] = 1;
}
else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
// Tabulation - Space Optimized
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
};Valid Anagram
Link: https://leetcode.com/problems/valid-anagram
// Using frequency calculation using static array
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()){
return false;
}
int freq[26] = {0};
for(int i = 0; i < s.size(); i++){
freq[s[i] - 'a']++;
freq[t[i] - 'a']--;
}
for(int val: freq){
if(val != 0){
return false;
}
}
return true;
}
};
// Using string sorting
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()){
return false;
}
sort(s.begin(), s.end(), [](char c1, char c2){
return c1 < c2;
});
sort(t.begin(), t.end(), [](char c1, char c2){
return c1 < c2;
});
return s == t;
}
};Valid Palindrome
Link: https://leetcode.com/problems/valid-palindrome/
// Naive Approach
class Solution {
public:
bool isPalindrome(string s) {
string s2;
for(char c: s){
if(isalnum(c)){
s2 += tolower(c);
}
}
int N = s2.size();
for(int i = 0; i < N; i++){
if(s2[i] != s2[N-i-1]){
return false;
}
}
return true;
}
};
// Two Pointer Approach
class Solution {
public:
bool isPalindrome(string s) {
int N = s.size();
int i = 0;
int j = N - 1;
while(i < j){
if(!isalnum(s[i])){
i++;
}
else if(!isalnum(s[j])){
j--;
}
else if(tolower(s[i]) != tolower(s[j])){
return false;
}
else{
i++;
j--;
}
}
return true;
}
};Valid Parentheses
Link: https://leetcode.com/problems/valid-parentheses/
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> mapper{{'(',')'}, {'{', '}'}, {'[',']'}};
stack<char> st;
for(char c: s){
if(mapper.find(c) != mapper.end()){
st.push(mapper[c]);
}
else{
if(st.size() == 0 || st.top() != c){
return false;
}
else{
st.pop();
}
}
}
return st.size() == 0;
}
};
// Elegant solution
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(char c: s){
if(c == '('){
st.push(')');
}
else if(c == '['){
st.push(']');
}
else if(c == '{'){
st.push('}');
}
else{
if(st.size() > 0 && c == st.top()){
st.pop();
}
else{
return false;
}
}
}
return st.size() == 0;
}
};Valid Sudoku
Link: https://leetcode.com/problems/valid-sudoku
class Solution {
private:
bool isRowsValid(vector<vector<char>>& board){
for(int i = 0; i < 9; i++){
unordered_set<char> set;
for(int j = 0; j < 9; j++){
if(board[i][j] == '.'){
continue;
}
if(set.find(board[i][j]) == set.end()){
set.insert(board[i][j]);
}
else{
return false;
}
}
}
return true;
}
bool isColumnsValid(vector<vector<char>>& board){
for(int i = 0; i < 9; i++){
unordered_set<char> set;
for(int j = 0; j < 9; j++){
if(board[j][i] == '.'){
continue;
}
if(set.find(board[j][i]) == set.end()){
set.insert(board[j][i]);
}
else{
return false;
}
}
}
return true;
}
bool isBoxValid(vector<vector<char>>& board){
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
unordered_set<char> set;
for(int a = 0; a < 3; a++){
for(int b = 0; b < 3; b++){
int temp = board[(3 * i) + a][(3 * j) + b];
if(temp == '.'){
continue;
}
if(set.find(temp) == set.end()){
set.insert(temp);
}
else{
return false;
}
}
}
}
}
return true;
}
public:
bool isValidSudoku(vector<vector<char>>& board) {
return isRowsValid(board) && isColumnsValid(board) && isBoxValid(board);
}
};Validate Binary Search Tree
Link: https://leetcode.com/problems/validate-binary-search-tree
// Recursive Solution
class Solution {
public:
bool isValidBST(TreeNode* root) {
return validate(root, NULL, NULL);
}
bool validate(TreeNode* root, TreeNode* minval, TreeNode* maxval){
if(root == NULL){
return true;
}
if((minval == NULL || root->val > minval->val) && (maxval == NULL || root->val < maxval->val)){
return validate(root->left, minval, root) && validate(root->right, root, maxval);
}
return false;
}
};Vowels Game in a String
Link: https://leetcode.com/problems/vowels-game-in-a-string
// If there's a vowel in the string, then alice wins
class Solution {
public:
bool doesAliceWin(string s) {
for(char c: s){
if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
return true;
}
}
return false;
}
};