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

# Category: Programming

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

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

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

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

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

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

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

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

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

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

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