Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: … Continue reading Trapping Rain Water

Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. Example: Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6 Solution C# Program public class Solution { public int MaximalRectangle(char[][] matrix) { if(matrix == null || matrix.Length == 0) return 0; int row = … Continue reading Maximal Rectangle

The Coin Change Problem – Hackerrank Solution

For Problem Statement refer: https://www.hackerrank.com/challenges/coin-change/problem Solution public static long getWays(int n, List<Long> c) { // Write your code here long[] dp = new long[n+1]; dp[0] = 1; for(int i=0;i<c.size();i++) { int coin = c.get(i).intValue(); for(int j=1;j<=n;j++) { if(j >= coin) { dp[j] = dp[j] + dp[j-coin]; } } } return dp[n]; } Code Explanation Refer: … Continue reading The Coin Change Problem – Hackerrank Solution

Encryption – Hackerrank

Problem Statement Refer to: https://www.hackerrank.com/challenges/encryption/problem Solution - Java Program static String encryption(String s) { int len = s.length(); int row = (int)Math.floor(Math.sqrt(len)); int col = (int)Math.ceil(Math.sqrt(len)); if(row * col < len) row = col; String res = ""; for(int i=0;i<col;i++) { for(int j=i;j<len;j = j+col) { res += s.charAt(j); } res += " "; } … Continue reading Encryption – Hackerrank

Huffman Decoding – Hackerrank

Problem Statement Refer: https://www.hackerrank.com/challenges/tree-huffman-decoding/problem Solution void decode(String s, Node root) { StringBuilder sb = new StringBuilder(); Node c = root; for(int i=0;i<s.length();i++) { c = s.charAt(i) == '1' ? c.right : c.left; if(c.left == null && c.right == null) { sb.append(c.data); c = root; } } System.out.println(sb); }

Minimum Jumps – Dynamic Programming

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Print the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element. Input Format n, size … Continue reading Minimum Jumps – Dynamic Programming

Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2. The … Continue reading Container With Most Water

Count Subsequences

Given a string, count the number of distinct subsequences of it ( including empty subsequence ). For the uninformed, A subsequence of a string is a new string which is formed from the original string by deleting some of the characters without disturbing the relative positions of the remaining characters. For example, "AGH" is a … Continue reading Count Subsequences

Max Sum K – Partition

Agarwal has a habit of creating Ajeeb Samasya as usual and Shubham always comes to his rescue. This is time he has created another samasya which is as follows. Read carefully! Shubham has an array of N integers and an integer K. He wants to create a subsequence of this array with some conditions applied. … Continue reading Max Sum K – Partition

Containers in STL – C++

1) Sequential Containers It implements data structure which can be accessed in a sequential manner. vectorlistdequearraysforward_list 2) Container Adaptors It provides a different interface for sequential containers. queuepriority_queuestack 3) Associative Containers It implements sorted data structures that can be quickly searched(O(logn) time complexity. setmultisetmapmultimap 4) Unordered Associative Containers It implements unordered data structure that can … Continue reading Containers in STL – C++

Find Merge Point of Two Lists

Given pointers to the head nodes of  2 linked lists that merge together at some point, find the Node where the two lists merge. It is guaranteed that the two head Nodes will be different, and neither will be NULL. In the diagram below, the two lists converge at Node x: [List #1] a--->b--->c \ x--->y--->z--->NULL / … Continue reading Find Merge Point of Two Lists

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit. Example: Input: [2,1,5,6,2,3] Output: … Continue reading Largest Rectangle in Histogram

Best Time to Buy and Sell Stock – Easy Problem

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you … Continue reading Best Time to Buy and Sell Stock – Easy Problem

Binary Search STL

In this program, we will see, how to find an element in the sorted array. #include <iostream> #include <algorithm> using namespace std; int main() { int arr[] = {10, 20, 30, 40, 50, 60, 100, 100}; int n = sizeof(arr) / sizeof(int); //Search -- Key int key; cout << "Enter the Key" << endl; cin … Continue reading Binary Search STL

Palindromic Queries

Given a string s and m queries . Each query consists of (l,r) where 1 <= l <= r <= n(size of string). You need to print whether l to r is a palindromic string or not. A string can be called palindrome if its reverse is same as itself . Ex - "aba" .Input … Continue reading Palindromic Queries

Search an element in array using find() function

C++ Program #include <iostream> #include <algorithm> using namespace std; int main() { int arr[] = {1, 11, 10, 9, 100}; int n = sizeof(arr) / sizeof(int); //Search -- Key int key; cout << "Enter the Key" << endl; cin >> key; auto itr = find(arr, arr + n, key); int index = itr - arr; … Continue reading Search an element in array using find() function

Sorting in C++

#include <iostream> #include <algorithm> #include <string> using namespace std; bool compare(string s1, string s2) { if (s1.length() == s2.length()) return s1 < s2; return s1.length() > s2.length(); } int main() { int n; cout << "Enter the number" << endl; cin >> n; cin.get(); string s[100]; for (int i = 0; i < n; i++) … Continue reading Sorting in C++

Count the number of all possible binary strings without consecutive 1’s

You are provided an integers N. You need to count all possible distinct binary strings of length N such that there are no consecutive 1’s.Input Format First line contains integer t which is number of test case. For each test case, it contains an integer n which is the the length of Binary String.Constraints 1<=t<=100 … Continue reading Count the number of all possible binary strings without consecutive 1’s

String class : C++

#include <iostream> #include <string> using namespace std; int main() { //string intialization string s0; string s1("Mei"); string s2 = "Meikandanathan"; string s3(s1); string s4 = s2; char arr[] = {'a', 'b', 'c', '\0'}; string s5(arr); cout << s0 << endl; cout << s1 << endl; cout << s2 << endl; cout << s3 << endl; … Continue reading String class : C++

Rotate Function

Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow: F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]. Calculate the maximum value of F(0), F(1), ..., F(n-1). Note:n is guaranteed to be less than 105. … Continue reading Rotate Function

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dictionary may be reused multiple times in the segmentation.You may assume the dictionary does not contain duplicate words. Example 1: Input: s = "leetcode", wordDict = ["leet", "code"] … Continue reading Word Break

Unique Binary Search Trees : Catalan Numbers

Count no of BST's that can be formed using N nodes numbered from 1,2,3,....n. Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 … Continue reading Unique Binary Search Trees : Catalan Numbers

Lexicographical Numbers : Beauty of DFS

Given an integer n, return 1 - n in lexicographical order. For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9]. Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000. See the beauty of DFS Solution import java.util.*; public class Main { public static void main(String args[]) { // Your Code Here … Continue reading Lexicographical Numbers : Beauty of DFS

Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1: Input: coins = [1, 2, 5], … Continue reading Coin Change

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums = [5,7,7,8,8,10], … Continue reading Find First and Last Position of Element in Sorted Array

4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range … Continue reading 4Sum II

Path In Zigzag Labelled Binary Tree

In an infinite binary tree where every node has two children, the nodes are labelled in row order. In the odd numbered rows (ie., the first, third, fifth,...), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,...), the labelling is right to left. Given the label of a node in this … Continue reading Path In Zigzag Labelled Binary Tree

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [   1->4->5,   1->3->4,   2->6 ] Output: 1->1->2->3->4->4->5->6 Solution Java Program Implementation /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { … Continue reading Merge k Sorted Lists

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] Solution C# … Continue reading 3Sum

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. … Continue reading Climbing Stairs

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval … Continue reading Insert Interval

Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones. Example 1: Input: matrix = [   [0,1,1,1],   [1,1,1,1],   [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares … Continue reading Count Square Submatrices with All Ones

Insert Delete GetRandom O(1)

Hi Geeks! In this article, we going to see about how to insert, delete and get random elements with O(1) Time Complexity. Design a data structure that supports all following operations in average O(1) time. insert(val): Inserts an item val to the set if not already present.remove(val): Removes an item val from the set if present.getRandom: Returns a … Continue reading Insert Delete GetRandom O(1)

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note: There may be more than one LIS combination, it is only necessary for you to return the length.Your algorithm should run in O(n2) complexity. … Continue reading Longest Increasing Subsequence

Minimum Edit Distance

Hi geeks! In this article, we going to see about Minimum Edit Distance problem with Dynamic Programming Approach. Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a characterDelete a characterReplace a character Example 1: Input: word1 = "horse", word2 = … Continue reading Minimum Edit Distance

Maximal Square

Hi Geeks! In this article, we going to see about Maximal Square Problem. Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 … Continue reading Maximal Square

Find the Town Judge

In a town, there are N people labelled from 1 to N.  There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody.Everybody (except for the town judge) trusts the town judge.There is exactly one person that satisfies properties 1 and 2. You are given trust, an array … Continue reading Find the Town Judge

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k. Example 1: Input: nums = [1,2,3,1], k = 3 Output: true Example 2: Input: nums = [1,0,1,1], k = 1 Output: true Example 3: Input: nums = [1,2,3,1,2,3], k … Continue reading Contains Duplicate II

Check If It Is a Straight Line

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane. Example 1: Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true Example 2: Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false Constraints: 2 <= coordinates.length <= 1000coordinates[i].length == 2-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4coordinates contains no duplicate point. … Continue reading Check If It Is a Straight Line

Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1. Two nodes of a binary tree are cousins if they have the same depth, but have different parents. We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree. Return true if and only … Continue reading Cousins in Binary Tree

MongoDb with C# – CRUD Operations Part 1

In this article we going to see about all important commands in mongodb with c# driver. I'm going to demonstrate a CRUD operations on MongoDb with C#, so it helps you to understand better. Create a Sample Project in Visual Studio Here I have created a project with namespace MongoDbEssentials. To use MongoDb in Visual … Continue reading MongoDb with C# – CRUD Operations Part 1

Diagonal Traverse II

Hi Geeks ! Welcome to 100 days of Leetcode challenge. Day 57 of 100 Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images. Example 1: Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] Example 2: Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16] Example 3: Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] Output: … Continue reading Diagonal Traverse II

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to … Continue reading First Bad Version

First Unique Number

You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the FirstUnique class: FirstUnique(int[] nums) Initializes the object with the numbers in the queue.int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.void add(int value) insert value to the queue. Example 1: Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] … Continue reading First Unique Number

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with … Continue reading Longest Substring Without Repeating Characters

Callback functions in JavaScript

Hi friends! In this article we going to learn about Callback functions in JavaScript with several examples. Callback functions is also called higher order functions. In JavaScript functions are called as first class objects. We can pass object to function as an argument.We can also pass other functions into function as an argument, to execute … Continue reading Callback functions in JavaScript

Find the Duplicate Number (Hare and Tortoise)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: You must not modify the array (assume the array is read … Continue reading Find the Duplicate Number (Hare and Tortoise)

Binary Search Tree Iterator

Hi Geeks! Welcome to 100 Days of Leetcode Programming challenge. Day 53 : Binary Search Tree Iterator In this article, we going to see about Binary Search Tree Iterator. Let's see the given problem. Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. … Continue reading Binary Search Tree Iterator

Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules: Any left parenthesis '(' must have a corresponding right parenthesis ')'.Any right parenthesis ')' must have a corresponding left parenthesis '('.Left parenthesis '(' must go before the corresponding right parenthesis ')'.'*' could … Continue reading Valid Parenthesis String

Validate Stack Sequences

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack. Example 1: Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true Explanation: We might do the following sequence: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> … Continue reading Validate Stack Sequences