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

# Month: July 2020

## 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