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.

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.

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.

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.

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.

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) ?

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.

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].