Trapping Rain Water Problem
Trapping rainwater problem: Find the maximum amount of water that can be trapped within a given set of bars where each bar’s width is 1 unit.
Tag: Algorithm
std::prev_permutation | Overview and Implementation in C++
This post discusses std::prev_permutation, which can be used to find the lexicographically smaller permutations of a string.
Merging Overlapping Intervals
Given a set of intervals, print all non-overlapping intervals after merging the overlapping intervals.
Maximum Sum Circular Subarray
Given a circular integer array, find a subarray with the largest sum in it.
Maximum Sum Subarray Problem (Kadane’s Algorithm)
Given an integer array, find a contiguous subarray within it that has the largest sum using Kadane’s algorithm.
Longest Bitonic Subarray Problem
The Longest Bitonic Subarray (LBS) problem is to find a subarray of a given sequence in which the subarray’s elements are first sorted in increasing order, then in decreasing order, and the subarray is as long as possible.
std::next_permutation | Overview and Implementation in C++
This post discusses std::next_permutation, which can be used to find the lexicographically greater permutations of a string.
Find majority element (Boyer–Moore Majority Vote Algorithm)
Given an integer array containing duplicates, return the majority element if present. A majority element appears more than n/2 times, where n is the array size.
Shuffle an array using Fisher–Yates shuffle algorithm
Given an integer array, in-place shuffle it. The algorithm should produce an unbiased permutation, i.e., every permutation is equally likely.
Sort an array of 0’s, 1’s, and 2’s (Dutch National Flag Problem)
Given an array containing only 0’s, 1’s, and 2’s, sort it in linear time and using constant space.
Deletion from BST (Binary Search Tree)
Deletion from BST – write an efficient function to delete a given key in BST. To delete a node from BST, there are three possible cases to consider.
Search a given key in BST – Iterative and Recursive Solution
Given a BST, write an efficient function to search a given key in it. The algorithm should return the parent node of the key and print if the key is the left or right node of the parent node. If the key is not present in the BST, the algorithm should be able to determine that.