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

# Category: Leetcode

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

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

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

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

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

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

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

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

## C# Program to find Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its minimum depth = … Continue reading C# Program to find Minimum Depth of Binary Tree

## Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place. Example 1: Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ] Example 2: Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], … Continue reading Set Matrix Zeroes

## Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string. Example 1: Input: "hello" Output: "holle" Example 2: Input: "leetcode" Output: "leotcede" Solution public class Solution { public string ReverseVowels(string s) { string vowel = "aeiouAEIOU"; int left = 0, right = s.Length-1; char[] c = s.ToCharArray(); while(left … Continue reading Reverse Vowels of a String

## Sum of Left Leaves Iterative and Recursive Approach

Find the sum of all left leaves in a given binary tree. Example: 3 / \ 9 20 / \ 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24. Solution DFS Approach - Recursive /** * Definition for a binary tree node. * public class … Continue reading Sum of Left Leaves Iterative and Recursive Approach

## Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]: direction can be 0 (for left shift) or 1 (for right shift). amount is the amount by which string s is to be shifted.A left shift by 1 means remove the first character of s and append it to the end.Similarly, a right shift by 1 means remove the last character … Continue reading Perform String Shifts

## Sum Root to Leaf Numbers

Hi Geeks! Welcome to 100 Days of Leetcode Programming Challenge. Day 46 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. Note: A leaf is a node with no children. Example: Input: [1,2,3] 1 … Continue reading Sum Root to Leaf Numbers

## Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Leetcode 12th Day Challenge. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, … Continue reading Contiguous Array

## Convert Sorted Array to Binary Search Tree

Hi Geeks! Welcome to 100 Days of Leetcode Challenge. In this article, we going to see about how to Convert Sorted Array to Binary Search Tree. Day 45 of 100 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined … Continue reading Convert Sorted Array to Binary Search Tree

## Find Bottom Left Tree Value

Hi Geeks! Welcome to 100 Days of Leetcode Challenge. In this article, we going to see about how to find the bottom left tree value. Day 44 of 100 Given a binary tree, find the leftmost value in the last row of the tree. Example 1: Input: 2 / \ 1 3 Output: 1 Example … Continue reading Find Bottom Left Tree Value

## How to Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key.The right subtree of a node contains only nodes with keys greater than the node's key.Both the left and right subtrees must also … Continue reading How to Validate Binary Search Tree

## How to find the Height and Diameter of the Binary Tree

Hi friends, in this article, we going to see about how to find the height and diameter of Binary Tree. Height of Binary Tree Before finding the diameter of Binary Tree, we must have basic knowledge of how to find the Height of binary tree. Look at the below problem to find the Height(Maximum Depth) … Continue reading How to find the Height and Diameter of the Binary Tree

## Binary Search Tree : Insertion

You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a … Continue reading Binary Search Tree : Insertion

## Min Stack

Hi Geeks. Welcome to 100 Days of Leetcode challenge. Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack.pop() -- Removes the element on top of the stack.top() -- Get the top element.getMin() -- Retrieve the minimum element in the stack. Example: … Continue reading Min Stack

## Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 … Continue reading Path Sum II

## Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example:Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Solution Level … Continue reading Binary Tree Zigzag Level Order Traversal

## Binary Tree Paths

Given a binary tree, return all root-to-leaf paths. Note: A leaf is a node with no children. Example: Input: 1 / \ 2 3 \ 5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3 DFS Straight Forward Approach /** * Definition for a binary tree node. * public class TreeNode { * public int … Continue reading Binary Tree Paths

## Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Example: Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- Solution Perform Level Order traversal with simple condition /** * Definition for … Continue reading Binary Tree Right Side View

## Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example:Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] Solution - Easy to understand /** * Definition for a binary tree … Continue reading Binary Tree Level Order Traversal