Greedy: Remove overlapping intervals.
Problem Statement: You are given an array of intervals [start, end]. You need to return minimum number of intervals to remove to make the rest of the intervals non-overlapping Example Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 You need to remove [1,3] to make rest of the intervals non overlapping Solution We follow greedy approach as […]
Greedy: Check if the string is a substring of another string
Problem Statement: You are given 2 strings s, t. You need to check if s is a substring of t. A substring of a string is a new string that is formed by deleting some of the character without disturbing the relative position. Example Input: s = “abc”, t = “aerbrtcsd” Output: true Solution We […]
Greedy: Get the minimum platforms needed to avoid delay in the train arrival.
Problem Statement: You are given an array of arrival and departure timings for train at a station. You need to find the minimum umber of platforms required such that no train waits. Example arrival[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00} departure[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} Output: 3 This is because, in […]
Greedy: Remove k digits from an number to make it a smallest integer.
Problem Statement: You are given a number and integer k. You need to remove k digits from the number and it should return the smallest integer possible. Example Input: num = “10300”, k = 1 Output: “300” Here if you remove the leading “1”, the o/p will be the smallest integer possible. Solution Here we […]
Greedy: Add elements in an array so the sum is equal to the given range
Problem Statement: You are given sorted array, and an integer K. You need to add elements in such a way that any number in the range [1, k] inclusive can be formed by the sum of the some of the elements in the array. You need to return the minimum number of patches required Example […]
Greedy: Remove duplicates from a string
Problem Statement: You are given a string s, you need to remove duplicate letters so that every letter should appear only once. The result should be in smallest lexicographical order Example Input: s = “bcabcccdd” Output: “abcd” Solution The solution is very simple: 1. First we count the frequency of each character. 2. Then we […]
Binary Search Trees: Flatten BST to sorted list
Problem Statement: You are given a root of a binary tree. You need to flatten into a sorted list. Solution We need to do inorder traversal. For that we will create a dummy node. Then we take a pointer ‘prev’ and point it to dummy node. Then we perform in-order traversal as: prev->right = curr […]
Binary Search Trees: Correct a BST where 2 nodes are swapped
Problem Statement: You are given a root node of a binary search tree where 2 nodes are swapped. You need to correct the BST and return it. Solution A simple solution is traverse the BST in in-order store the node values in an array and sort the array. Then insert the array into BST. This […]
Binary Search Trees: Check if the BST has a dead end
Problem Statement: You are given a root node of a BST. You need to check if it has a dead end or not. A dead end is a node, where you will not be able to insert any other nodes after it. BST should contain +ve integers only. Example 8 / \ 5 9 / […]
Binary Search Trees: Check if the pre-order is a valid BST
Problem Statement: You are given an array of integers in pre-order fashion. Then you need to check if it is a valid BST. Solution pre-order means, root element, followed by left sub-tree, followed by right sub-tree. First we will construct a BST from the given sequence. Then we compare the pre-order traversal of the constructed […]