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.
Tag: 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.
Insertion in a BST – Iterative and Recursive Solution
A Binary Search Tree (BST) is a rooted binary tree, whose nodes each store a key (and optionally, an associated value), and each has two distinguished subtrees, commonly denoted left and right.
Inorder Tree Traversal – Iterative and Recursive
Given a binary tree, write an iterative and recursive solution to traverse the tree using inorder traversal in C++, Java, and Python.
Preorder Tree Traversal – Iterative and Recursive
Given a binary tree, write an iterative and recursive solution to traverse the tree using preorder traversal in C++, Java, and Python.
Postorder Tree Traversal – Iterative and Recursive
Given a binary tree, write an iterative and recursive solution to traverse the tree using postorder traversal in C++, Java, and Python.