Reverse an array

Read more →

Find the maximum and minimum element in an array

https://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/ Divide and conquer struct Pair { int min; int max; }; struct Pair getMinMax(int arr[], int low, int high) { struct Pair minmax, mml, mmr; int mid; if (low == high) { minmax.max = arr[low]; minmax.min = arr[low]; return minmax; } if (high - low == 1) { if (arr[low] > arr[high]) { minmax.max = arr[low]; minmax.min = arr[high]; } else { minmax.max = arr[high]; minmax.min = arr[low]; } return minmax; } mid = low + (high - low) / 2; mml = getMinMax(arr, low, mid); mmr = getMinMax(arr, mid + 1, high); minmax.
Read more →

Find the Kth max and min element in an array

https://practice.geeksforgeeks.org/problems/kth-smallest-element/0 Make priority queue of size k, insert first k elements from the array For the remaining elements, pop and insert into pq if element is smaller than top class Solution { public: int kthSmallest(int arr[], int l, int r, int k) { priority_queue<int, vector<int>> pq(arr, arr + k); int n = r - l + 1; for (int i = k; i < n; i++) { if (arr[i] < pq.
Read more →

Sort an array of 0s, 1s and 2s

Read more →

Move all the negative elements to one side of the array

Read more →

Find the union and intersection of the two sorted arrays

https://practice.geeksforgeeks.org/problems/union-of-two-arrays/0 Union Does not handle duplicates class Solution { public: int doUnion(int a[], int n, int b[], int m) { int i = 0, j = 0; sort(a, a + n); sort(b, b + m); vector<int> v; while (i < n && j < m) { if (a[i] < b[j]) { v.push_back(a[i]); i++; } else if (a[i] > b[j]) { v.push_back(b[j]); j++; } else { v.push_back(a[i]); // or // v.
Read more →

Cyclically rotate an array by one

Read more →

Minimise the maximum difference between heights

Read more →

Minimum number of jumps to reach end of an array

Read more →

Find the duplicate in an array of N+1 integers

Read more →

Kadane’s algorithm

Read more →

Merge intervals

Read more →

Next permutation

https://leetcode.com/problems/next-permutation/ Find non-increasing sequence from right Find just greater number from right Swap them Reverse from i to end class Solution { public: void nextPermutation(vector<int> &nums) { int i = nums.size() - 2; while (i >= 0 && nums[i + 1] <= nums[i]) { i--; } if (i >= 0) { int j = nums.size() - 1; while (j >= 0 && nums[j] <= nums[i]) { j--; } swap(nums[i], nums[j]); } reverse(nums.
Read more →

Count inversion

Read more →

Best time to buy and sell stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ Only 1 transaction is allowed One pass, just need to check the lowest valley/highest peak (and their difference) This problem reduces to maximum difference between two elements when larger element must come after smaller element class Solution { public: int maxProfit(vector<int> &prices) { int n = prices.size(); int minPrice = INT_MAX, maxProfit = 0; for (int i = 0; i < n; i++) { minPrice = min(minPrice, prices[i]); maxProfit = max(maxProfit, prices[i] - minPrice); } return maxProfit; } }; Maximum profit by buying and selling a share at most twice https://leetcode.
Read more →

Find all pairs on integer array whose sum is equal to K

Read more →

Find common elements in 3 sorted arrays

Read more →

Find if there is any subarray with sum equal to 0

Read more →

Find maximum product subarray

Read more →

Find longest consecutive subsequence

Read more →

Given an array of size N and a number K, find all elements that appear more than N/K times

Read more →

Find whether an array is a subset of another array

https://practice.geeksforgeeks.org/problems/array-subset-of-another-array/0 Can also insert into set twice, and check if size is the same. string isSubset(int arr1[], int arr2[], int m, int n) { int i = 0, j = 0; if (m < n) return "No"; sort(arr1, arr1 + m); sort(arr2, arr2 + n); while (i < n && j < m) { if (arr1[j] < arr2[i]) j++; else if (arr1[j] == arr2[i]) { j++; i++; } else if (arr1[j] > arr2[i]) return "No"; } return (i < n) ?
Read more →

Find the triplet that sum to a given value

https://practice.geeksforgeeks.org/problems/triplet-sum-in-array/0 class Solution { public: bool find3Numbers(int A[], int n, int X) { sort(A, A + n); for (int i = 0; i < n - 2; i++) { int l = i + 1, r = n - 1; while (l < r) { int sum = A[i] + A[l] + A[r]; if (sum == X) return true; else if (sum < X) { l++; } else { r--; } } } return false; } }; When X = 0 https://leetcode.
Read more →

Trapping rain water

https://practice.geeksforgeeks.org/problems/trapping-rain-water/0 Find lMax, rMax ans += min(lMax, rMax) - currHeight class Solution { public: int trap(vector<int> &height) { if (height.empty()) return 0; int n = height.size(); vector<pair<int, int>> maxHeights(n); maxHeights[0].first = height[0]; maxHeights[n - 1].second = height[n - 1]; for (int i = 1; i < n; i++) { maxHeights[i].first = max(height[i], maxHeights[i - 1].first); } for (int i = n - 2; i >= 0; i--) { maxHeights[i].second = max(height[i], maxHeights[i + 1].
Read more →

Chocolate distribution

Read more →

Minimum number of merge operations required to make an array palindrome

Read more →

Search an element in a matrix

Read more →

Reverse a string

Read more →

Check whether a string is palindrome

Read more →

Find duplicate characters in a string

Read more →

Why are strings immutable in Java?

Read more →

Check whether one string is a rotation of another

Read more →

Check whether a string is a valid shuffle of two strings

Read more →

Count and say

Read more →

Find the longest palindrome in a string

https://leetcode.com/problems/longest-palindromic-substring/ Expand from center, check for even and odd palindromes class Solution { public: string longestPalindrome(string s) { if (s.size() < 1) return ""; int start = 0; int l = s.size(); int maxLength = 1; for (int i = 0; i < l; i++) { // Odd int low = i - 1, high = i; while (low >= 0 && high < l && s[low] == s[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } low--; high++; } // Even low = i - 1, high = i + 1; while (low >= 0 && high < l && s[low] == s[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } low--; high++; } } return s.
Read more →

Split the binary string into two substring with equal 0s and 1s

Read more →

Edit distance

Read more →

Balanced parenthesis

Read more →

Convert a sentence into its equivalent mobile numeric keypad sequence

Read more →

Minimum number of bracket reversals needed to make an expression balanced

https://practice.geeksforgeeks.org/problems/count-the-reversals/0 }{{}}{{{ Remove all valid pairs, remaining string is like }}}…{{{… ans = ceil(lBraces) + ceil(rBraces) in remaining string int countRev(string s) { int n = s.size(); if (n % 2 != 0) return -1; stack<char> st; for (int i = 0; i < n; i++) { if (s[i] == '}' && !st.empty()) { if (st.top() == '{') st.pop(); else st.push(s[i]); } else st.push(s[i]); } int lCount = 0; while (!
Read more →

Count of number of given string in 2D character array

https://www.geeksforgeeks.org/find-count-number-given-string-present-2d-character-array/ class Solution { bool searchUtil(int r, int c, string &word, vector<pair<int, int>> &dir, vector<vector<char>> &grid) { int R = grid.size(); int C = grid[0].size(); if (grid[r][c] != word[0]) { return false; } int len = word.length(); for (int i = 0; i < 8; i++) { int k = 1, rd = r + dir[i].first, cd = c + dir[i].second; while (k < len) { if (rd >= R || cd >= C || rd < 0 || cd < 0) { break; } if (grid[rd][cd] !
Read more →

Longest common prefix

https://leetcode.com/problems/longest-common-prefix/ Divide and conquer, compare left and right subarrays. class Solution { string lcp(vector<string> &strs, int l, int r) { if (l == r) return strs[l]; else { int mid = l + (r - l) / 2; string leftLCP = lcp(strs, l, mid); string rightLCP = lcp(strs, mid + 1, r); return commonPrefix(leftLCP, rightLCP); } } string commonPrefix(string left, string right) { int l = min(left.length(), right.length()); int ctr = 0; while (ctr < l && left[ctr] == right[ctr]) { ctr++; } return left.
Read more →

Number of flips to make binary string alternate

Read more →

Find the second most repeated word in string

https://practice.geeksforgeeks.org/problems/second-most-repeated-string-in-a-sequence/0 class Solution { public: string secFrequent(string arr[], int n) { map<string, int> mp; for (int i = 0; i < n; i++) { mp[arr[i]]++; } int maxFreq = -1, notMaxFreq = -1; string ans = ""; for (auto it : mp) { if (it.second > maxFreq) { notMaxFreq = maxFreq; maxFreq = it.second; } else if (it.second > notMaxFreq && it.second != maxFreq) { notMaxFreq = it.second; } } for (auto it : mp) { if (it.
Read more →

Recursively remove all adjacent duplicates

Read more →

Transform one string to another using minimum number of given operation

https://www.geeksforgeeks.org/transform-one-string-to-another-using-minimum-number-of-given-operation/ Check relative character frequencies & length of strings Start from end, increase res till character found in B Doing this because insertion is only allowed in front of A #include <bits/stdc++.h> using namespace std; int minOps(string A, string B) { int n = A.length(), m = B.length(); if (n != m) return -1; map<char, pair<int, int>> mp; for (int i = 0; i < n; i++) { mp[A[i]].
Read more →

Find first and last positions of an element in a sorted array

Read more →

Find a fixed point (value equal to index) in a given array

Read more →

Search in a rotated sorted array

Read more →

Find missing and repeating

Read more →

Find majority element

Read more →

Searching in an array where adjacent differ by at most K

Read more →

Merge 2 sorted arrays

Read more →

Sort array according to count of set bits

Read more →

Kth smallest number again

https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/kth-smallest-number-again-2/ #include <bits/stdc++.h> using namespace std; void solve() { int n, q; cin >> n >> q; vector<pair<int, int>> v(n); for (auto &it : v) cin >> it.first >> it.second; sort(v.begin(), v.end()); int idx = 0; for (int i = 1; i < n; i++) { if (v[idx].second >= v[i].first) { v[idx].second = max(v[idx].second, v[i].second); } else { idx++; v[idx] = v[i]; } } while (q--) { int k; cin >> k; int ans = -1; for (int i = 0; i <= idx; i++) { if (v[i].
Read more →

Book allocation aka Painter’s Partition

Read more →

Missing number in AP

Read more →

Reverse a linked list

Read more →

Reverse a linked list in group of given size

https://practice.geeksforgeeks.org/problems/reverse-a-linked-list-in-groups-of-given-size/1 class Solution { public: struct node *reverse(struct node *head, int k) { stack<node *> st; struct node *curr = head; struct node *prev = nullptr; while (curr != nullptr) { int ctr = 0; while (curr != nullptr && ctr < k) { st.push(curr); curr = curr->next; ctr++; } while (!st.empty()) { if (prev == nullptr) { prev = st.top(); head = prev; st.pop(); } else { prev->next = st.
Read more →

Detect loop in a linked list

Read more →

Delete loop in a linked list

https://practice.geeksforgeeks.org/problems/remove-loop-in-linked-list/1 class Solution { public: void removeLoop(Node *head) { Node *hare = head, *tor = head; while (hare != nullptr && hare->next != nullptr && tor != nullptr) { tor = tor->next; hare = hare->next->next; if (hare == tor) { Node *ptr1 = tor, *ptr2 = tor; unsigned int k = 1; while (ptr1->next != ptr2) { ptr1 = ptr1->next; k++; } ptr1 = head; ptr2 = head; while (k--) ptr2 = ptr2->next; while (ptr2 !
Read more →

Find the starting point of the loop

https://leetcode.com/problems/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; bool isCycle = false; while (slow != NULL && fast != NULL) { slow = slow->next; if (fast->next == NULL) return NULL; fast = fast->next->next; if (slow == fast) { isCycle = true; break; } } if (!isCycle) return NULL; slow = head; while (slow !
Read more →

Remove duplicates in a sorted linked list

Read more →

Remove duplicates in a unsorted linked list

Read more →

Move the last element to front in a linked list

Read more →

Add 1 to a number represented as a linked list

https://practice.geeksforgeeks.org/problems/add-1-to-a-number-represented-as-linked-list/1 class Solution { Node *reverse(Node *head) { Node *prev = nullptr; Node *current = head; Node *next; while (current != nullptr) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } Node *addOneUtil(Node *head) { Node *ans = head; Node *temp, *prev = nullptr; int carry = 1, sum = 0; while (head != nullptr) { sum = carry + head->data; carry = (sum >= 10) ?
Read more →

Add two numbers represented by linked lists

https://practice.geeksforgeeks.org/problems/add-two-numbers-represented-by-linked-lists/1 class Solution { Node *reverse(Node *head) { Node *prev = nullptr, *curr = head, *next = nullptr; while (curr != nullptr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } public: Node *addTwoLists(struct Node *first, struct Node *second) { first = reverse(first); second = reverse(second); int c = 0, sum = 0; Node *start = nullptr, *end = nullptr; while (first !
Read more →

Intersection of two sorted linked list

Read more →

Intersection point of two linked lists

Read more →

Find the middle element of a linked list

Read more →

Check if a linked list is a circular linked list

Read more →

Check whether the singly linked list is a palindrome

https://practice.geeksforgeeks.org/problems/check-if-linked-list-is-pallindrome/1 class Solution { Node *reverseLL(Node *head) { Node *curr = head, *prev = nullptr, *next; while (curr != nullptr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } public: // Function to check whether the list is palindrome. bool isPalindrome(Node *head) { int ctr = 0; Node *slow = head, *fast = head; if (head == nullptr || head->next == nullptr) { return true; } while (slow !
Read more →

Reverse a doubly linked list

Read more →

Why is quicksort preferred for arrays while merge sort for linked lists?

Quicksort is also one of the efficient algorithms with the average time complexity of O(nlogn). But the worst-case time complexity is O(n^2). Also, variations of the quick sort like randomized quicksort are not efficient for the linked list because unlike arrays, random access in the linked list is not possible in O(1) time. If we sort the linked list using quicksort, we would end up using the head as a pivot element which may not be efficient in all scenarios.
Read more →

Flatten a linked list

Read more →

Clone a linked list with next and random pointer

https://leetcode.com/problems/copy-list-with-random-pointer/ Inefficient class Solution { public: Node *copyRandomList(Node *head) { map<Node *, Node *> mp; for (Node *c = head; c != nullptr; c = c->next) mp[c] = new Node(c->val); for (Node *c = head; c != nullptr; c = c->next) { mp[c]->next = mp[c->next]; mp[c]->random = mp[c->random]; } return mp[head]; } }; Optimised class Solution { public: Node *copyRandomList(Node *head) { Node *iter = head; Node *front = head; while (iter !
Read more →

Level order traversal

Read more →

Height of a tree

Read more →

Diameter of a tree

Read more →

Mirror of a tree

Read more →

Inorder traversal of a tree

Read more →

Preorder traversal of a tree

Read more →

Postorder traversal of a tree

Read more →

Right view of a tree

Read more →

Left view of a tree

Read more →

Check if a tree is balanced

Read more →

Find LCA in a binary tree

Read more →

Find a value in a BST

Read more →

Find min and max value in a BST

Read more →

Check if a tree is a BST

Read more →

Find LCA in a BST

Read more →

Fractional knapsack

https://practice.geeksforgeeks.org/problems/fractional-knapsack/0 class Solution { public: double fractionalKnapsack(int W, Item arr[], int n) { sort(arr, arr + n, [](const Item &a, const Item &b) { return ((double)a.value / a.weight) > (double)b.value / b.weight; }); int currWeight = 0; double cost = 0; for (int i = 0; i < n; i++) { if (arr[i].weight + currWeight <= W) { currWeight += arr[i].weight; cost += arr[i].value; } else { cost += (arr[i].value / (double)arr[i].
Read more →

Find minimum number of coins

https://practice.geeksforgeeks.org/problems/coin-piles/0 class Solution { public: int coinChange(vector<int> &coins, int amount) { int n = coins.size(); int dp[n + 1][amount + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= amount; j++) { if (j == 0) { dp[i][j] = 0; } if (i == 0) { dp[i][j] = INT_MAX - 1; } } } dp[0][0] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= amount; j++) { if (coins[i - 1] <= j) { dp[i][j] = min(dp[i - 1][j], 1 + dp[i][j - coins[i - 1]]); } else { dp[i][j] = dp[i - 1][j]; } } return dp[n][amount] == INT_MAX - 1 ?
Read more →

Implement stack from scratch

Read more →

Implement queue from scratch

Read more →

Implement 2 stack in an array

Read more →

Reverse a string using stack

Read more →

Implement a maxheap/minheap

https://www.geeksforgeeks.org/building-heap-from-array/ #include <bits/stdc++.h> using namespace std; class Heap { vector<int> v; bool isMinHeap; bool compare(int a, int b) { return isMinHeap ? a < b : a > b; } void heapify(int i) { int left = 2 * i, right = 2 * i + 1; int minIdx = i; if (left < (int)v.size() && compare(v[left], v[minIdx])) { minIdx = left; } if (right < (int)v.size() && compare(v[right], v[minIdx])) { minIdx = right; } if (minIdx !
Read more →

Kth largest element in an array

Read more →

Merge K sorted arrays

Read more →

Connect N ropes with minimum cost

Read more →

Implement BFS

https://practice.geeksforgeeks.org/problems/bfs-traversal-of-graph/1 GfG has incorrect testcases. Always check for multiple components, which requires the commented outer visited loop. class Solution { vector<int> bfsTraversal; void bfs(int i, vector<bool> &visited, vector<int> adj[]) { queue<int> q; visited[i] = true; q.push(i); while (!q.empty()) { int node = q.front(); q.pop(); bfsTraversal.push_back(node); for (int it : adj[node]) { if (!visited[it]) { visited[it] = true; q.push(it); } } } } public: vector<int> bfsOfGraph(int V, vector<int> adj[]) { vector<bool> visited(V, false); // for (int i = 0; i < V; i++) { // if (!
Read more →

Implement DFS

https://practice.geeksforgeeks.org/problems/depth-first-traversal-for-a-graph/1 Recursive class Solution { vector<int> dfsTraversal; void dfsHelper(int i, vector<bool> &visited, vector<int> adj[]) { visited[i] = true; dfsTraversal.push_back(i); for (vector<int>::iterator it = adj[i].begin(); it != adj[i].end(); it++) { if (!visited[*it]) { dfs(*it, visited, adj); } } } public: vector<int> dfsOfGraph(int V, vector<int> adj[]) { vector<bool> visited(V, false); for (int i = 0; i < V; i++) { if (!visited[i]) { dfsHelper(i, visited, adj); } } return dfsTraversal; } }; Iterative class Solution { vector<int> dfsTraversal; void dfsHelper(int i, vector<bool> &visited, vector<int> adj[]) { stack<int> st; visited[i] = true; st.
Read more →

Detect cycle in directed graph using BFS/DFS

https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ Using DFS class Solution { bool dfsHelper(int i, vector<bool> &visited, vector<bool> &visitedDirected, vector<int> adj[]) { visited[i] = true; visitedDirected[i] = true; for (int it : adj[i]) { if (!visited[it]) { if (dfsHelper(it, visited, visitedDirected, adj)) { return true; } } else if (visitedDirected[it]) { return true; } } visitedDirected[i] = false; return false; } public: bool isCyclic(int V, vector<int> adj[]) { vector<bool> visited(V, false); vector<bool> visitedDirected(V, false); for (int i = 0; i < V; i++) { if (!
Read more →

Detect cycle in undirected graph using BFS/DFS

https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1 DFS class Solution { bool dfsHelper(int i, int p, vector<bool> &visited, vector<int> adj[]) { visited[i] = true; for (auto it : adj[i]) { if (visited[it] == false) { if (dfsHelper(it, i, visited, adj)) { return true; } } else if (it != p) { return true; } } return false; } public: bool isCycle(int V, vector<int> adj[]) { vector<bool> visited(V, false); for (int i = 0; i < V; i++) { if (!
Read more →

Minimum steps by knight

https://practice.geeksforgeeks.org/problems/steps-by-knight/0 class pos { public: int x, y, dist; pos(int x, int y, int dist) : x(x), y(y), dist(dist) {} }; class Solution { bool isInside(int x, int y, int N) { return (x >= 1 and x <= N and y >= 1 and y <= N); } public: int minStepToReachTarget(vector<int> &KnightPos, vector<int> &TargetPos, int N) { vector<pair<int, int>> dir = { {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, }; bool visited[N + 1][N + 1] = {0}; queue<pos> q; q.
Read more →

Implement topological sort

https://practice.geeksforgeeks.org/problems/topological-sort/1 Topological sort is only valid for a Directed Acyclic Graph Using DFS class Solution { stack<int> st; void dfsHelper(int i, vector<bool> &visited, vector<int> adj[]) { visited[i] = true; for (auto it : adj[i]) { if (!visited[it]) { visited[it] = true; dfsHelper(it, visited, adj); } } st.push(i); } public: vector<int> topoSort(int V, vector<int> adj[]) { vector<bool> visited(V, false); for (int i = 0; i < V; i++) { if (!
Read more →

Check if graph is bipartite

https://www.geeksforgeeks.org/bipartite-graph/ Color the graph by BFS traversal, colors maintains track of visited nodes. colors[it] = 1 - colors[node] is the fun alternator part Using BFS class Solution { bool bfsHelper(int i, vector<int> &colors, vector<int> adj[]) { queue<int> q; colors[i] = 1; q.push(i); while (!q.empty()) { int node = q.front(); q.pop(); for (int it : adj[node]) { if (colors[it] == -1) { colors[it] = 1 - colors[node]; q.push(it); } else if (colors[it] == colors[node]) { return false; } } } return true; } public: bool isBipartite(int V, vector<int> adj[]) { vector<int> colors(V, -1); for (int i = 0; i < V; i++) { if (colors[i] == -1) { if (!
Read more →

Coin change

Read more →

Knapsack

Read more →

Painting the fence

Read more →

Maximize the cut segments

https://practice.geeksforgeeks.org/problems/cutted-segments/0 class Solution { int dp[10005]; int solve(int x, int a, int b, int c) { if (dp[x] != -1) return dp[x]; if (x < min({a, b, c})) return dp[x] = INT_MIN; int n1 = (x >= a) ? solve(x - a, a, b, c) + 1 : INT_MIN; int n2 = (x >= b) ? solve(x - b, a, b, c) + 1 : INT_MIN; int n3 = (x >= c) ?
Read more →

Longest common subsequence

https://practice.geeksforgeeks.org/problems/longest-common-subsequence/0 Iterative class Solution { int dp[1005][1005]; public: int lcs(int x, int y, string s1, string s2) { for (int i = 0; i <= x; i++) { for (int j = 0; j <= y; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[x][y]; } }; Recursive
Read more →

Longest repeated subsequence

Read more →

Longest increasing subsequence

Read more →

Longest common substring

Read more →

Unbounded knapsack

Read more →

Longest palindromic subsequence

Read more →

Count set bits in an integer

Read more →