Ternary Search vs Binary search
In this article, we will implement a ternary search algorithm and compare its performance with binary search algorithm.
Tag: Algorithm
Implementation of KMP Algorithm – C, C++, Java, and Python
The KMP Algorithm (or Knuth, Morris, and Pratt string searching algorithm) cleverly uses the previous comparison data. It can search for a pattern in linear time as it never re-compares a text symbol that has matched a pattern symbol.
Longest Common Subsequence of k–sequences
The Longest Common Subsequence (LCS) problem is finding the longest subsequence present in given two sequences in the same order, i.e., find the longest sequence which can be obtained from the first original sequence by deleting some items and from the second original sequence by deleting other items.
Huffman Coding Compression Algorithm
Huffman coding (also known as Huffman Encoding) is an algorithm for doing data compression, and it forms the basic idea behind file compression. This post talks about the fixed-length and variable-length encoding, uniquely decodable codes, prefix rules, and Huffman Tree construction.
Wildcard Pattern Matching
Given a string and a pattern containing wildcard characters, i.e., * and ?’, where ? can match to any single character in the string and * can match to any number of characters including zero characters, design an efficient algorithm to find if the pattern matches with the complete string or not.
Longest Increasing Subsequence using LCS
The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique.
Maximum Product Subarray Problem
Given an integer array, find the maximum product subarray. In other words, find a subarray that has the maximum product of its elements.
Longest Increasing Subsequence Problem
The Longest Increasing Subsequence (LIS) problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique.
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.
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.