# Amazon Coding Interview Questions  Drishti-Soft Interview Questions

## Array Questions Amazon

Question 1. Slowest Key Leetcode Solution The problem Slowest Key Leetcode Solution provides us with a sequence of keys that have been pressed. We are also given an array or vector of times these keys have been released. The sequence of keys is given in the form of a string. So, the problem asked us to ...

Question 2. 3Sum Leetcode Solution Problem Statement   Given an array 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. Notice: that the solution set must not contain duplicate triplets. Example #1 [-1,0,1,2,-1,4] ...

Question 3. Insert Interval Leetcode Solution The problem Insert Interval Leetcode Solution provides us with a list of some intervals and one separate interval. Then we are told to insert this new interval among the list of intervals. So, the new interval might be intersecting with intervals that are already in the list, or it might ...

Question 4. Combination Sum Leetcode Solution The problem Combination Sum Leetcode Solution provides us an array or list of integers and a target. We are told to find the combinations that can be made using these integers any number of times that add up to the given target. So more formally, we can use the given ...

Question 5. Island Perimeter Leetcode Solution Problem Statement   In this problem, we are given a grid in form of a 2-D array. grid[i][j] = 0 represents there is water at that point and grid[i][j] = 1 represents land. Grid cells are connected vertically/horizontally but not diagonally. There is exactly one island (a connected component of land ...

Question 6. Maximum Subarray Leetcode Solution Problem Statement   Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example nums = [-2,1,-3,4,-1,2,1,-5,4] 6 Explanation: [4,-1,2,1] has the largest sum = 6. nums = [-1] -1 Approach 1 (Divide and Conquer)   In this approach ...

Question 7. Rank Transform of an Array Leetcode Solution The problem Rank Transform of an Array Leetcode Solution provided us with an array of integers. The array or the given sequence is unsorted. We need to assign ranks to each integer in the given sequence. There are some restriction s for assigning the ranks. The ranks must start with ...

Question 8. Decompress Run-Length Encoded List Leetcode Solution The problem Decompress Run-Length Encoded List Leetcode Solution states that you are given an array or vector containing a sequence. The sequence has some specific representation. The input sequence is formed from another sequence. We will call that another sequence as the original sequence. As per which the input sequence ...

Question 9. Replace Elements with Greatest Element on Right Side Leetcode Solution The problem Replace Elements with Greatest Element on Right Side Leetcode Solution provides us with an array or vector of integers. The problem asked us to replace all the elements with the element that is greatest among all the elements on the right side. So consider if we had an ...

Question 10. Find Winner on a Tic Tac Toe Game Leetcode Solution The problem Find Winner on a Tic Tac Toe Game Leetcode Solution asks us to find out the winner of a tic tac toe game. The problem provides us with an array or vector of moves made by the players. We need to go through the moves and judge who ...

Question 11. Find Common Characters Leetcode Solution Problem Statement   In this problem, we are given a list of string. We have to find out the characters that are common in all the strings. If a character is present in all strings in multiple times, then we have to output the character multiple times. Suppose, we have array ...

Question 12. Minimum Time Visiting All Points Leetcode Solution The problem Minimum Time Visiting All Points Leetcode Solution provides us with an array or vector of points on coordinate axes. The problem after providing us with the input asks us to find the minimum time to visit all the points given in the input. When you move one unit ...

Question 13. Find N Unique Integers Sum up to Zero Leetcode Solution The problem Find N Unique Integers Sum up to Zero Leetcode Solution, provides us with an integer. It asks us to return n unique integers that sum up to 0. So, the question is pretty simple to understand. So, before diving into the solution. Let us take a look at ...

Question 14. Partition Array Into Three Parts With Equal Sum Leetcode Solution The problem Partition Array Into Three Parts With Equal Sum Leetcode Solution provides us with an array or vector and asks if there are three partitions possible of the sequence. Here, by partition we mean that is there two indices i, j such that the sum of elements from start ...

Question 15. Find Common Characters Leetcode Solution Problem Statement   In this problem, we are given an array of strings. We need to print a list of all characters that appear in every string in the array(duplicates included). That is if a character appears 2 times in every string, but not 3 times, we need to have it ...

Question 16. Find All Numbers Disappeared in an Array Leetcode Solution Problem Statement   In this problem, we are given an array of integers. It contains elements ranging from 1 to N, where N = size of the array. However, there are some elements that have disappeared and some duplicates are present in their place. Our goal is to return an array ...

Question 17. Majority Element II Leetcode Solution In this problem, we are given an array of integers. The goal is to find all the elements which occur more than ⌊N / 3⌋ time in the array where N = size of the array and ⌊ ⌋ is the floor operator. We need to return an array of ...

Question 18. Contains Duplicate II Leetcode Solution Problem Statement   In this problem we are given an array of integers and we have to check if there exists any duplicate element which are at a distance of at least k to each other. i.e. the difference between the indices of those two same element should be less than ...

Question 19. Relative Sort Array Leetcode Solution In this problem, we are given two arrays of positive integers. All elements of the second array are distinct and are present in the first array. However, the first array can contain duplicate elements or elements that are not in the second array. We need to sort the first array ...

Question 20. Find Words That Can Be Formed by Characters Leetcode Solution Problem statement   In the problem ” Find Words That Can Be Formed by Characters” we are given an array of strings that consists of lower case English alphabets (words) and a string that consists of a set of characters (chars). Our task is to check for each string in the array ...

Question 21. Number of Equivalent Domino Pairs Leetcode Solution Problem statement   In the problem ” Number of Equivalent Domino Pairs,”  we are given a list of dominoes where each domino consists of two values like dominoes[i]=[a,b]. Two dominoes, dominoes[i] =[a,b] and dominoes[j]=[c,d]  are equivalent if (a==c and b==d) or (a==d and c==d). Our task is to find out the ...

Question 22. Pascal’s Triangle II Leetcode Solution Problem Statement   In this problem we have been given Row index(i) of the Pascal Triangle. We have to create a linear array containing the values of the ith row and return it. Row index starts from 0. We know that Pascal’s triangle is a triangle where each number is the ...

Question 23. Unique Paths Leetcode Solution The problem Unique Paths Leetcode Solution states that you are given two integers representing the size of a grid. Using the size of the grid, the length, and breadth of the grid. We need to find the number of unique paths from the top left corner of the grid to ...

Question 24. Number of Good Pairs Leetcode Solution Problem Statement   In this problem an array of integers is given and we have to find out the count of total number of good pairs (a[i], a[j]) where a[i]=a[j]. Example nums = [1,2,3,1,1,3] 4 Explanation:   There are 4 good pairs at indices (0,3), (0,4), (3,4), (2,5) . [1,1,1,1] 6 Explanation:  ...

Question 25. Third Maximum Number Leetcode Solution As the title says, the goal is to find the third maximum integer in a given array of integers. Note that we need to find the distinct third maximum integer in the array. We return the maximum integer in the array when it has no distinct third maximum integer. Example   ...

Question 26. Balanced Binary Tree Leetcode Solution A binary tree is Height-balanced if the difference of heights of left and right subtree of every node in the tree is at most 1. In this problem, we are going to check for a balanced binary tree. Example   2 / 1 / 4 Not balanced 1 / \ 2 ...

Question 27. How Many Numbers Are Smaller Than the Current Number Leetcode Solution Problem Statement   In this problem, we are given an array. For each element of this array, we have to find out the number of elements smaller than that element. i.e. for each i (0<=i<arr.length) we have to find out count of elements less than the number arr[i]. For that we ...

Question 28. Merge Sorted Arrays Leetcode Solution In the problem “Merge Sorted Arrays”, we are given two arrays sorted in non-descending order. The first array is not fully filled and has enough space to accommodate all elements of the second array as well. We have to merge the two arrays, such that the first array contains elements ...

Question 29. Search in Rotated Sorted Array Leetcode Solution Consider a sorted array but one index was picked and the array was rotated at that point. Now, once the array has been rotated you are required to find a particular target element and return its index. In case, the element is not present, return -1. The problem is generally ...

Question 30. Search Insert Position Leetcode Solution In this problem, we are given a sorted array and a target integer. We have to find its Search Insert Position. If the target value is present in the array, return its index. Return the index at which the target should be inserted so as to keep the order sorted(in ...

Question 31. Kids With the Greatest Number of Candies Leetcode Solution In the problem “Kids With the Greatest Number of Candies”, we are given an array of integers that represents the number of chocolates some children have got and some extra candies that can be distributed in any manner. Now, we need to find: Can every child have the greatest number ...

Question 32. Running Sum of 1d Array Leetcode Solution Problem Statement   In running sum of 1d array problem we have been given an array nums for which we have to return an array where for each index i in the result array  arr[i] = sum( nums … nums[i] ). Example  nums = [1,2,3,4] [1,3,6,10] Explanation: Running sum is :  ...

Question 33. Plus One Leetcode Solution Problem statement   In the problem ” Plus One”  we are given an array where each element in the array represents a digit of a number. The complete array represents a number. The zeroth index represents the MSB of the number.  We can assume that there is no leading zero in ...

Question 34. Kth largest element in an Array Leetcode Solutions In this problem, we have to return the kth largest element in an unsorted array. Note that the array can have duplicates. So, we have to find the Kth largest element in the sorted order, not the distinct Kth largest element. Example   A = {4 , 2 , 5 , 3 ...

Question 35. Max Consecutive Ones Leetcode Solution Problem Statement   In Max Consecutive Ones problem a binary array is given. We have to find the maximum number of consecutive ones present in the given array. The input array will only contain 0 and 1. Example [1,1,0,1,1,1] 3 Explanation: The first two digits or the last three digits are ...

Question 36. Rearrange Array such that arr[i] >= arr[j] if i is even and arr[i] <= arr[j] if i is odd and j < i Suppose you have an integer array. The problem statement asks to rearrange the array in such a way that the elements at even position in an array should be greater than all elements before it and the elements at odd positions should be less than the elements before it. Example   ...

Question 37. Sort Array By Parity II Leetcode Solution Problem statement   In the problem ” Sort Array By Parity II,” we are given a parity array where all the elements are positive integers. The array contains an even number of elements. The array contains an equal number of even and odd elements. Our task is to rearrange the elements ...

Question 38. Count pair with Given Sum In problem “count pair with given sum” we have given an integer array[] and another number say ‘sum’, you have to determine whether any of the two elements in a given array has a sum equal to “sum”. Example   Input: arr []={1,3,4,6,7} and sum = 9. Output: “ Elements found ...

Question 39. Group Multiple Occurrence of Array Elements Ordered by first Occurrence You are given a question in which you have given an unsorted array with multiple occurrences of numbers. The task is to group all the multiple occurrences of array elements ordered by first occurrence. Meanwhile, the order should be the same as the number comes. Example   Input: [ 2, 3,4,3,1,3,2,4] ...

Question 40. Maximum difference between frequency of two elements such that element having greater frequency is also greater Suppose, you have an integer array. The problem statement asks to find out the maximum difference between the frequency of any two distinct elements of a given array, but the element with the greater frequency should also be greater in value than the other integer. Example   Input: arr[] = {2,4,4,4,3,2} ...

Question 41. Maximize Sum of Array after K Negations Leetcode Solution This post is on Maximize Sum Of Array After K Negations Leetcode Solution Problem statement   In the problem ” Maximize Sum Of Array After K Negations” we are given an array arr and a value K. The array consists of integer values. We can change the value of arr[i] to ...

Question 42. Smallest Subarray with k Distinct Numbers Suppose, you have an integer array and a number k. The problem statement asks to find out the smallest sub-array of range (l, r) inclusively, in such a way there are exactly k distinct numbers present in that smallest sub-array. Example   Input: {1, 2, 2, 3, 4, 5, 5} k=3 ...

Question 43. All Unique Triplets that Sum up to a Given Value We have given an array of integers and a given number called ‘sum’. The problem statement asks to find out the triplet that adds up to the given number ‘sum’. Example   Input: arr[] = {3,5,7,5,6,1} sum=16 Output: (3, 7, 6), (5, 5, 6) Explanation: Triplet which equals to the given ...

Question 44. Longest Subarray Having Count of 1s One More than Count of 0s We have given an array of integers. An array contains 1’s and 0’s only. The problem statement asks to find out the length of the longest Sub-Array which having the quantity of 1’s digit is just one more than the count of 0’s in a sub-array. Example   Input: arr[] = ...

Question 45. Maximum Array from Two given Arrays Keeping Order Same Suppose we have two integers array of same size n. Both of the arrays can contain common numbers as well. The problem statement asks to form the resultant array that contains the ‘n’ maximum values from both of the arrays. The first array should be prioritized (elements of the first ...

Question 46. Guess Number Higher or Lower II Problem Statement   “Guess Number Higher or Lower II” states that we are going to play a game that is called Guess Game. The game says that I pick a number from 1 to n. Whenever you guess the number which I have not picked, I m going to say you ...

Question 47. Rearrange an Array Such that arr[i] is equal to i “Rearrange an array such that arr[i]=i”  problem states that you are given an array of integers ranging from 0 to n-1. Since all the elements may not be present in the array, then in place of them -1 is there. The problem statement asks to rearrange the array in such ...

Question 48. Segregate 0s and 1s in an Array Problem Statement   Suppose you have an integer array. The problem “Segregate 0s and 1s in an array” asks to segregate the array in two parts, in 0s and in 1s. The 0’s should be on the left side of the array and 1’s on the right side of the array. ...

Question 49. Find Largest d in Array such that a + b + c = d Problem Statement   Suppose you have an array of integers. Input values are all distinct elements. The problem “Find largest d in array such that a + b + c = d” asks to find out the largest element ‘d’ in the set such that a + b + c = ...

Question 50. Maximum Number of Chocolates to be Distributed Equally Among k Students “The maximum number of chocolates to be distributed equally among k students” states that you are given n boxes that have some chocolates in it. Suppose there are k students. The task is to distribute the maximum number of chocolates among k students equally, by selecting consecutive boxes. We can ...

Question 51. Maximum Consecutive Numbers Present in an Array Problem Statement   Suppose you have an array of integers of size N. The problem “Maximum consecutive numbers present in an array” asks to find out the maximum count of consecutive numbers that could be scattered in an array. Example   arr[] = {2, 24, 30, 26, 99, 25} 3 Explanation: The ...

Question 52. Queries for Number of Distinct Elements in a Subarray We have given an array of integer and a number of queries and we have to find out the number of all the distinct elements we have within the given range, the query consists of two numbers left and right, this is the given range, with this given range we ...

Question 53. Range Minimum Query (Square Root Decomposition and Sparse Table) In the range minimum query problem we have given a query and an integer array. Each query contains the range as left and right indexes for each range. The given task is to determine the minimum of all number that lies within the range. Example   Input: arr[] = {2, 5, ...

Question 54. Range Sum Query using Sparse Table In the range sum query using sparse table problem we have a range query and given an integer array. The given task is to find out the sum of all integers that comes in the range. Example   Input: arr[] = {1,4,6,8,2,5} Query: {(0, 3), (2, 4), (1, 5)} Output: 19 16 25 ...

Question 55. Count and Toggle Queries on a Binary Array An array of size n has been given as an input value. The problem “Count and Toggle Queries on a Binary Array” asks to perform some of the queries which are given below, queries can vary in a random manner. The queries are ⇒ Toggle query ⇒ toggle(starting, ending), this ...

Question 56. Queries for Decimal Values of Subarrays of a Binary Array Write Queries for decimal values of subarrays of a binary array in a given binary array. The problem statement asks to find out the decimal number so formed with the help of range in a binary array. Example   Input: arr[] = {1, 0, 1, 1, 0, 0, 1, 1} Query(1, ...

Question 57. Maximize Elements Using Another Array Suppose, we have given two integers array of same size n. Both of the arrays contain positive numbers. The problem statement asks to maximize the first array by using the second array element keeping the second array as a priority (elements of the second array should appear first in output). ...

Question 58. Minimum swaps required to bring all elements less than or equal to k together The problem “Minimum swaps required to bring all elements less than or equal to k together” states that you have an integer array. The problem statement asks to find out the smallest count of swaps that will be required to get the elements together which are less than or equal ...

Question 59. Find First and Last Position of Element in Sorted Array Leetcode Solution Problem statement   In this article titled “Find First and Last Position of Element in Sorted Array Leetcode Solution,” we will discuss the solution to a leetcode problem. In the given problem we are given an array. We are also given a target element. Elements in the array are sequenced in ...

Question 60. Monotonic Array LeetCode Solution Problem statement   In the problem “Monotonic Array” we are given an array. Our task is to check if the array is a monotonic array or not. A monotonic array is an array where elements are either sorted in increasing order or in decreasing order. If the array is sorted in ...

Question 61. Maximum subsequence sum such that no three are consecutive The problem “Maximum subsequence sum such that no three are consecutive ” states that you are given an array of integers. Now you need to find a subsequence that has the maximum sum given that you cannot consider three consecutive elements. To recall, a subsequence is nothing but an array ...

Question 62. Find duplicates in a given array when elements are not limited to a range The problem “Find duplicates in a given array when elements are not limited to a range” states that you have an array consisting of n integers. The problem statement it to find out the duplicate elements if present in the array. If no such element exists return -1. Example   [ ...

Question 63. Check if Array Contains Contiguous Integers With Duplicates Allowed You are given an array of integers which can contain duplicate elements as well. The problem statement asks to find out if it is a set of contiguous integers, print “Yes” if it is, print “No” if it is not. Example   Sample Input: [2, 3, 4, 1, 7, 9] Sample ...

Question 64. The K Weakest Rows in a Matrix Leetcode Solution Problem statement   In the problem ” The K Weakest Rows in a Matrix” we are given a matrix of n rows and m columns. matrix is filled with 0 or 1. The special thing about this matrix is that all the ones are towards the left-hand side of each row ...

Question 65. Capacity To Ship Packages Within D Days Leetcode Solution Problem statement   In the problem ” Capacity To Ship Packages Within D Days,” we have packets in port A that must be transferred to port B in D days. we are given a weights array that contains the weight of each packet and the number of days in which we ...

Question 66. Can Make Arithmetic Progression From Sequence Leetcode Solution Problem statement   In the problem ” Can Make Arithmetic Progression From Sequence” we are given an array, now we need to answer if it is possible to generate an Arithmetic Progression by rearranging the sequence. Example arr = [3,1,5] true Explanation: We can rearrange the array as{1,3,5} which forms an ...

Question 67. Best Time to Buy and Sell Stock III Leetcode Solution Problem statement   In the problem “Best Time to Buy and Sell Stock  III,” we are given an array where each element in the array contains the price of the given stock on that day. The definition of the transaction is buying one share of stock and selling that one share ...

Question 68. Best Time to Buy and Sell Stock  II Leetcode Solution Problem statement   In the problem “Best Time to Buy and Sell Stock  II,” we are given an array where each element in the array contains the price of the given stock on that day. The definition of the transaction is buying one share of stock and selling that one share ...

Question 69. Best Time to Buy and Sell Stock with Transaction Fee Leetcode Solution Problem statement   In the problem “Best Time to Buy and Sell Stock with Transaction Fee,” we are given an array where each element in the array contains the price of the given stock on that day. The definition of the transaction is buying one share of stock and selling that ...

Question 70. Count of index pairs with equal elements in an array Suppose, we have given an integer array. The problem “Count of index pairs with equal elements in an array” asks to find out the no of pair of indices (i,j) in such a way that arr[i]=arr[j] and i is not equal to j. Example   arr[] = {2,3,1,2,3,1,4} 3 Explanation Pairs ...

Question 71. Find Sum of all unique sub-array sum for a given array Suppose you have an array of integers. The problem “Find Sum of all unique sub-array sum for a given array” asks to find out the sum of all unique sub-arrays (Sub-array sum is the sum of each sub-array’s elements). By unique sub-array sum, we meant to say that no sub-array ...

Question 72. Minimum Sum Path in a Triangle Problem Statement   The problem “Minimum Sum Path in a Triangle” states that you are given a sequence in the form of a triangle of integers. Now starting from the top row what is the minimum sum you can achieve when you reach the bottom row? Example   1 2 3 5 ...

Question 73. Longest subarray not having more than K distinct elements The problem “Longest subarray not having more than K distinct elements” states that suppose you have an array of integers, the problem statement asks to find out the longest sub-array that having not greater than k different elements. Example   arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5} ...

Question 74. Given an Array of Pairs Find all Symmetric Pairs in it Find all symmetric pairs – You are given some pairs of an array. You have to find out the symmetric pairs in it. The symmetric pair is said to be symmetric when in pairs say (a, b) and (c, d) in which ‘b’ is equal to ‘c’ and ‘a’ is ...

Question 75. Minimum operation to make all elements equal in array The problem “Minimum operation to make all elements equal in array” states that you are given an array with some integers in it. You have to find out the minimum operations that can be done to make an array equal. Example   [ 1,3,2,4,1] 3 Explanation Either 3 subtractions can be ...

Question 76. Construct Binary Tree from given Parent Array representation The problem “Construct Binary Tree from given Parent Array representation” states that you are given an array. This input array represents a binary tree. Now you need to construct a binary tree on the basis of this input array. The array stores the index of parent node at each index. ...

Question 77. Find subarray with given sum (Handles Negative Numbers) The problem “Find subarray with given sum (Handles Negative Numbers)” states that you are given an integer array, containing negative integers as well and a number called “sum”. The problem statement asks to print the sub-array, which sums up to a given number called “sum”.  If more than one sub-array ...

Question 78. Length of the largest subarray with contiguous elements The problem “Length of the largest subarray with contiguous elements” states that you are given an integer array. The problem statement asks to find out the length of the longest contiguous sub-array of which elements can be arranged in a sequence (continuous, either ascending or descending). The numbers in the ...

Question 79. Count number of triplets with product equal to given number The problem “Count number of triplets with product equal to given number” states that we are given an integer array and a number m. The problem statement asks to find out the total number of triplets of with product equals to m. Example   arr[] = {1,5,2,6,10,3} m=30 3 Explanation Triplets ...

Question 80. Maximum difference between first and last indexes of an element in array Suppose, you have an array of integers. The problem “Maximum difference between first and last indexes of an element in array” asks to find out the difference between the first and last index of each number present in an array such that the difference is being maximum of all. Example   ...

Question 81. Find four elements that sum to a given value (Hashmap) The problem “Find four elements that sum to a given value (Hashmap)” states that suppose, you have an integer array and a number called sum. The problem statement asks to determine if four elements present in the array which sums up to the given value “sum”. If true, then function ...

Question 82. Longest subsequence such that difference between adjacents is one The problem “Longest subsequence such that difference between adjacents is one” states that you are given an integer array. Now you need to find the length of longest subsequence such that the difference of adjacent elements is 1. Example   1 2 3 4 7 5 9 4 6 Explanation As ...

Question 83. Find all triplets with zero sum The problem “Find all triplets with zero sum” states that you are given an array containing positive and negative number both. The problem statement asks to find out the triplet with the sum equal to 0. Example   arr[] = {0,-2,1,3,2,-1} (-2 -1  3) (-2 0  2) (-1 0  1) Explanation ...

Question 84. Check if a given array contains duplicate elements within k distance from each other The problem “Check if a given array contains duplicate elements within k distance from each other” states that we have to check for duplicates in given unordered array within the range of k. Here the value of k is smaller than the given array. Examples   K = 3   arr[] = ...

Question 85. Pair with given product The problem “Pair with given product” states that you are given an integer array and a number “x”. Determine, whether an array consists of a pair of which product equals ‘x’ exist in the given input array. Example   [2,30,12,5] x = 10 Yes, it has Product Pair Explanation Here 2 ...

Question 86. Maximum Distance in Array The problem “Maximum Distance in Array” states that you are given “n” no. of arrays and all the arrays are given in ascending order. Your task is to find the maximum difference/absolute difference of two numbers in an array and we can define the maximum distance between two numbers as ...

Question 87. First element occurring k times in an array We have given a number ‘k’ and an integer array. The problem “First element occurring k times in an array” says to find out the first element in the array which occurs exactly k times in an array. If there is no element in the array which occurs k times ...

Question 88. Print all subarrays with 0 sum You are given an integer array, your task is to print all the possible sub-arrays with sum is equal to 0. So we need to Print all subarrays with 0 sum. Example   arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6} Sub-Array found from 0 index ...

Question 89. Contains Duplicate We are given an array and it may be containing duplicates elements or maybe not. So we need to check if it contains duplicate. Examples   [1, 3, 5, 1] true [“apple”, “mango”, “orange”, “mango”] true [22.0, 4.5, 3.98, 45.6, 13.54] false Approach   We can check an array in several ways ...

Question 90. Form minimum number from given sequence The problem “Form minimum number from given sequence” states that you are given some pattern of I’s and D’s only. The meaning of I stands for increasing and for decreasing we are provided with D. The problem statement asks to print the minimum number which satisfies the given pattern. We have ...

Question 91. Range Queries for Longest Correct Bracket Subsequence You are given a sequence of some brackets subsequence, in other words, you are given brackets like ‘(’ and ‘)’ and you are given a query range as a starting point and ending point. The problem “Range Queries for Longest Correct Bracket Subsequence” asks to find out the maximum length ...

Question 92. Largest subarray with equal number of 0s and 1s You are given an array of integers. The integers are only 0 and 1 in the input array. The problem statement asks to find out the largest sub-array that can have equal count of 0s and 1s. Example   arr[]={0,1,0,1,0,1,1,1} 0 to 5 (total 6 elements) Explanation From the array position ...

Question 93. Binary array after M range toggle operations You are given a binary array, which consists of 0 initially and Q number of queries. The problem statement asks to toggle the values (converting 0s into 1s and 1s into 0s). After the Q queries performed, print the resultant array. Example   arr[] = {0, 0, 0, 0, 0} Toggle(2,4) ...

Question 94. Non-overlapping sum of two sets Problem Statement   The problem “Non-overlapping sum of two sets” states that you are given two arrays as input values as arrA[] and arrB[] of the same size n. Also, both of the arrays have distinct elements individually and some common elements. Your task is to find out the total sum ...

Question 95. Find all pairs (a, b) in an array such that a % b = k Problem Statement   The problem “Find all pairs (a, b) in an array such that a % b = k” states that you are given an array of integers and an integer value called k. The problem statement asks to find out the pair in such a way that that x ...

Question 96. Range LCM Queries Problem Statement   The problem “Range LCM Queries” states that you have an integer array and q number of queries. Each query contains the (left, right) as a range. The given task is to find out the LCM(left, right), i.e, LCM of all the number that comes in the range of ...

Question 97. Queries for GCD of all numbers of an array except elements in a given range Problem Statement   The “Queries for GCD of all numbers of an array except elements in a given range” problem states that you will be given an integer array and a q number of queries. Each query contains the number left and right. The problem statement asks to find out the ...

Question 98. Find whether a subarray is in form of a mountain or not Problem Statement   The problem “Find whether a subarray is in form of a mountain or not” states that you are given an integer array and a range. The problem statement asks to find out whether the sub-array formed between the given range is in form of a mountain form or ...

Question 99. Subset Sum Problem in O(sum) space Problem Statement   The “Subset sum in O(sum) space” problem states that you are given an array of some non-negative integers and a specific value. Now find out if there is a subset whose sum is equal to that of the given input value. Example   Array = {1, 2, 3, 4} ...

Question 100. Find Index of Closing Bracket for a Given Opening Bracket in an Expression Problem Statement   Given a string s of length/size n and an integer value representing the index of an opening square bracket. Find index of closing bracket for a given opening bracket in an expression. Example   s = "[ABC]" index = 0 8 s = "[C-[D]]" index = 3 5 s ...

Question 101. Gold Mine Problem Problem Statement   The “Gold Mine problem” states that you are given a 2D grid having some non-negative coins placed in each cell of the given grid. Initially, the miner is standing at the first column but there is no restriction on the row. He can start in any row. The ...

Question 102. Longest Increasing Consecutive Subsequence Subsequences are another topic loved by interviewers. Tweaking them around can always give them new opportunities for testing candidates. It can check the candidate’s ability to think and analyze things and come up with the best and optimal solutions. Today we are solving a subsequence problem that will be doing ...

Question 103. Best Time to Buy and Sell Stock Problem Statement   The problem “Best Time to Buy and Sell Stock” states that you are given an array of prices of length n, where the ith element stores the price of stock on ith day. If we can make only one transaction, that is, to buy on one day and ...

Question 104. Top K Frequent Elements Problem Statement   In top K frequent elements we have given an array nums[], find the k most frequently occurring elements. Examples   nums[] = {1, 1, 1, 2, 2, 3} k = 2 1 2   nums[] = {1} k = 1 1 Naive Approach for Top K Frequent Elements   Build ...

Question 105. Bubble sort using two Stacks Problem Statement   The problem “Bubble sort using two Stacks” states that you are given an array a[ ] of size n. Create a function to sort the given array a[ ] using a bubble sort paradigm with two stack data structures. Example   a[ ] = {15, 12, 44, 2, 5, ...

Question 106. Sort an array according to the order defined by another array Problem Statement   You are given two arrays of integers arr1[] and arr2[]. The problem “Sort an array according to the order defined by another array” asks to sort the first array according to the second array so that the numbers in first array will be relatively sorted off all the ...

Question 107. Construction of Longest Increasing Subsequence (N log N) Problem Statement   You are given an array of integers. The problem “Construction of Longest Increasing Subsequence (N log N)” asks to construct the longest increasing subsequence. Example   arr[]={1, 4, 7, 2, 9, 6, 12, 3 } 12, 9, 7, 4, 1 and the size of this longest increasing subsequence is ...

Question 108. Minimum time required to rot all oranges Problem Statement   The problem “Minimum time required to rot all oranges” states that you are given a 2D array, every cell has one of the three possible values 0, 1 or 2. 0 means an empty cell. 1 means a fresh orange. 2 means a rotten orange. If a rotten ...

Question 109. Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’ Problem Statement   The problem ” Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’ ” states that you have an “n” sized array containing integers. The numbers in the array are in a range of 0 to n-1. The problem statement asks to rearrange the array in ...

Question 110. Maximum Product Subarray Problem Statement   The problem “Maximum Product Subarray” states that you are given an array of integer containing both positive and negative numbers. The problem statement asks to find out the maximum product of the sub-array. Example   arr[] = { 2, -2, 3, 5} 15 Explanation The elements in the sub-array ...

Question 111. Convert array into Zig-Zag fashion Problem Statement   The problem “Convert array into Zig-Zag fashion” states that you are given an – of integers. The problem statement asks to sort the array in a zig-zag manner such that the elements in the array will look like à  a < b > c < d > e ...

Question 112. First negative integer in every window of size k Problem Statement   The problem “First negative integer in every window of size k” states that you are given an array containing positive and negative integers, for every window of size k print the first negative integer in that window. If there is no negative integer in any window then output ...

Question 113. Distance of nearest cell having 1 in a binary matrix Problem Statement   The problem “Distance of nearest cell having 1 in a binary matrix” states that you are given a binary matrix(containing only 0s and 1s) with at least one 1. Find the distance of the nearest cell having 1 in the binary matrix for all the elements of the ...

Question 114. Form Minimum Number From Given Sequence Problem Statement   The problem “Form Minimum Number From Given Sequence states that you are given a string s of length/size n representing a pattern of characters ‘I’ i.e. increasing and ‘D’ i.e. decreasing only. Print the minimum number for the given pattern with unique digits from 1-9. For instance – ...

Question 115. Number Of Longest Increasing Subsequence Problem Statement   The problem “Number Of Longest Increasing Subsequence” states that you are given an array a[ ] of size n. Print the number of longest increasing subsequences in it. Example   a[ ] = {1, 2, 5, 4, 7} 2 Explanation: The longest increasing subsequences can be seen in the ...

Question 116. Find Minimum In Rotated Sorted Array Problem Statement   “Find Minimum In Rotated Sorted Array” states that you are given a sorted array of size n which is rotated at some index. Find the minimum element in the array. Example   a[ ] = {5, 1, 2, 3, 4} 1 Explanation: If we arrange the array in sorted ...

Question 117. Implementation of Deque using circular array Problem Statement   “Implementation of Deque using circular array” asks to implement the following functions of a Deque(Doubly Ended Queue) using circular array, insertFront(x) : insert an element x at the front of Deque insertRear(x) : insert an element x at the rear of Deque deleteFront() : delete an element from ...

Question 118. Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest Problem Statement   Suppose you have an integer array. The problem “Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest, ..” asks to rearrange the array in such a way that the smallest number comes first and then the largest number, then second smallest and then the second ...

Question 119. Rearrange array such that even positioned are greater than odd Problem Statement   Suppose you have an integer array. The problem “Rearrange array such that even positioned are greater than odd” asks to rearrange the array such the elements at even position in an array should be greater than the element just before it. Arr[i-1] < = Arr[i], if position ‘i’ ...

Question 120. Arrange given numbers to form the biggest number Problem Statement   Suppose you have an array of integers. The problem “Arrange given numbers to form the biggest number”  asks to rearrange the array in such a manner that the output should be the maximum value which can be made with those numbers of an array. Example   [34, 86, 87, ...

Question 121. Remove duplicates from sorted array Problem Statement   “Remove duplicates from sorted array” states that you are given a sorted array of size N. You need to remove the duplicate elements from the array. Print the array containing unique elements after the removal of duplicate elements. Example   a [] = {1, 1, 1, 1} {1} Explanation: ...

Question 122. Count subarrays having total distinct elements same as original array Problem Statement   “Count subarrays having total distinct elements same as original array” states that you are given an integer array. The problem statement asks to find out the total number of sub-arrays that contain all distinct elements as present in an original array. Example   arr[] = {2, 1, 3, 2, ...

Question 123. Product of array except self Problem Statement   “Product of array except self” problem, states that you are given an array a [ ]. Print another array p [ ] of the same size such that value at i’th index of array p is equal to the product of all the elements of the original array ...

Question 124. First missing positive Problem Statement   “First missing positive” problem states that you are given an array a[ ] (sorted or unsorted) of size n. Find the first positive number that is missing in this array. Example   a[ ] = {1, 3, -1, 8}  2 Explanation: If we sort the array we get {-1, ...

Question 125. Contiguous Array Leetcode Problem Statement   “Contiguous Array Leetcode” problem states that you are given an array a[ ] of size n consists of 1’s and 0’s only. Find the longest subarray in which the number of 1’s is equal to the number of 0’s. Example   a[ ] = {1, 0, 1, 1, 1, ...

Question 126. Numbers with prime frequencies greater than or equal to k Problem Statement   Problem “Numbers with prime frequencies greater than or equal to k” states that you are given an array of integers size n and an integer value k. All the numbers inside it are prime numbers. The problem statement asks to find out the numbers which appear in the ...

Question 127. Find pairs with given sum such that elements of pair are in different rows Problem Statement   “Find pairs with given sum such that elements of pair are in different rows” problem states that you are given a matrix of integers and a value called “sum”. The problem statement asks to find out all the pairs in a matrix that sums up to a given ...

Question 128. Common elements in all rows of a given matrix Problem Statement   “Common elements in all rows of a given matrix” problem state that, you are given a matrix of M*N. The problem statement asks to find out all the common elements in a given matrix in each row of the matrix in O(M*N) time. Example   arr[]={{12, 1, 4, 5, ...

Question 129. Collect maximum points in a grid using two traversals Problem Statement   We are given a matrix of size “n x m”, and we need to collect maximum points in a grid using two traversals. If we are standing at cell i,j then we have three options to go to cell i+1, j or i+1, j-1or i+1, j+1. That is ...

Question 130. Given two unsorted arrays find all pairs whose sum is x Problem Statement   Given two unsorted arrays, find all pairs whose sum is x problem states that you are given two arrays of integers that are unsorted and a value called sum. The problem statement asks to find out the total number of pairs and print all those pairs that add ...

Question 131. Sort elements by frequency Problem Statement   You are given an array of integers, some numbers are repeated in it. The problem statement asks to print the number in the array in decreasing order according to their frequency that is to sort elements by frequency. Example   arr[]={3,4,3,1,2,9,2,9,2,5 } 2 2 2 3 3 9 9 ...

Question 132. Find the first repeating element in an array of integers Problem Statement   Find the first repeating element in an array of integers problem states that you are given an array of integer. It asks to find out the first repeating element from the array and print that number. Example   arr[] = {2,6,9,3,1,9,1} 9 Explanation: In the given array there are ...

Question 133. Find the subarray with least average Problem Statement   You have given an integer array and a number k. The problem statement asks to find the subarray with least average, which is to find out the sub-array of k elements, which has the minimum average. Example   arr[] = {12, 34, 20, 30, 24, 45} k = 3 Sub-Array of [0, 2] has a minimum average. Explanation: ...

Question 134. Find minimum number of merge operations to make an array palindrome Problem Statement   You are given an array of integers. The problem statement asks to find minimum number of merge operations to make an array palindrome, i.e. find out the minimum number of merging operations to be done on the array to make it a palindrome. Merging operation simply means that ...

Question 135. Check given array of size n can represent BST of n levels or not Problem Statement   Given an array with n elements, check given array of size n can represent BST of n levels or not. That is to check whether the binary search tree constructed using these n elements can represent a BST of n levels. Examples   arr[] = {10, 8, 6, 9, ...

Question 136. Find maximum average subarray of k length Problem Statement   You are given an array of integers and a number k. The problem statement asks to find maximum average subarray of k length. Subarray is nothing but an array composed from a contiguous block of the original array’s elements Example   arr[] = {1,3,12,34,76,10} [2, 4] Explanation: Array starting ...

Question 137. Printing brackets in Matrix Chain Multiplication Problem Problem Statement   We need to find the order of multiplication of matrices such that the number of operations involved in the multiplication of all the matrices is minimized. Then we need to print this order i.e. printing brackets in matrix chain multiplication problem. Consider you have 3 matrices A, B, ...

Question 138. Find minimum difference between any two elements Problem Statement   You are given an array of integers. The problem statement asks to find minimum difference between any two elements given in the array. Example   arr[] = {11,1,6,8,20,13} 2 Explanation: Minimum difference between 11 and 13 is 2. arr[] = {19,14,80,200,32,29} 3 Explanation: Minimum difference between 32 and 29 ...

Question 139. Largest rectangular sub-matrix whose sum is 0 Problem Statement   Find the maximum size sub-matrix in a 2D array whose sum is zero. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and find the matrix with ...

Question 140. Maximum sum rectangle in a 2D matrix Problem Statement   Find the maximum sum rectangle in a 2D matrix i.e. to find a sub-matrix with maximum sum. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and ...

Question 141. Maximum Sum Increasing Subsequence Problem Statement   You are given an array of integers. Your task is to find out the maximum sum subsequence within the array in such a way that the numbers in subsequence should be ordered in a sorted manner in increasing order. A subsequence is nothing but a sequence that we ...

Question 142. Largest Sum Contiguous Subarray Problem Statement   You are given an array of integers. The problem statement asks to find out the largest sum contiguous subarray. This means nothing but to find a subarray (continuous elements) which has the largest sum among all other subarrays in the given array. Example   arr[] = {1, -3, 4, ...

Question 143. Matrix Chain Multiplication In the matrix chain multiplication II problem, we have given the dimensions of matrices, find the order of their multiplication such that the number of operations involved in multiplication of all the matrices is minimized. Consider you have 3 matrices A, B, C of sizes a x b, b x ...

Question 144. Sorted Array to Balanced BST In sorted array to balanced BST problem, we have given an array in sorted order, construct a Balanced Binary Search Tree from the sorted array. Examples   Input arr[] = {1, 2, 3, 4, 5} Output Pre-order : 3 2 1 5 4 Input arr[] = {7, 11, 13, 20, 22, ...

Question 145. Single Number Given an array a[ ] of size n. All the elements in the array are present twice except for 1. Find the element which appears only once or in other words we say that find the single number. Example   Input : a[ ] = {1, 3, 5, 5, 2, 1, 3} ...

Question 146. Subset Leetcode In Subset Leetcode problem we have given a set of distinct integers, nums, print all subsets (the power set). Note: The solution set must not contain duplicate subsets. An array A is a subset of an array B if a can be obtained from B by deleting some (possibly, zero ...

Question 147. Shuffle an Array Given an array or set which contains n elements. Here the elements are unique or there is no repetition. Shuffle an array(or a set) of numbers without duplicates. Example   // Init an array with set 2, 4, 3 and 1. int[] nums = {2, 4, 3, 1}; Shuffle object = ...

Question 148. Maximal Square In the maximal square problem we have 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 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 ...

Question 149. Dividing Array into Pairs With Sum Divisible by K The dividing array into pairs with sum divisible by K is a problem which is asked in interviews with various tweaks now and then. Those who know me know my habit of converting these problems into stories. In this article let us look into this problem. Situation To Understand The ...

Question 150. Count Distinct Elements in Every Window of Size K Subsets are something which we have been dealing with for some time now. In the last episode, we covered the number of subsets we could make with distinct even numbers. This time we count distinct elements in every window of size K. Section-1   About the problem. Given an unsorted array ...

Question 151. Find Three Element From Different Three Arrays Such That a + b + c = sum Three Sum is a problem loved by interviewers. It is a problem I was personally asked during the Amazon interview. So, without wasting any more time let us get to the problem. An array that has both positive and negative numbers. Three numbers that sum up to zero/can be modified, ...

Question 152. Word Search Word search is something like the word-finding puzzles at some time in our life. Today I bring to the table a modified crossword. My readers must be a bit perplexed as to what I am talking about. Without wasting any more time let us get to the problem statement Can ...

Question 153. K Empty Slots K empty slots correctly present a gardener’s dilemma, trying to pick flowers that suit our condition. Our gardener has a field of N-slots. Mr gardener has planted a flower in each one of the slots. Each flower will bloom on a certain unique day. Also, we have planted evergreen flowers. ...

Question 154. Count Pairs Whose Products Exist in Array In count pairs whose products exist in array problem we have given an array, count all the distinct pairs whose product value is present in the array. Example   Input A[]={2, 5, 6, 3, 15} Output Number of distinct pairs whose product exists in the array is: 2 Pairs are: (2, ...

Question 155. Print All Distinct Elements of a Given Integer Array Given an integer array, print all distinct elements in the array. The given array may contain duplicates and the output should print every element only once. The given array is not sorted. Example   Input: nums[]= {12, 10, 9, 45, 2, 10, 10, 45} Output: 12, 10, 9, 45, 2 Approach ...

Question 156. Pair of Positive Negative Values in an Array In pair of positive negative values in an array problem we have given an array A of distinct integers, print all the pairs having positive value and negative value of a number that exists in the array. We need to print pairs in order of their occurrences. A pair whose ...

Question 157. Count Pairs With Given Sum Given an integer array of size n, and an integer  ‘K’, you need to count the number of pairs(need not to be unique) present in the array whose sum is equal to ‘K’. Example   Input: Arr={1,  5,  7, 1} K=6 Output: 2 Brute force solution for Count Pairs With Given Sum   Main idea ...

Question 158. Insert Delete GetRandom In Insert Delete GetRandom problem we need to 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 random element from the current set ...

Question 159. Merge Overlapping Intervals In merge overlapping intervals problem we have given a collection of intervals, merge and return all overlapping intervals. Example   Input : [[2, 3], [3, 4], [5, 7]] Output: [[2, 4], [5, 7]] Explanation: We can merge [2, 3] and [3, 4] together to form [2, 4] Approach for finding Merge ...

Question 160. Median of Two Sorted Arrays Given two sorted arrays A and B of size n and m respectively. Find the median of the final sorted array obtained after merging the given two arrays or in other words, we say that find median of two sorted arrays. ( Expected time complexity: O(log(n)) ) Approach 1 for ...

Question 161. Maximum Product Subarray In the maximum product subarray problem, we have given an array of integers, find the contiguous sub-array with atleast one element which has the largest product. Example   Arr=[ 0, -1, 0 ,1 ,2, -3] Maximum product = 2 Arr=[-1, -1, -1] Maximum product = -1 Arr=[0, -1, 0, -2, 0] ...

Question 162. Find Maximum of Minimum for Every Window Size in a Given Array Given an array a[ ] of size n. For every window size that varies from 1 to n in array print or find maximum of minimum for every window size in a given array. Example   Input : a[ ] = {10, 20, 30, 50, 10, 70, 30} Output : 70 30 20 ...

Question 163. Minimum Size Subarray Sum Given an array nums of a positive integer and a sum s, find the minimum size of a contiguous subarray of nums such that whose sum equals to or greater than s(given value). Example   Input: nums[] = {2, 3, 1, 2, 4, 3} s = 7 Output: 2   {Subarray [4, ...

Question 164. Search an Element in Sorted Rotated Array In search in sorted rotated array problem we have given a sorted and rotated array and an element, check if the given element is present in the array or not. Examples   Input nums[] = {2, 5, 6, 0, 0, 1, 2} target = 0 Output true Input nums[] = {2, ...

Question 165. Maximum Product Subarray Given an array of n integers, find the maximum product obtained from a contiguous subarray of the given array. Examples   Input arr[] = {-2, -3, 0, -2, -40} Output 80 Input arr[] = {5, 10, 6, -2, 1} Output 300 Input arr[] = {-1, -4, -10, 0, 70} Output 70 ...

Question 166. Set Matrix Zeroes In the set matrix zeroes problem, we have given a (n X m) matrix, if an element is 0, set its entire row and column 0. Examples   Input: { [1, 1, 1] [1, 0, 1] [1, 1, 1] } Output: { [1, 0, 1] [0, 0, 0] [1, 0, 1] ...

Question 167. 3 Sum In 3 Sum problem, we have given an array nums of n integers, find all the unique triplets that sum up to 0. Example   Input: nums = {-1, 0, 1, 2, -1, -4} Output: {-1, 0, 1}, {-1, 2, -1} Naive Approach for 3 Sum problem   The Brute force approach ...

Question 168. Find The Duplicate Number Given an array nums containing (n + 1) elements and every element is between 1 to n. If there is only one duplicate element, find the duplicate number. Examples   Input: nums = {1, 3, 4, 2, 2} Output: 2 Input: nums = {3, 1, 3, 4, 2} Output: 3 Naive ...

Question 169. Reservoir Sampling Reservoir Sampling is a technique of selecting k reservoir items randomly from a given list of n items, where n is very large. For example, search lists in Google, YouTube etc. Naive Approach for Reservoir Sampling   Build a reservoir array of size k, randomly select items from the given list. ...

Question 170. Most Frequent Element in an Array You are given an array of integers. The problem statement says that you have to find out the most frequent element present in an array. If there are multiple values that occurs the maximum number of times, then we have to print any of them. Example   Input [1, 4,5,3,1,4,16] Output ...

Question 171. Minimum Path Sum In the minimum path sum problem, we have given “a × b” matrix consisting of non-negative numbers. Your task is to find the path from top left to right bottom which minimizes the sum consisting of all the numbers which come in a path you found. Note: You can only move ...

Question 172. How to Efficiently Implement k Stacks in a Single Array? Design and implement a new data structure that Implement k Stacks in a Single Array. The new data structure must support these two operations – push (element, stack_number): that pushes the element in a given number of the stack. pop (stack_number): that pop out the top element from a given ...

Question 173. Print Next Greater Number of Q queries In Print Next Greater Number of Q queries problem we have given an array a[ ] of size n containing numbers and another array q[ ] of size m representing queries. Each query represents the index in array a[ ]. For each query, i print the number from the array ...

Question 174. Check if an Array is Stack Sortable In check if an array is stack sortable problem we have given an array a[ ] of size n containing elements from 1 to n in random order. Sort the array in ascending order using a temporary stack following only these two operations – Remove the element at the starting ...

Question 175. Find Top K (or Most Frequent) Numbers in a Stream In find top k (or most frequent) numbers in a stream problem, we have given an integer array consisting of some numbers. The problem statement says that you have to take an element from the array, and you can only have at most k numbers at the top. We need ...

Question 176. K Empty Slots LeetCode K Empty Slots is a very famous problem on LeetCode. The problem statement is like that- A garden is consists of n slots containing a flower each. All the flowers are unbloomed initially. Given an array a[ ] of flowers and an integer k. Considering i stating from 0, i+1’th ...

Question 177. Trapping Rain Water In Trapping Rain Water problem we have given N non-negative integers representing an elevation map and the width of each bar is 1. We have to find the amount of water that can be trapped in the above structure. Example   Let’s understand that by an example For the above elevation ...

Question 178. Sliding Window Technique Before getting on and along with what is the sliding window technique? What it does and how it does what it does let us get the hang of this concept by a small problem Given an array of integers, we have the task of finding the minimum sum from all ...

Question 179. Finding K closest element In Finding K closest element problem we have given a sorted array and a value x. The problem is to find the K number of elements closest to x in the given array. Given an array arr[] ={12, 16, 22, 30, 35, 39, 42,45, 48, 50, 53, 55, 56} and x ...

Question 180. Jump Game In jump game we have given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example   Input: arr = [2,3,1,1,4] ...

Question 181. Postfix to Prefix Conversion In this problem, we have given a string that denotes the postfix expression. We have to do postfix to prefix conversion. Prefix Notation In this notation, we write the operands after the operator. It is also known as Polish Notation. For instance: +AB is a prefix expression. Postfix Notation In ...

Question 182. Combination Sum In combination sum problem we have given an array of positive integers arr[] and a sum s, find all unique combinations of elements in arr[] where the sum of those elements is equal to s. The same repeated number may be chosen from arr[] an unlimited number of times. Elements ...

Question 183. Max Area of Island Problem Description: Given a 2D matrix, the matrix has only 0(representing water)  and 1(representing land) as entries. An island in the matrix is formed by grouping all the adjacent 1’s connected 4-directionally(horizontal and vertical). Find the maximum area of the island in the matrix. Assume that all four edges of ...

Question 184. Search in Sorted Rotated Array An element search in sorted rotated array can be found using binary search in O(logn) time. The objective of this post is to find a given element in a sorted rotated array in O(logn) time. Some example of a sorted rotated array is given. Example   Input : arr[] = {7,8,9,10,1,2,3,5,6}; ...

Question 185. Unique Paths A m x n 2D  grid is given and you are standing at the topmost and leftmost cell in the grid. i.e. the cell located at (1,1). Find the number of unique paths that can be taken to reach a cell located at (m,n) from the cell located at (1,1) ...

Question 186. Maximum Subarray In the Maximum Subarray problem we have given an integer array nums, find the contiguous sub array which has the largest sum and print the maximum sum subarray value. Example   Input nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4} Output 6 Algorithm   The goal is to find ...

Question 187. Length of Longest Fibonacci Subsequence Given a strictly increasing array of positive integers, find the length of the longest fibonacci subsequence. A sequence of n elements is fibonacci like if, n >= 3 xi = x(i – 2) + x(i -1), where xi is the ith term of the sequence and i >= 2 Examples   Input arr[] ...

Question 188. Merging Intervals In merging intervals problem we have given a set of intervals of the form [l, r], merge the overlapping intervals. Examples   Input {[1, 3], [2, 6], [8, 10], [15, 18]} Output {[1, 6], [8, 10], [15, 18]} Input {[1, 4], [1, 5]} Output {[1, 5]} Naive Approach for merging intervals   ...

Question 189. 4Sum In the 4Sum problem, we have given an integer x and an array a[ ] of size n. Find all the unique set of 4 elements in array such that sum of those 4 elements is equal to the given integer x. Example   Input  a[ ] = {1, 0, -1, ...

Question 190. Find Peak Element Let’s understand Find Peak Element problem. Today we have with us an array that needs its peak element. Now, you must be wondering as to what do I mean by the peak element? The peak element is one which is greater than all its neighbours. Example: Given an array of ...

Question 191. K-th Smallest Element in a Sorted Matrix In K-th Smallest Element in a Sorted Matrix problem, we have given an n x n matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the given 2D array. Example   Input 1: k = 3 and matrix = 11, 21, 31, 41 ...

Question 192. Pascal Triangle Leetcode The Pascal Triangle is a very good Leetcode problem that is asked so many times in Amazon, Microsoft, and other companies. we have given non-negative integer rows, print first rows rows of the pascal triangle. Example   rows = 5 rows = 6 Types of solution for Pascal Triangle Leetcode   Dynamic Programming ...

Question 193. Missing Number In Missing Number problem we have given an array of size N containing a number from 0 to N. All the values in the array are unique. We need to find the missing number which is not present in the array and that number lies between 0 to N. Here ...

Question 194. Merge Sorted Array In merge sorted array problem we have given two sorted arrays in increasing order. In input first, we have given the number initialized to array1 and array2. These two-number are N and M. The size of array1 is equal to the sum of N and M. In array 1 first ...

Question 195. Partition Equal Subset Sum Partition Equal Subset Sum is a problem in which we have given an array of positive numbers. We have to find out that can we divide it into two subsets such that the sum of elements in both sets is the same. Here it’s not necessary that the number of ...

Question 196. Sort Colors Sort colors is a problem in which we have to given an array containing N objects. Each box is painted with a single color which can be red, blue, and white. We have N objects which are already painted. We have to sort the array such that the same color ...

Question 197. Rotate Array Rotate array is a problem in which we have given an array of size N. We have to rotate the array in the right direction. Each element shift by one position right and last element of the array come to the first position. So, we have given a value K ...

Question 198. Container with Most Water Problem description : you are given n integers (y0, y1, y2 … yn-1) at n indices (i = 0,1,2 … n-1). Integer at i-th index is yi. Now, you draw n lines on a cartesian plane each connecting points (i, yi) and (i, 0). Find the maximum volume of water ...

Question 199. Matrix Chain Multiplication using Dynamic Programming Matrix Chain Multiplication is a method in which we find out the best way to multiply the given matrices. We all know that matrix multiplication is associative(A*B = B*A) in nature. So, we have a lot of orders in which we want to perform the multiplication. Actually, in this algorithm, ...

Question 200. Subarray Sum Equals k Given an integer array and an integer k. Find total number of contiguous subarrays of given array whose sum of elements is equal to k. Example   Input 1: arr[] = {5,0,5,10,3,2,-15,4} k = 5 Output: 7 Input 2: arr[] = {1,1,1,2,4,-2} k = 2 Output: 4 Explanation : consider example-1 ...

Question 201. Subset sum problem In the subset sum problem, we are given a list of all positive numbers and a Sum. We need to check if there is a subset whose sum is equal to the given sum. Example   Input List of numbers: 1 2 3 10 5 sum: 9 Output  true Explanation  for ...

Question 202. Heap Sort Heap sort is a comparison based sorting technique that is based on a Binary Heap data structure. HeapSort is similar to a selection sort where we find the maximum element and then place that element at the end. We repeat this same process for the remaining elements. Given an unsorted ...

Question 203. Coin Change Problem Coin Change Problem – Given some coins of different values c1, c2, … , cs (For instance: 1,4,7….). We need an amount n. Use these given coins to form the amount n. You can use a coin as many times as required. Find the total number of ways in which ...

Question 204. Multiplication of Two Matrices Problem Statement   In the “Multiplication of Two Matrices” problem we have given two matrices. We have to multiply these matrices and print the result or final matrix. Here, the necessary and sufficient condition is the number of columns in A should be equal to the number of rows in matrix ...

Question 205. Minimum number of Merge Operations to make an Array Palindrome Problem Statement   In the “Minimum number of Merge Operations to make an Array Palindrome” problem we have given an array “a[]”. Find the minimum number of merge_operations are required to make an array palindrome. Note, A palindrome is a word, phrase, or sequence that reads the same backward as forwards. ...

Question 206. Form Minimum Number from Given Sequence of D’s and I’s Problem Statement   In the “Form Minimum Number from Given Sequence of D’s and I’s” problem, we have given a pattern containing only I’s and D’s. I for increasing and D for decreasing. Write a program to print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat. Input Format   ...

Question 207. Find the Subarray of given length with Least Average Problem Statement   In the “Find the Subarray of given length with Least Average” problem we have given an array and an input integer X. Write a program to find the subarray of length X with least/minimum average. Prints the starting and ending indexes of the subarray which has the least ...

Question 208. Find Zeros to be Flipped so that Number of Consecutive 1’s is Maximized Problem Statement   In the “Find Zeros to be Flipped so that Number of Consecutive 1’s is Maximized” problem we have given a binary array and a number x which denotes the no. of zeros to be flipped. Write a program to find the zeros that need to be flipped so ...

Question 209. Merge K Sorted Arrays and Print Sorted Output Problem Statement   In the “Merge K Sorted Arrays and Print Sorted Output” problem we have given k sorted arrays of different size. Write a program to merge those arrays and prints the final sorted array as output. Input Format   The first line containing an integer n. Next n lines containing ...

Question 210. Find the Minimum Element in a Sorted and Rotated Array Problem Statement   In the “Find the Minimum Element in a Sorted and Rotated Array” problem we have given a sorted array a[]. This array is rotated at some unknown point, find the minimum element in this array. Input Format   The first and only one line containing an integer value n. ...

Question 211. Sort Elements by Frequency II Problem Statement   In the “Sort Elements by Frequency II” problem we have given an array a[]. Sort the array according to the frequency of the elements where the higher frequency element comes first then others. Input Format   The first and only one line containing an integer n. Second-line containing n ...

Question 212. Stock Buy Sell to Maximize Profit Problem Statement   In the “Stock Buy Sell to Maximize Profit” problem we have given an array that contains stock price on each day, find the maximum profit that you can make by buying and selling in those days. Here, we can buy and sell multiple times but only after selling ...

Question 213. Merge Overlapping Intervals II Problem Statement   In the “Merge Overlapping Intervals II” problem we have given a set of intervals. Write a program that will merge the overlapping intervals into one and print all the non-overlapping intervals. Input Format   The first line containing an integer n. Second-line containing n pairs where each pair is ...

Question 214. Maximum Subarray Sum using Divide and Conquer Problem Statement   In the “Maximum Subarray Sum using Divide and Conquer” problem we have given an array of both positive and negative integers. Write a program that will find the largest sum of the contiguous subarray. Input Format   The first line containing an integer N. Second-line containing an array of ...

Question 215. Pancake Sorting Problem Problem Statement   “Pancake Sorting Problem” is based on pancake sorting. Given an unsorted array, we need to write a program that uses only flip operation to sort the array. Flip is the operation that reverses the array. Input Format   The first line containing an integer N. Second-line containing N space-separated ...

Question 216. Pancake Sorting Problem Statement   In the “Pancake Sorting” problem we have given an array of integers A[]. Sort the array by performing a series of pancake flips. In one pancake flip we do the following steps: Choose an integer k where 1 <= k <= arr.length. Reverse the sub-array arr[0…k-1] (0-indexed). Input ...

Question 217. Arrange given Numbers to Form the Biggest Number II Problem Statement   In the “Arrange given Numbers to Form the Biggest Number II” problem, we have given an array of positive integers.  Arrange them in such a way that the arrangement will form the largest value. Input Format   The first and only one line containing an integer n. Second-line containing ...

Question 218. Iterative Implementation of Quick Sort Problem Statement   In the “Iterative Implementation of Quick Sort” problem, we have given an array a[]. We have to sort the array using quick sort. Here, quick sort is not implemented recursively, it is implemented in an iterative manner. Input Format   The first line containing an integer n. Second-line containing ...

Question 219. Shuffle a given Array Problem Statement   In the “Shuffle a given Array” problem we have given an array of integers. Write a program that shuffles the given array. That is, it will shuffle the elements in the array randomly. Input Format   The first line containing an integer n. Second-line containing n space-separated integer Output ...

Question 220. Find the Row with Maximum Number of 1’s Problem Statement   In the “Find the Row with Maximum Number of 1’s” problem we have given a matrix(2D array) containing binary digits with each row sorted. Find the row which has the maximum number of 1’s. Input Format   The first line containing two integers values n, m. Next, n lines ...

Question 221. Sorting a K Sorted Array Problem Statement   In the “Sorting a K Sorted Array” problem we have given an array of n elements, where each element is at most k away from its target position. Devise an algorithm that sorts in O(n log k) time. Input Format   The first line containing two integer values N ...

Question 222. Maximum Product Subarray II Problem Statement   In the “Maximum Product Subarray II” problem we have given an array consisting of positive, negative integers, and also zeroes. We need to find the maximum product of the subarray. Input Format   The first line containing an integer N. Second-line containing N space-separated integers. Output Format   The only ...

Question 223. Largest Subarray with Equal Number of 0’s and 1’s Problem Statement   In the “Largest Subarray with Equal Number of 0’s and 1’s” problem, we have given an array a[] containing only 0 and 1. Find the largest subarray with an equal number of 0’s and 1’s and will print the start index and end index of the largest subarray. ...

Question 224. Maximum Sum Increasing Subsequence Problem Statement   In the “Maximum Sum Increasing Subsequence” problem we have given an array. Find the sum of the maximum subsequence of the given array, that is the integers in the subsequence are in sorted order. A subsequence is a part of an array which is a sequence that is ...

Question 225. Number of Smaller Elements on Right Side Problem Statement   In the “Number of Smaller Elements on Right Side” problem, we have given an array a[]. Find the number of smaller elements that are on the right_side of each element. Input Format   The first and only one line containing an integer N. Second-line containing N space-separated integers. Output ...

Question 226. Increasing Subsequence of Length three with Maximum Product Problem Statement   In the “Increasing Subsequence of Length three with Maximum Product” problem, we have given an array of positive integers. Find the subsequence of length 3 with the maximum product. Subsequence should be increasing. Input Format   The first and only one line containing an integer N denoting the size ...

Question 227. Elements Appear more than N/K times in Array Problem Statement   In the “Elements Appear more than N/K times in Array” problem we have given an integer array of size n. Find the elements which appear more than n/k times. Where k is the input value. Input Format   The first and only one line containing two integers N and ...

Question 228. Find the Peak Element from an Array Problem Statement   In the “Find the Peak Element from an Array” problem we have given an input array of integers. Find a peak element. In an array, an element is a peak element, if the element is greater than both the neighbours. For corner elements, we can consider the only ...

Question 229. Rearrange Positive and Negative Numbers Alternatively in Array Problem Statement   In the “Rearrange Positive and Negative Numbers Alternatively in Array” problem we have given an array a[]. This array contains positive and negative integers. Rearrange the array in such a way that positive and negative are placed alternatively. Here, the number of positive and negative elements need not ...

Question 230. Find the Maximum Repeating Number in Array Problem Statement   In the “Find the Maximum Repeating Number in Array” problem we have given an unsorted array of size N. Given array contains numbers in range {0, k} where k <= N. Find the number that is coming the maximum number of times in the array. Input Format   The ...

Question 231. Tug of War Problem Statement   In tug of war problem, we have given an array of integers, divide the array into two subsets of size n/2 size each so that the difference of the sum of two subsets is as minimum as possible. If n is even each subset size is n/2. If ...

Question 232. First Circular Tour to Visit all the Petrol Bunks In the first circular tour to visit all the petrol bunks problem the statement is such that there is a circle with n petrol pumps on the circle. Every petrol pump has a pair of data. The first value is the amount of petrol pump has and the second is ...

Question 233. Count Possible Triangles Problem Statement   In count possible triangles problem we have given an array of n positive integers. Find the number of triangles that can be formed using three different elements of the array as the sides of a triangle. Note: The condition of the triangle is the sum of two sides ...

Question 234. Maximum Circular Subarray Sum Problem Statement   In the maximum circular subarray sum problem, we have given an array of integers arranged in a circle, find the maximum sum of consecutive numbers in the circular array. Example   Input arr[] =  {13, -17, 11, 9, -4, 12, -1} Output 40 Explanation Here, sum = 11 + ...

Question 235. Four Elements that Sum to Given Problem Statement   In four elements that sum to a given problem, we have given an array containing N elements that may be positive or negative. Find the set of four elements whose sum is equal to given value k. Input Format   First-line containing an integer N. Second-line containing an array ...

Question 236. Partition Problem Problem Statement   In the Partition problem, we have given a set that contains n elements. Find whether the given set can be divided into two sets whose sum of elements in the subsets is equal. Example   Input arr[] = {4, 5, 11, 9, 8, 3} Output Yes Explanation The array ...

Question 237. The Celebrity Problem Problem Statement   In the celebrity problem there is a room of N people, Find the celebrity. Conditions for Celebrity is- If A is Celebrity then Everyone else in the room should know A. A shouldn’t know anyone in the room. We need to find the person who satisfies these conditions. ...

Question 238. Find a Sorted Subsequence of size 3 Problem Statement   In the given unsorted array of integers. We need to find a sorted subsequence of size 3. Let three elements be array[i], array[j], array[k] then, array[i] < array[j] < array[k] for i< j < k. If there are multiple triplets found in the array then print any one ...

Question 239. Subarray with Given Sum Problem Statement   In the subarray with the given sum problem, we have given an array containing n positive elements. We have to find the subarray in which the sum of all the elements of the subarray equal to a given_sum. Subarray is obtained from the original array by deleting some ...

Question 240. Maximum Element in an Array which is Increasing and then Decreasing Problem Statement   In the given array which contains n elements. Elements are stored in such a way that first k elements are in increasing order and then n-k elements in decreasing from there, we need to find the maximum element in the array. Example   a)    Input array : [15, 25, ...

Question 241. Count Minimum Steps to Get the given Array Problem Statement   In count minimum steps to get the given array problem, we have given an input array target[] containing n elements, we need to compute the minimum number of operations from converting array[] of size n with all zeros to target[]. Operations a)    Increment an element by 1 is ...

Question 242. Find the Lost Element From a Duplicated Array Problem Statement   Given two arrays A and B, one array is a duplicate of the other except one element. The one element is missing from either A or B. we need to find the lost element from a duplicated array. Example   5 1 6 4 8 9 6 4 8 ...

Question 243. Rearrange given Array in Maximum Minimum Form Problem Statement   In the “Rearrange given Array in Maximum Minimum Form” problem, we have given a sorted array containing N elements. Rearrange the given sorted array of positive integers, such that alternative elements are ith max and ith min. See below for a better understanding of rearrangement of elements- Array ...

Question 244. Subarray and Subsequence Problem Statement   In the subarray and subsequence problem, we have to print all the subarrays and subsequences for a given array. Generate all possible non-empty subarrays. A subarray is commonly defined as a part or section of an array in which the contiguousness is based on the index. The subarray ...

Question 245. Merge Two Sorted Arrays Problem Statement   In merge two sorted arrays problem, we have given two input sorted arrays, we need to merge these two arrays such that the initial numbers after complete sorting should be in the first array and remaining in the second array. Example   Input A[] = {1, 3, 5, 7, ...

Question 246. Count of Triplets With Sum Less than Given Value Problem Statement   We have given an array containing N number of elements. In the given array, Count the number of triplets with a sum less than the given value. Example   Input a[] = {1, 2, 3, 4, 5, 6, 7, 8} Sum = 10 Output 7 Possible triplets are : ...

Question 247. Next Greater Element in an Array Problem Statement   Given an array, we will find the next greater element of each element in the array. If there is no next greater element for that element then we will print -1, else we will print that element. Note: Next greater element is the element that is greater and ...

Question 248. Merging Two Sorted Arrays Problem Statement   In merging two sorted arrays problem we have given two sorted arrays, one array with size m+n and the other array with size n. We will merge the n sized array into m+n sized array and print the m+n sized merged array. Example   Input 6 3 M[] = ...

Question 249. Find a Fixed Point in a Given Array Problem Statement   Given an array of n distinct elements, find a fixed point in a given array, where a fixed point means the element value is the same as the index. Example   Input 5 arr[] = {0,4,8,2,9} Output 0 is a fixed point in this array because value and index ...

Question 250. Find Element Using Binary Search in Sorted Array Problem Statement   Given a sorted array, Find element using binary search in the sorted array. If present, print the index of that element else print -1. Example   Input arr[] =  {1, 6, 7, 8, 9, 12, 14, 16, 26, 29, 36, 37, 156} X = 6 //element to be searched ...

Question 251. Find Triplet in Array With a Given Sum Problem Statement   Given an array of integers, find the combination of three elements in the array whose sum is equal to a given value X. Here we will print the first combination that we get. If there is no such combination then print -1. Example   Input N=5, X=15 arr[] = ...

Question 252. Find Duplicates in an Array in Most Efficient Way Problem Statement   Display all the elements which are duplicates in the most efficient way in O(n) and O(1) space. Given an array of size n which contains numbers from range 0 to n-1, these numbers can occur any number of times. Find duplicates in an array in the most efficient ...

Question 253. Sort 0s 1s and 2s in an Array Problem Statement   Given an array containing N elements where elements of the array are 0,1 or 2. Sort or Segregate 0s 1s and 2s in an array. Arrange all zeros in the first half, all ones in the second half and all twos in the third half. Example   Input 22 ...

Question 254. Find Leaders in an Array Problem Statement   Given an array containing N elements. Find the leaders in an array. Leaders are the element that have no element larger than themselves on the right of them in the array. Example   Input 7 1 95 4 46 8 12 21 Output 95 46 21 Explanation Here no ...

Question 255. Smallest Positive Number Missing in an Unsorted Array Problem Statement   In the given unsorted array find the smallest positive number missing in an unsorted array. A positive integer doesn’t include 0. We can modify the original array if needed. The array may contain positive and negative numbers. Example   a. Input array : [3, 4, -1, 0, -2, 2, 1, ...

Question 256. Find K Length Subarray of Maximum Average Problem Statement   In find K length subarray of maximum average problem, we have given an array of size N. Finding the start position of a subarray in the given array of size k with a maximum average. The array may contain positive and negative numbers. (Average = sum of elements/number ...

Question 257. Find Pythagorean Triplets from Array Problem Statement   We have given an array that contains n integers. We need to find the set of Pythagorean triples from the given array. Note: Pythagorean triplets condition: a^2 + b^2 = c^2. Example   Input 6 [3, 4, 6, 5, 7, 8] Output Pythagorean triplets: 3, 4, 5 Approach 1   ...

Question 258. Move All the Zeros to the End of the Given Array Problem Statement   In the given array move all the zeros which are present in the array to the end of the array. Here there is always a way exist to insert all the number of zeroes to the end of the array. Example   Input 9 9 17 0 14 0 ...

Question 259. Find Minimum Distance Between Two Numbers in an Array Problem Statement   In the given unsorted array, which may also contain duplicates, find the minimum distance between two different numbers in an array. Distance between 2 numbers in an array: the absolute difference between the indices +1. Example   Input 12 3 5 4 2 6 5 6 6 5 4 ...

Question 260. Count Number of Occurrences in a Sorted Array Problem Statement   In the “Count Number of Occurrences in a Sorted Array” problem, we have given a sorted array. Count the number of occurrences or frequency in a sorted array of X where X is an integer. Example   Input 13 1 2 2 2 2 3 3 3 4 4 ...

Question 261. Maximum Sum of Non Consecutive Elements Problem Statement   In the “Maximum Sum of Non Consecutive Elements” given array, you need to find the maximum sum of non-consecutive elements. You can not add immediate neighbor numbers. For example [1,3,5,6,7,8,] here 1, 3 are adjacent so we can’t add them, and 6, 8 are not adjacent so we ...

Question 262. Find Smallest Missing Number in a Sorted Array Problem Statement   In the “Find Smallest Missing Number in a Sorted Array” problem we have given an integer array. Find the smallest missing number in N sized sorted array having unique elements in the range of 0 to M-1, where M>N. Example   Input [0, 1, 2, 3, 4, 6, 7, ...

Question 263. First Repeating Element Problem Statement   We have given an array that contains n integers. We have to find the first repeating element in the given array. If there is no repeated element then print “No repeating integer found”. Note: Repeating elements are those elements that come more than once. (Array may contain duplicates) ...

Question 264. A Product Array Puzzle Problem Statement   In a product array puzzle problem we need to construct an array where the ith element will be the product of all the elements in the given array except element at the ith position. Example   Input  5 10 3 5 6 2 Output 180 600 360 300 900 ...

Question 265. Find All Pairs With a Given Difference Problem Statement   We have given an array of containing different elements or no repeated elements present in the array. Find all pairs with a given difference. If there is no any pair with given different then print “No pair with given different”. Example   Input 10 20 90 70 20 80 ...

Question 266. Find the first Repeating Number in a Given Array Problem Statement   There can be multiple repeating numbers in an array but you have to find the first repeating number in a given array (occurring the second time). Example   Input 12 5 4 2 8 9 7 12 5 6 12 4 7 Output 5 is the first repeating element ...

Question 267. Maximum difference between two elements such as larger element comes after smaller Problem Statement   We have given an array of n integers in which we have to find the maximum difference between two elements such as larger element comes after smaller. Example   Input 4  7  2  18  3  6  8  11  21 Output 19 Approach 1 for Maximum difference between two elements    ...

Question 268. Majority Element Problem Statement   Given a sorted array, we need to find the majority element from the sorted array. Majority element: Number occurring more than half the size of the array. Here we have given a number x we have to check it is the majority_element or not. Example   Input 5 2 ...

Question 269. Find the First and Second Smallest Elements Problem Statement   In find the first and second smallest elements problem we have given an array of integers. Find the first and second smallest integers from an array or find two smallest numbers from an array. Example   Input 7, 6, 8, 10, 11, 5, 13, 99 Output First Smallest is ...

Question 270. Find the Number Occurring Odd Number of Times in an Array Problem Statement   Given an array of positive integers. All numbers occur even a number of times except one number which occurs an odd number of times. We have to find the number occurring an odd number of times in an array. Example   Input 1, 1, 1, 1, 2, 2, 3, ...

Question 271. Sort Elements by Frequency of Occurrences Problem Statement   In sort elements by frequency of occurrences problem, we have given an array a[]. Sort array elements in such a way that the element with the highest number of occurrences comes first. If the number of occurrences is equal then the print the number which appeared first in ...

Question 272. Find the Missing Number Problem Statement   In finding the missing number from an array of 1 to N numbers we have given an array that contains N-1 numbers. One number is missing from an array of numbers from 1 to N. We have to find the missing number. Input Format   First-line containing an integer ...

## String Questions Amazon

Question 273. Minimum Number of Steps to Make Two Strings Anagram Leetcode Solutions Problem Statement   In this problem, we are given two strings ‘s’ & ‘t’ consisting of lower-case English characters. In one operation, we can choose any character in string ‘t’ and change it to some other character. We need to find the minimum number of such operations to make ‘t’ an ...

Question 274. Isomorphic Strings Leetcode Solution Problem Statement   In this problem, we are given two strings, a and b. Our goal is to tell whether the two strings are isomorphic or not. Two strings are called isomorphic if and only if the characters in the first string can be replaced by any character(including itself) at all ...

Question 275. Minimum Swaps to Make Strings Equal Leetcode Solution Problem Statement   You are given two strings s1 and s2 of equal length consisting of letters “x” and “y” only. you can swap any two characters belong to different strings, your task is to make both the string equal. return minimum number of swaps required to make both strings equal ...

Question 276. Remove Palindromic Subsequences Leetcode Solution The problem Remove Palindromic Subsequences Leetcode Solution states that you are given a string. The string consists of only two characters ‘a’ or ‘b’. You are required to erase the whole string. There is a restriction that you can delete only a palindromic subsequence in one move. Find the minimum ...

Question 277. Defanging an IP Address Leetcode Solution Problem Statement   In this problem, we are given an IP Address. We just have to convert it into a Defanged IP Address i.e. in our output string, all the “.” are converted to “[.]”. Example #1: address = "1.1.1.1" "1[.]1[.]1[.]1" #2: address = "255.100.50.0" "255[.]100[.]50[.]0" Approach 1 (Using String Stream/Builder)   ...

Question 278. String Matching in an Array Leetcode Solution The problem String Matching in an Array Leetcode Solution provides us with an array of strings. The problem asks us to find the strings that are substrings of some other string from the input. Just a quick reminder, a substring is nothing but a part of the string remaining after ...

Question 279. Is Subsequence Leetcode Solution Problem Statement   In this problem, we are given two different strings. The goal is to find out whether the first string is a subsequence of the second. Examples first string = "abc" second string = "mnagbcd" true first string = "burger" second string = "dominos" false Approach(Recursive)   This is easy ...

Question 280. Find the Difference Leetcode Solution In this problem, we are given two strings. The second string is generated by shuffling the characters of the first string randomly and then adding an extra character at any random position. We need to return the extra character that was added to the second string. The characters will always ...

Question 281. Add Binary Leetcode Solution Problem Statement   Given two binary strings a and b, we have to add these two strings and then return the result as a binary string. Binary string are the strings that contains only 0s and 1s. Example a = "11", b = "1" "100" a = "1010", b = "1011" "10101" Approach   For adding two ...

Question 282. Valid Palindrome Leetcode Solution Problem Statement   Given a string, we have to determine if it is a palindrome, considering only alphanumeric characters i.e. numbers and alphabets only. We also have to ignore cases for alphabet characters. Example "A man, a plan, a canal: Panama" true Explanation: “AmanaplanacanalPanama”  is a valid palindrome. "race a car" ...

Question 283. Reverse Vowels of a String Leetcode Solution Problem Statement   In this problem a string is given and we have to reverse only the vowels of this string. Example "hello" "holle" Explanation: before reversing :  “hello” after reversing    :  “holle” "leetcode" "leotcede" Explanation: Approach 1 (Using Stack)   We just have to reverse the vowels present in input ...

Question 284. Roman to Integer Leetcode Solution In the problem “Roman to Integer”, we are given a string representing some positive integer in its Roman numeral form. Roman numerals are represented by 7 characters that can be converted to integers using the following table: Note: The integer value of the given roman numeral will not exceed or ...

Question 285. Path Crossing Leetcode Solution Problem Statement   In path crossing problem a_string is given in which there are only four different characters ‘N’, ‘S’, ‘E’ or ‘W’ showing the movement of an object in one direction at a time by 1 unit. Object is initially at origin (0,0). We have to find out if the ...

Question 286. Multiply Strings Leetcode Solution The problem Multiply Strings Leetcode solution asks us to multiply two strings which are given to us as input. We are required to print or return this result of multiplying to the caller function. So to put it more formally given two strings, find the product of the given strings. ...

Question 287. Integer to Roman Leetcode Solution In this problem, we are given an integer and are required to convert into roman numeral. Thus the problem is generally referred to as “Integer to Roman” and this is Integer to Roman Leetcode Solution. If someone does not know about Roman numerals. In the old times, people did not ...

Question 288. Scramble String Problem Statement   “Scramble String” problem states that you are given two strings. Check if the second string is a scrambled string of first one or not? Explanation Let string s = “great” Representation of s as binary tree by recursively dividing it into two non-empty sub-strings. This string can be ...

Question 289. Group Anagrams We have to find out the group anagrams of the given words. This means for each word we are going to sort it and store it as a key and original input which is not sorted as a value and if any other input has the same value as a ...

Question 290. Integer to English words In problem “Integer to English words” we have given a non-negative integer and the tasks to convert that integer into its numerical words or we get an input of a number, any number, and our task is to represent that number in a string form. Let’s see one example, the ...

Question 291. Find Smallest Range Containing Elements from k Lists In the problem “Find the smallest range containing elements from k lists” we have given K lists which are sorted and of the same size N. It asks to determine the smallest range that contains at least element(s) from each of the K lists. If there is more than one ...

Question 292. Minimum insertions to form a palindrome with permutations allowed The problem “Minimum insertions to form a palindrome with permutations allowed” states that you are given a String with all letters in lowercase. The problem statement asks to find out the minimum insertion of a character to a string that it can become Palindrome. The position of characters can be ...

Question 293. LCS (Longest Common Subsequence) of three strings The problem “LCS (Longest Common Subsequence) of three strings” states that you are given 3 strings. Find out the longest common subsequence of these 3 strings. LCS is the string that is common among the 3 strings and is made of characters having the same order in all of the ...

Question 294. Check if Array Contains Contiguous Integers With Duplicates Allowed You are given an array of integers which can contain duplicate elements as well. The problem statement asks to find out if it is a set of contiguous integers, print “Yes” if it is, print “No” if it is not. Example   Sample Input: [2, 3, 4, 1, 7, 9] Sample ...

Question 295. Longest Repeated Subsequence The problem “Longest Repeated Subsequence” states that you are given a string as an input. Find out the longest repeated subsequence, that is the subsequence that exists twice in the string. Example   aeafbdfdg 3 (afd) Approach   The problem asks us to find out the longest repeated subsequence in the string. ...

Question 296. Check for Palindrome after every character replacement Query The problem “Check for Palindrome after every character replacement Query” states that suppose you are given a String and no. of Queries, each query has two integer input values as i1 and i2 and one character input called ‘ch’. The problem statement asks to change the values at i1 and ...

Question 297. Letter Combinations of a Phone Number In letter combinations of a phone number problem, we have given a string containing numbers from 2 to 9. The problem is to find all the possible combinations that could be represented by that number if every number has some letters assigned to it. The assignment of the number is ...

Question 298. Longest Substring Without Repeating Characters Given a string, we have to find the length of the longest substring without repeating characters. Let’s look into a few examples: Example   pwwkew 3 Explanation: Answer is “wke” with length 3 aav 2 Explanation: Answer is “av” with length 2 Approach-1 for Longest Substring Without Repeating Characters    Brute Force  ...

Question 299. Form minimum number from given sequence The problem “Form minimum number from given sequence” states that you are given some pattern of I’s and D’s only. The meaning of I stands for increasing and for decreasing we are provided with D. The problem statement asks to print the minimum number which satisfies the given pattern. We have ...

Question 300. Find Index of Closing Bracket for a Given Opening Bracket in an Expression Problem Statement   Given a string s of length/size n and an integer value representing the index of an opening square bracket. Find index of closing bracket for a given opening bracket in an expression. Example   s = "[ABC]" index = 0 8 s = "[C-[D]]" index = 3 5 s ...

Question 301. Text Justification Problem Statement   The problem “Text Justification” states that you are given a list s[ ] of type string of size n and an integer size. Justify the text such that each line of text consists of size number of characters. You can use space(‘ ‘) as a character to complete ...

Question 302. Reverse individual words Problem Statement   The problem “Reverse individual words” states that you are given a string s. Now, print the reverse of all the individual words in the string. Example   s = "TutorialCup - changing the way of learning" puClairotuT - gnignahc eht yaw fo gninrael  s = "Reverse individual words" esreveR ...

Question 303. Remove brackets from an algebraic string containing + and – operators Problem Statement   You are given a string s of size n representing an arithmetic expression with parenthesis. The problem “Remove brackets from an algebraic string containing + and – operators” asks us to create a function that can simplify the given expression. Example   s = "a-(b+c)" a-b-c  s = a-(b-c-(d+e))-f a-b+c+d+e-f ...

Question 304. Minimum sum of squares of character counts in a given string after removing k characters Problem Statement   The problem “Minimum sum of squares of character counts in a given string after removing k characters” states that you are given a string containing lower case characters only. You are allowed to remove k characters from the string such that in the remaining string the sum of ...

Question 305. Queue based approach for first non-repeating character in a stream Problem Statement   The problem “Queue based approach for first non-repeating character in a stream” states that you are given a stream containing lower case characters, find the first non-repeating character whenever a new character is added to the stream, and if there is no non-repeating character return -1. Examples   aabcddbe ...

Question 306. Form Minimum Number From Given Sequence Problem Statement   The problem “Form Minimum Number From Given Sequence states that you are given a string s of length/size n representing a pattern of characters ‘I’ i.e. increasing and ‘D’ i.e. decreasing only. Print the minimum number for the given pattern with unique digits from 1-9. For instance – ...

Question 307. Palindrome Substring Queries Problem Statement   The problem “Palindrome Substring Queries” states that you are given a String and some queries. With those queries, you have to determine if the formed substring from that query is a palindrome or not. Example   String str = "aaabbabbaaa" Queries q[] = { {2, 3}, {2, 8},{5, 7}, ...

Question 308. Arrange given numbers to form the biggest number Problem Statement   Suppose you have an array of integers. The problem “Arrange given numbers to form the biggest number”  asks to rearrange the array in such a manner that the output should be the maximum value which can be made with those numbers of an array. Example   [34, 86, 87, ...

Question 309. Palindrome Partitioning Problem Statement   Given a string, find the minimum number of cuts required such that all the substrings of partitions are palindromes. Since we are cutting our original string into different partitions such that all the substrings are palindromes, we call this problem the Palindrome Partition Problem. Example    asaaaassss 2 Explanation: ...

Question 310. Reverse words in a string Problem Statement   “Reverse words in a string” states that you are given a string s of size n. Print the string in reverse order such that the last word becomes the first, second last becomes the second, and so on. Hereby string we refer to a sentence containing words instead ...

Question 311. Maximum weight transformation of a given string Problem Statement   The maximum weight transformation of a given string problem states that given a string consisting only of two characters ‘A’ and ‘B’. We have an operation where we can transform string to another string by toggling any character. Thus many transformations are possible. Out of all the possible ...

Question 312. Mobile Numeric Keypad Problem Problem Statement   In the mobile numeric keypad problem, we consider a numeric keypad.  We need to find all number of possible numeric sequences of given length such that you are only allowed to press buttons which are top, down, left, and right of the current button. You are not allowed ...

Question 313. Shortest Palindrome In the shortest palindrome problem, we have given a string s of length l. Add characters in front of it to make it palindrome if it’s not. Print the smallest count of characters used to make the given string a palindrome. Example   Input : s = abc Output: 2  (by ...

Question 314. Second Most Repeated Word in a Sequence Given a sequence of strings, the task is to find out the second most repeated (or frequent) word or string in a sequence. (Considering no two words are the second most repeated, there will be always a single word). Example   Input: {“aaa”, ”bb”, ”bb”, ”aaa”, ”aaa”, c”} Output: String with ...

Question 315. Maximum Occurring Character Given a string of size n containing lower case letters. We need to find the maximum occurring character in the input string. If there is more than one character with a maximum occurrence then print any of then. Example   Input: String s=”test” Output: Maximum occurring character is ‘t’. Approach 1: ...

Question 316. Decode Ways In Decode Ways problem we have given a non-empty string containing only digits, determine the total number of ways to decode it using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Example   S = “123” Number of ways to decode this string is 3 If we ...

Question 317. Edit Distance In the edit distance problem we have to find the minimum number of operations required to convert a string X of length n to another string Y of length m. Operations allowed: Insertion Deletion Substitution Example   Input: String1 = “abcd” String2 = “abe” Output: Minimum operations required is 2 ( ...

Question 318. Substring With Concatenation Of All Words In substring with the concatenation of all words problem, we have given a string s and a list consist of many words each of the same length. Print the starting index of the substring which can be the result of the concatenation of all the words in the list in ...

Question 319. Minimum Bracket Reversals In minimum bracket reversals problem, we have given a string s containing an expression of characters ‘{‘ and ‘}’ only. Find the minimum number of bracket reversals needed to make an expression balanced. Example   Input : s = “}{” Output: 2 Input : s = “{{{” Output: The given expression can not ...

Question 320. Expression Contains Redundant Bracket or Not Given a string s containing an expression of operators, operands, and parenthesis. Find if the given string contains any unnecessary parenthesis without which the expression will still give the same result. In other words, we have to find that expression contains a redundant bracket or not. Redundant Bracket   If an ...

Question 321. Check if Two Expressions With Brackets are Same Given two strings s1 and s2 representing expressions containing addition operator, subtraction operator, lowercase alphabets, and parenthesis. Check if two expressions with brackets are the same. Example   Input  s1 = “-(a+b+c)” s2 = “-a-b-c” Output  Yes Input  s1 = “a-b-(c-d)” s2 = “a-b-c-d” Output No Algorithm to Check if Two ...

Question 322. Valid Parenthesis String In the valid parenthesis string problem we have given a string containing ‘(‘, ‘)‘ and ‘*‘, check if the string is balanced if ‘*‘ can be replaced with ‘(‘, ‘)‘ or an empty string. Examples   Input “()” Output true Input “*)” Output true Input “(*))” Output true Naive Approach for ...

Question 323. Longest Palindromic Subsequence In the longest palindromic subsequence problem we have given a string, find the length of the longest palindromic subsequence. Examples   Input: TUTORIALCUP Output: 3 Input: DYNAMICPROGRAMMING Output: 7 Naive Approach for Longest Palindromic Subsequence   The naive approach to solve the above problem is to generate all the subsequences of the ...

Question 324. KMP Algorithm KMP(Knuth-Morris-Pratt) algorithm is used for pattern searching in a given string. We are given a string S and a pattern p, our goal is to determine whether or not the given pattern is present in the string. Example   Input: S = “aaaab” p = “aab” Output: true Naive Approach   The ...

Question 325. Check for Balanced Parentheses in an Expression Given a string s of length n. Check whether there is a closing parenthesis for every opening parentheses i.e. if all the parentheses are balanced. In other words, we can also say that, if we have a ‘}’, ‘)’ and ‘]’ for every ‘{‘, ‘(‘ and ‘[‘ respectively, the expression ...

Question 326. Find if an Expression has Duplicate Parenthesis or Not Given a string containing balanced parenthesis. Find if the expression/string contains duplicate parenthesis or not. Duplicate Parenthesis   When an expression is in the middle of or surrounded by the same type of balanced parenthesis i.e. enclosed between the same type of opening and closing parenthesis more than once it is ...

Question 327. Find Maximum Depth of Nested Parenthesis in a String Given a string s. Write the code to print the maximum depth of nested parenthesis in the given string. Example Input : s = “( a(b) (c) (d(e(f)g)h) I (j(k)l)m)” Output : 4 Input : s = “( p((q)) ((s)t) )” Output : 3 Using Stack   Algorithm Initialize a string s of length ...

Question 328. Balanced Expression with Replacement In Balanced Expression with Replacement problem we have given a string s containing parenthesis i.e. ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’. The string also contains x at some places as a replacement of parenthesis. Check if the string can be converted into an expression with valid parenthesis after replacing all ...

Question 329. Decode String Suppose, you are given an encoded string. A string is encoded in some kind of pattern, your task is to decode the string. Let us say, < no of times string occurs > [string ] Example   Input 3[b]2[bc] Output bbbcaca Explanation Here “b” occurs 3times and “ca” occur 2 times. ...

Question 330. Prefix to Infix Conversion In prefix to infix conversion problem, we have given expression in prefix notation. Write a program to convert it into an infix expression. Prefix Notation In this notation the operands are written after the operator. It is also known as Polish Notation. For instance : +AB is an prefix expression. ...

Question 331. Postfix to Infix Conversion In postfix to infix conversion problem, we have given expression in postfix notation. Write a program to convert the given notation in infix notation. Infix Notation In this notation, the operators are written between the operands. It is similar to how we generally write an expression. For instance: A + ...

Question 332. Prefix to Postfix Conversion In prefix to postfix conversion problem, we have given expression in prefix notation in string format. Write a program to convert the given notation in postfix notation. Prefix Notation In this notation, we write the operands after the operator. It is also known as Polish Notation. For instance: +AB is ...

Question 333. Next Permutation In the next permutation problem we have given a word, find the lexicographically greater_permutation of it. Example   input : str = "tutorialcup" output : tutorialpcu input : str = "nmhdgfecba" output : nmheabcdfg input : str = "algorithms" output : algorithsm input : str = "spoonfeed" output : Next Permutation ...

Question 334. Longest Common Subsequence You are given two strings str1 and str2, find out the length of the longest common subsequence. Subsequence: a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For ex ‘tticp‘ is the subsequence ...

Question 335. Repeated Substring Pattern In repeated substring patterns we have given a string check if it can be constructed by taking a substring of itself and appending multiple copies of the substring together. Example   Input 1: str = “abcabcabc” Output: True Explanation: “abcabcabc” can be formed by repeatedly appending “abc” to an empty string. ...

Question 336. Letter Case Permutation In letter case permutation we have given a string consisting of alphabets and numbers only, each character in the string can be converted into lowercase and uppercase, find out all different strings which can be obtained from different combinations of lowercase and uppercase of each character in the string. Example   ...

Question 337. Longest Common Prefix using Sorting In the Longest Common Prefix using Sorting problem we have given a set of strings, find the longest common prefix. i.e. find the prefix part that is common to all the strings. Example   Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”} Output: "tu" Input2: {"baggage", "banana", "batsmen"} Output: "ba" Input3: {"abcd"} Output: "abcd" ...

Question 338. Backspace String Compare In the backspace string compare problem we have given two Strings S and T, check if they are equal or not. Note that the strings contain ‘#’ which means backspace character. Examples   Input S = “ab#c” T = “ad#c” Output true (as both S and T converts to “ac”) Input ...

Question 339. Word Pattern We have all come across word patterns like “ABBA”, “AABB” and so on. We always wonder what this babble could relate to. Today we will try to solve a problem where we try to make use of the babble. A plethora of string problems does not help the case. Given ...

Question 340. Regular Expression Matching In the Regular Expression Matching problem we have given two strings one (let’s assume it x) consists of only lower case alphabets and second (let’s assume it y) consists of lower case alphabets with two special characters i.e, “.” and “*”. The task is to find whether the second string ...

Question 341. Reorganize String In Reorganize String problem we have given a string containing some characters “a-z” only. Our task is to rearrange those characters such that no two same characters are adjacent to each other. Example   Input apple Output pelpa Input book Output obko Input aa Output not possible Input aaab Output not ...

Question 342. String Compression In the String Compression problem, we have given an array a[ ] of type char. Compress it as the character and count of a particular character (if the count of character is 1 then the only character is stored in a compressed array). The length of the compressed array should ...

Question 343. Valid Parentheses In Valid Parentheses problem we have given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. ( ) [ ] { } ...

Question 344. Longest Common Prefix using Trie In the Longest Common Prefix using Trie problem we have given a set of strings, find the longest common prefix. i.e. find the prefix part that is common to all the strings. Example   Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”} Output: "tu" Input2: {"baggage", "banana", "batsmen"} Output: "ba" Input3: {"abcd"} Output: "abcd" ...

Question 345. Valid Number In the Valid Number problem we have given a string, check if it can be interpreted into a valid decimal number. It is to be noted that, for a given string to be interpreted as a valid decimal number. It should contain the following characters: Numbers 0-9 Exponent – “e” ...

Question 346. Find the Closest Palindrome number Problem   In Find the Closest Palindrome number problem we have given a number n. Find a number which is a palindrome and the absolute difference between the palindromic number and n is as minimum as possible except zero. If there is more than one number satisfying this condition then print ...

Question 347. Count and Say Count and Say in which we have given a number N and we need to find the Nth term of the count and say sequence. Firstly we need to understand what is count and say sequence. Firstly see some terms of the sequence: 1st term is “1”. 2nd term is ...

Question 348. Find unique character in a string In Find unique character in a string problem, we have given a string containing only lower case alphabets(a-z). We need to find the first non-repeating character in it and print the index. if no such character exists print -1. Input Format   Only a single line containing string. Output Format   Print ...

Question 349. Integer to Roman Integer to Roman conversion. We have given a number N and we need to print the Roman number of N. Roman numbers are represented by the use of {I, V, X, L, C, D, M} values. Let’s see some examples for good understanding. Input Format   Only a single line containing ...

Question 350. Rabin Karp Algorithm Rabin Karp Algorithm used to find the pattern string in the given text string. There are so many types of algorithms or methods used to find the pattern string. In this algorithm, we use Hashing for finding the pattern matching. If we got the same hash code for the substring ...

Question 351. Guess The Word Guess The Word is an interactive problem. An interactive problem means the data which is given to us is not predetermined. We can print values or call the specific function to interact or get more information regarding the solution. After each step, we also need to FLUSH the buffer to ...

Question 352. Distinct Subsequences Given two strings S and P1, we have to count all the number of distinct subsequences of S which equals P1. Note: A subsequence of a given string is a string that we archive by deleting some characters or possible zero characters also from the original string. We can’t change ...

Question 353. Isomorphic Strings Isomorphic Strings – Given two strings we need to check if for every occurrence of a character in string1 there is a unique mapping with characters in string2. In short, check, if there is one to one mapping or not. Example   Input str1 = “aab” str2 = “xxy” Output True ...

Question 354. Perform String Shifts Leetcode A shift is a process in which alphabets are incremented by 1 in their ASCII value. For the last alphabet z it starts again i.e. shift of z will be a. In perform string shifts leetcode problem we have Given a string s (lowercase characters only) and an array a[ ...

Question 355. String comparison containing wildcards In String comparison containing wildcards problem, we have given two strings second string contains small alphabets and the first contains small alphabets and some wildcard patterns.  Wildcard patterns are: ?: we can replace this wildcard with any small alphabet. *: we can replace this wildcard with any string. An empty ...

Question 356. Check whether Strings are K Distance Apart or Not Problem Statement   Given two strings and an integer k, write a program to check whether the given strings are k distance apart or not. That is if any character is mismatched or any character is to be removed then it is known as k distance apart. Input Format   The first ...

Question 357. Generate all Binary Strings Without Consecutive 1’s Problem Statement   In the “Generate all binary strings without consecutive 1’s” problem we have given an integer k, write a program to print all binary strings of size k with no consecutive 1’s. Input Format   The first and only one line containing an integer N. Output Format   Print all possible ...

Question 358. Sort a String According to Another String Problem Statement   Given two input strings, a pattern and a string. We need to sort the string according to the order defined by the pattern. Pattern string has no duplicates and it has all characters of the string. Input Format   The first line containing a string s which we need ...

Question 359. Check if String Follows Order of Characters by a Pattern or not Problem Statement   In the “Check if String Follows Order of Characters by a Pattern or not” problem we have to check if characters in the given input string follow the same order as determined by characters present in the given input pattern then print “Yes” else print “No”. Input Format   ...

Question 360. Reverse String Without Temporary Variable Problem Statement   In the “Reverse String Without Temporary Variable” problem we have given a string “s”. Write a program to reverse this string without using any extra variable or space. Input Format   The first line containing the given string “s”. Output Format   Print the string which is reverse of the ...

Question 361. Print all Palindromic Partitions of a String Problem Statement   In the “Print all Palindromic Partitions of a String” problem we have given a string “s”. Write a program to print all possible palindromic partitioning of s. A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as ...

Question 362. Count the Pairs at Same Distance as in English Alphabets Problem Statement   In the “Count of Pairs at Same Distance as in English Alphabets” problem we have given a string “s”. Write a program that will print the number of pairs whose elements are at the same distance as in English alphabets. Input Format   The first line containing the given ...

Question 363. Minimum Characters to be Added at Front to Make String Palindrome Problem Statement   In the “Minimum Characters to be Added at Front to Make String Palindrome” problem we have given a string “s”. Write a program to find the minimum characters to be added at the front to make a string palindrome. Input Format   The first and only one line containing ...

Question 364. Kth Non-repeating Character Problem Statement   In the “Kth Non-repeating Character” we have given a string “s”. Write a program to find out the kth non-repeating_character. If there are less than k character which is non-repeating in the string then print “-1”. Input Format   The first and only one line containing a string “s”. ...

Question 365. Remove Minimum Characters so that Two Strings Become Anagrams Problem Statement   In the “Remove Minimum Characters so that Two Strings Become Anagrams” problem we have given two input strings. Find the minimum number of_characters to be removed from these two strings such that, they become anagrams. Input Format   The first line containing a string “s”. The second line containing ...

Question 366. Generate all Binary Strings from Given Pattern Problem Statement   In the “Generate all Binary Strings from Given Pattern” problem we have given input string “s” consists of 0, 1, and ? (wildcard char). We need to generate all possible binary strings by replacing ? with ‘0’ and ‘1’. Input Format   The first and only one line containing ...

Question 367. Print all Possible Ways to Break a String in Bracket Form Problem Statement   In the “Print all Possible Ways to Break a String in Bracket Form” problem, we have given a string “s”. Find all possible ways to break the given string in bracket form. Enclose all substrings within brackets (). Input Format   The first and only one line containing a ...

Question 368. Caesar Cipher Description   The Caesar Cipher technique is one of the earliest techniques of encryption. Here, for each letter in the given text, it is replaced by a letter some fixed number of positions down the alphabet. If n = 1, replace A with by B, B would become C, and so ...

Question 369. Longest Palindrome can be Formed by Removing or Rearranging Characters Problem Statement   In the “Longest Palindrome can be Formed by Removing or Rearranging Characters” problem we have given a string “s”. Find the longest palindrome that can be constructed by removing or rearranging some characters or possibly zero characters from the string. There may be multiple solutions possible, you can ...

Question 370. Longest Common Prefix Word by Word Matching Problem Statement   In the “Longest Common Prefix using Word by Word Matching” problem, we have given N strings.  Write a program to find the longest common prefix of the given strings. Input Format   The first line containing an integer value N which denotes the number of strings. Next N lines ...

Question 371. Longest Common Prefix using Character by Character Matching Problem Statement   In the “Longest Common Prefix using Character by Character Matching” problem we have given an integer value N and N strings. Write a program to find the longest common prefix of the given strings. Input Format   The first line containing an integer value N which denotes the number ...

Question 372. Permutations of a Given String Using STL Problem Statement   In the “Permutations of a Given String Using STL” problem, we have given a string “s”. Print all the permutations of the input string using STL functions. Input Format   The first and only one line containing a string “s”. Output Format   Print all the permutation of the given ...

Question 373. Longest Common Prefix using Divide and Conquer Problem Statement   In the “Longest Common Prefix using Divide and Conquer ” problem, we have given an integer n and n strings. Write a program that will print the longest common prefix. If there is no common prefix then print “-1”. Input Format   The first line contains an integer n. ...

Question 374. Longest Common Prefix Using Binary Search II Problem Statement   In the “Longest Common Prefix Using Binary Search II” problem we have given an integer value N and N strings. Write a program that will print the longest common prefix of given strings. If there is no common prefix then print “-1”. Input Format   The first line containing ...

Question 375. Palindrome Permutations of a String Problem Statement   In the “Palindrome Permutations of a String” problem, we have given an input string “s”. Print all the possible palindromes that can be generated using the characters of the string. Input Format   The first and only one line containing a string “s”. Output Format   Print all the possible ...

Question 376. Check if Two given Strings are Isomorphic to each other Problem Statement   In the “Check if Two given Strings are Isomorphic to each other” problem we have given two strings s1 and s2. Write a program that says whether the given strings are isomorphic or not. Note: Two strings are said to be isomorphic if there is a one to ...

Question 377. Length of Longest valid Substring Problem Statement   In the “Length of Longest valid Substring” we have given a string that contains the opening and closing parenthesis only. Write a program that will find the longest valid parenthesis substring. Input Format   The first and only one line containing a string s. Output Format   The first and ...

Question 378. Form Minimum Number from Given Sequence of D’s and I’s Problem Statement   In the “Form Minimum Number from Given Sequence of D’s and I’s” problem, we have given a pattern containing only I’s and D’s. I for increasing and D for decreasing. Write a program to print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat. Input Format   ...

Question 379. Arrange given Numbers to Form the Biggest Number II Problem Statement   In the “Arrange given Numbers to Form the Biggest Number II” problem, we have given an array of positive integers.  Arrange them in such a way that the arrangement will form the largest value. Input Format   The first and only one line containing an integer n. Second-line containing ...

Question 380. Check if a Linked list of Strings form a Palindrome Problem Statement   In the “Check if a Linked list of Strings form a Palindrome” problem we have given a linked list handling string data. Write a program to check whether the data forms a palindrom or not. Example   ba->c->d->ca->b 1 Explanation: In the above example we can see that the ...

## Tree Questions Amazon

Question 381. Root to Leaf path with target sum Leetcode Solutions A binary tree and an integer K are given. Our goal is to return whether there is a root-to-leaf path in the tree such that it’s sum is equal to the target-K. The sum of a path is the sum of all nodes that lie on it. 2 / \ ...

Question 382. Scramble String Problem Statement   “Scramble String” problem states that you are given two strings. Check if the second string is a scrambled string of first one or not? Explanation Let string s = “great” Representation of s as binary tree by recursively dividing it into two non-empty sub-strings. This string can be ...

Question 383. Queries for Number of Distinct Elements in a Subarray We have given an array of integer and a number of queries and we have to find out the number of all the distinct elements we have within the given range, the query consists of two numbers left and right, this is the given range, with this given range we ...

Question 384. Morris Traversal Morris traversal is a method to traverse the nodes in a binary tree without using stack and recursion. Thus reducing the space complexity to linear. Inorder Traversal   Example 9 7 1 6 4 5 3 1           /    \         2    ...

Question 385. Kth ancestor of a node in binary tree Problem Statement   The problem “Kth ancestor of a node in binary tree” states that you are given a binary tree and a node. Now we need to find the kth ancestor of this node. An ancestor of any node is the nodes that lie on the path from the root ...

Question 386. Inorder Successor of a node in Binary Tree Problem Statement   The problem asks to find “Inorder Successor of a node in Binary Tree”. An inorder successor of a node is a node in the binary tree that comes after the given node in the inorder traversal of the given binary tree. Example      Inorder successor of 6 is ...

Question 387. Check if a given array can represent Preorder Traversal of Binary Search Tree The problem “Check if a given array can represent Preorder Traversal of Binary Search Tree” states that you are given a preorder traversal sequence. Now consider this sequence and find out if this sequence can represent a binary search tree or not? The expected time complexity for the solution is ...

Question 388. Construct Binary Tree from given Parent Array representation The problem “Construct Binary Tree from given Parent Array representation” states that you are given an array. This input array represents a binary tree. Now you need to construct a binary tree on the basis of this input array. The array stores the index of parent node at each index. ...

Question 389. Given a binary tree, how do you remove all the half nodes? The problem “Given a binary tree, how do you remove all the half nodes?” states that you are given a binary tree. Now you need to remove the half nodes. A half node is defined as a node in the tree that has only a single child. Either it is ...

Question 390. Iterative Preorder Traversal The problem “Iterative Preorder Traversal” states that you are given a binary tree and now you need to find the preorder traversal of the tree. We are required to find the preorder traversal using iterative method and not the recursive approach. Example     5 7 9 6 1 4 3 ...

Question 391. Find distance between two nodes of a Binary Tree Problem Statement   The problem “Find distance between two nodes of a Binary Tree” states that you are given a binary tree and you are given two nodes. Now you need to find the minimum distance between these two nodes. Example   // Tree is shown using the image above node 1 ...

Question 392. Write Code to Determine if Two Trees are Identical The problem “Write Code to Determine if Two Trees are Identical” states that you are given two binary trees. find out if they are identical or not? Here, identical tree means that both the binary trees have the same node value with the same arrangement of nodes. Example   Both trees ...

Question 393. Boundary Traversal of binary tree Problem Statement   The problem “Boundary Traversal of binary tree” states that you are given a binary tree. Now you need to print the boundary view of a binary tree. Here boundary traversal means that all the nodes are shown as the boundary of the tree. The nodes are seen from ...

Question 394. Diagonal Traversal of Binary Tree Problem Statement   The problem “Diagonal Traversal of Binary Tree” states that you are given a binary tree and now you need to find the diagonal view for the given tree. When we see a tree from the top-right direction. The nodes which are visible to us is the diagonal view ...

Question 395. Bottom View of a Binary Tree Problem Statement   The problem “Bottom View of a Binary Tree” states that you are given a binary tree and now you need to find the bottom view for the given tree. When we see a tree from the downward direction. The nodes which are visible to us is the bottom ...

Question 396. Print Right View of a Binary Tree Problem Statement   The problem “Print Right View of a Binary Tree” states that you are given a binary tree. Now you need to find the right view of this tree. Here, right view of the binary tree means to print the sequence as the tree looks when looked from the ...

Question 397. Range LCM Queries Problem Statement   The problem “Range LCM Queries” states that you have an integer array and q number of queries. Each query contains the (left, right) as a range. The given task is to find out the LCM(left, right), i.e, LCM of all the number that comes in the range of ...

Question 398. Find Maximum Level sum in Binary Tree Problem Statement   The problem “Find Maximum Level sum in Binary Tree” states that you are given a binary tree with positive and negative nodes, find the maximum sum of a level in the binary tree. Example   Input 7 Explanation First Level : Sum = 5 Second Level : Sum = ...

Question 399. Red-Black Tree Introduction Red Black Tree is a self-balancing binary tree. In this tree, every node is either a red node or a black node. In this Red-black Tree Introduction, we will try to cover all of its basic properties. Properties of Red-Black Tree   Every node is represented as either red or black. ...

Question 400. Binary Search Tree Delete Operation Problem Statement   The problem “Binary Search Tree Delete Operation” asks us to implement the delete operation for binary search tree. Delete function refers to the functionality to delete a node with a given key/data. Example   Input Node to be deleted = 5 Output Approach for Binary Search Tree Delete Operation   So ...

Question 401. Iterative Method to find Height of Binary Tree Problem Statement   The problem “Iterative Method to find Height of Binary Tree” states that you are given a binary tree, find the height of the tree using the iterative method. Examples   Input 3 Input 4 Algorithm for Iterative Method to find Height of Binary Tree   The height of a tree ...

Question 402. Clone a Binary Tree with Random Pointers Problem Statement   You are given a complete binary tree with some random pointers. Random pointers are referred to nodes which every node points to other than its left and right child. So, this also changes the standard structure of a node in a simple binary tree. Now the node of ...

Question 403. Level order traversal using two Queues Problem Statement   The problem “Level order traversal using two Queues” states that you are given a binary tree, print its level order traversal line by line. Examples   Input 5 11 42 7 9 8 12 23 52 3 Input 1 2 3 4 5 6 Algorithm for Level Order Traversal ...

Question 404. Check if all levels of two Binary Tree are anagrams or not Problem Statement   The problem “Check if all levels of two Binary Tree are anagrams or not” says that you are given two Binary Trees, check if all the levels of the two trees are anagrams or not. Examples   Input true Input false Algorithm to Check if all levels of two ...

Question 405. Check if the given array can represent Level Order Traversal of Binary Search Tree Problem Statement   The problem “Check if the given array can represent Level Order Traversal of Binary Search Tree” states that you are given a level order traversal of the binary search tree. And using the level order traversal of the tree. We need to efficiently find if the level order ...

Question 406. Number of siblings of a given Node in n-ary Tree Problem Statement   The problem “Number of siblings of a given Node in n-ary Tree” states that you are given an n-ary Tree and a target node. Find the number of siblings of the target node. Assume that node is always present in the tree and the first node is the ...

Question 407. Convert BST into a Min-Heap without using array Problem Statement   “Convert BST into a Min-Heap without using array” problem states that you are given a BST (binary search tree) and you need to convert it into a min-heap. The min-heap should contain all the elements in the binary search tree. The algorithm should run in linear time complexity. ...

Question 408. Merge two BSTs with limited extra space Problem Statement   The problem “Merge two BSTs with limited extra space” states that you are given two binary search tree(BST) and you need to print the elements from both the trees in sorted order. That is in such an order that it seems that elements are from a single BST. ...

Question 409. Iterative Postorder Traversal Using Two Stacks Problem Statement   The problem “Iterative Postorder Traversal Using Two Stacks” states that you are given a binary tree with n nodes. Write the program for it’s iterative postorder traversal using two stacks. Example   Input   4 5 2 6 7 3 1 Input   4 2 3 1 Algorithm   Create ...

Question 410. Binary Tree to Binary Search Tree Conversion using STL set Problem Statement   We are given a binary tree and we need to convert it into a binary search tree. The problem “Binary Tree to Binary Search Tree Conversion using STL set” asks to do conversion using STL set. We have already discussed converting the binary tree into BST but we ...

Question 411. K’th Largest element in BST using constant extra space Problem Statement   “K’th Largest element in BST using constant extra space” states that you are given a binary search tree and you need to find the kth largest element in it. So if we arrange the elements of the binary search tree in descending order then we need to return ...

Question 412. K’th Largest Element in BST when modification to BST is not allowed Problem Statement   “K’th Largest Element in BST when modification to BST is not allowed” states that you are given a binary search tree and you need to find the kth largest element. This means that when all the elements of the binary search tree are arranged in descending order. Then ...

Question 413. Iterative method to find ancestors of a given binary tree Problem Statement   “Iterative method to find ancestors of a given binary tree” problem states that you are given a binary tree and an integer representing a key. Create a function to print all the ancestors of the given key using iteration. Example   Input  key = 6 5 2 1 Explanation: ...

Question 414. Check if each internal node of a BST has exactly one child Problem Statement   “Check if each internal node of a BST has exactly one child” problem states that you are given a preorder traversal of a binary search tree. And you need to find if all the non-leaf nodes contain only a single child. Here we also consider that all the ...

Question 415. Find k-th smallest element in BST (Order Statistics in BST) Problem Statement   “Find k-th smallest element in BST (Order Statistics in BST)” problem states that you are given a binary search tree and you need to find the k-th smallest number in the BST. This means if we do an in-order traversal of the binary search tree and store the ...

Question 416. Vertical sum in a given binary tree Problem Statement   “Vertical sum in a given binary tree” problem states that you are given a binary tree and we need to find the sum of each vertical level. By vertical level, we mean if we draw vertical lines at a distance of 1 unit in the left and right ...

Question 417. A program to check if a binary tree is BST or not Problem Statement   “A program to check if a binary tree is BST or not” states that you are given a binary tree and you need to check if the binary tree satisfies the properties of the binary search tree. So, the binary tree has the following properties:  The left subtree ...

Question 418. Maximum Depth Of Binary Tree Problem Statement   “Maximum depth of binary tree” problem states that you are given a binary tree data structure. Print the maximum depth of the given binary tree. Example   Input 2 Explanation: Maximum depth for the given tree is 2. Because there is only a single element below the root (i.e. ...

Question 419. Convert BST to Min Heap Problem Statement   Given a complete Binary Search Tree, write an algorithm to convert it into a Min Heap, which is to convert BST to Min Heap. The Min Heap should be such that the values on the left of a node must be less than the values on the right ...

Question 420. Merge Two Balanced Binary Search Trees Problem Statement   Given Two Balanced Binary Search Trees, there are n elements in the first BST and m elements in the second BST. Write an algorithm to merge two balanced binary search trees to form a third balanced Binary Search Tree with (n + m) elements. Example   Input Output Pre-order ...

Question 421. Binary Search Tree Search and Insertion Problem Statement   Write an algorithm to perform searching and insertion in Binary Search Tree. So what we are going to do is insert some of the elements from input into a binary search tree. Whenever asked to search a particular element, we’ll be searching it among the elements in BST(short ...

Question 422. Check given array of size n can represent BST of n levels or not Problem Statement   Given an array with n elements, check given array of size n can represent BST of n levels or not. That is to check whether the binary search tree constructed using these n elements can represent a BST of n levels. Examples   arr[] = {10, 8, 6, 9, ...

Question 423. Binary Tree to Binary Search Tree Conversion In binary tree to binary search tree conversion problem, we have given a binary tree convert it to Binary Search Tree without changing the structure of the tree. Example   Input Output pre-order : 13 8 6 47 25 51 Algorithm   We do not have to change the structure of the ...

Question 424. Sorted Linked List to Balanced BST In sorted linked list to balanced BST problem, we have given a singly Linked list in sorted order, construct a Balanced Binary Tree from the singly Linked List. Examples   Input 1 -> 2 -> 3 -> 4 -> 5 Output Pre-order : 3 2 1 5 4 Input 7 -> ...

Question 425. Sorted Array to Balanced BST In sorted array to balanced BST problem, we have given an array in sorted order, construct a Balanced Binary Search Tree from the sorted array. Examples   Input arr[] = {1, 2, 3, 4, 5} Output Pre-order : 3 2 1 5 4 Input arr[] = {7, 11, 13, 20, 22, ...

Question 426. Transform a BST to Greater sum Tree In transform a BST to greater sum tree Given a Binary Search Tree write an algorithm to convert it to a greater sum tree, that is, transform each node to contain the sum of all the elements greater than it. Example   Input Output Pre-order : 69 81 87 34 54 ...

Question 427. Advantages of BST over Hash Table The most commonly used operations on any data structure are insertion, deletion, and searching. Hash Table is able to perform these three operations with the average time complexity of O(1), while self-balancing Binary Search Trees take O(log n) time complexity. At first, it seems as Hash Tables are better than ...

Question 428. Construct BST from its given Level Order Traversal Given the level order traversal of a Binary Search Tree, write an algorithm to construct the Binary Search Tree or BST from ITS given level order traversal. Example   Input levelOrder[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31} Output In-order : 5 8 9 12 15 18 ...

Question 429. Construct BST from given Preorder Traversal Given a pre-order traversal of a Binary Search Tree(BST), write an algorithm to construct the BST from given preorder traversal. Examples   Input   preOrder[] = {7, 5, 3, 6, 9} Output Inorder : 3 5 6 7 9 Input preOrder[] = {12, 6, 1, 35, 20} Output Inorder : 1 6 ...

Question 430. Find the node with minimum value in a Binary Search Tree Given a Binary Search Tree, write an algorithm to find the node with the minimum value in a given binary search tree. Example   Input Output 5 Naive Approach   A simple approach is to do a tree traversal and find the node with the minimum value among all the nodes. This ...

Question 431. Construct Binary Tree from Given Inorder and Preorder Traversals In this problem, we have inorder and preorder of the binary tree. We need to construct a binary tree from the given Inorder and Preorder traversals. Example   Input: Inorder= [D, B, E, A, F, C] Preorder= [A, B, D, E, C, F] Output: Pre-order traversal of the tree formed by ...

Question 432. Print Ancestors of a Given Binary Tree Node Without Recursion Given a binary tree and a specific node or key. Print ancestors of a given binary tree node without recursion. Example   Input : key = 7 Output : 3 1 Input : key = 4 Output : 2 1 Algorithm for Ancestors of a Given Binary Tree Node   Create a class Node ...

Question 433. Level order Traversal in Spiral Form In this problem we have given a binary tree,  print its level order traversal in a spiral form. Examples   Input Output 10 30 20 40 50 80 70 60 Naive Approach for Level order Traversal in Spiral Form   The idea is to do a normal level order traversal using a ...

Question 434. Kth Smallest Element in a BST In this problem, we have given a BST and a number k, find the kth smallest element in a BST. Examples   Input tree[] = {5, 3, 6, 2, 4, null, null, 1} k = 3 Output 3 Input tree[] = {3, 1, 4, null, 2} k = 1 Output 1 ...

Question 435. Balanced Binary Tree In the balanced binary tree problem, we have given the root of a binary tree. We have to determine whether or not it is height balance. Examples   Input Output true Input Output: false Balanced Binary Tree   Every node in a balanced binary tree has a difference of 1 or less ...

Question 436. Interval Tree In the interval tree problem, we have given a set of intervals and three types of queries addInterval(x,y): Add an interval (x,y) to the set removeInterval(x,y): Remove an interval (x,y) from the set checkInterval(x,y): Check if interval (x,y) overlaps with some existing interval Design a data structure( Interval Tree ) ...

Question 437. Construct Complete Binary Tree from its Linked List Representation Given the linked list representation of a complete binary tree. The linked list is in the order of level order traversal of the tree. Write an algorithm to construct the complete binary tree back from its linked list representation. Example   Input 1 -> 2 -> 3 -> 4 -> 5 ...

Question 438. Lowest Common Ancestor Given the root of a binary tree and two nodes n1 and n2, find the LCA(Lowest Common Ancestor) of the nodes. Example   What is Lowest Common Ancestor(LCA)?   The ancestors of a node n are the nodes present in the path between root and node. Consider the binary tree shown in ...

Question 439. Lowest Common Ancestor in Binary Search Tree Given the root of a binary search tree and two nodes n1 and n2, find the LCA(Lowest Common Ancestor) of the nodes in a given binary search tree. Example   Naive Approach for Lowest Common Ancestor in Binary Search Tree   Find the LCA(n1, n2) using the optimal approach to find LCA ...

Question 440. Segment Tree If we have performing addition on a given range of array whose element values updated any time. Then in that type of problem, we handle using a segment tree structure. Given an array a[] with n elements and you have to answer multiple queries, each of the queries is one ...

Question 441. Print a Binary Tree in Vertical Order In this problem, we have given a pointer denoting the root of the binary tree and your task is to print the binary tree in the vertical order. Example   Input 1 / \ 2 3 / \ / \ 4 5 6 7 \ \ 8 9 Output 4 2 ...

Question 442. Binary Search Tree A binary search tree is a Binary tree with some rules that allows us to maintain the data in a sorted fashion. As it is a binary tree hence, a node can have at max 2 children. Structure of a Binary Search Tree node     Rules for Binary tree to ...

Question 443. Maximum Binary Tree In this problem, we have given an array a[ ] of size n. Create the maximum binary tree from the array and return its root node. It is made from the array using the following steps : The root node of the tree should be the maximum value in the given ...

Question 444. Binary Tree zigzag level order Traversal Given a binary tree, print the zigzag level order traversal of its node values. (ie, from left to right, then right to left for the next level and alternate between). Example   consider the binary tree given below Below is the zigzag level order traversal of the above binary tree Types ...

Question 445. Recover Binary Search Tree Consider a binary search tree, two nodes of the tree have been swapped, design an algorithm to recover the binary search Tree. Example Consider the binary search tree given below whose two nodes have been swapped as input. Incorrect nodes on the BST are detected(highlighted) and then swapped to obtain ...

Question 446. Populating Next Right Pointers in Each Node Given a Binary Tree, connect nodes that are at the same level from left to right. Structure of the Tree Node: A node of the tree contains 4 components which are data(integer value), pointers(next, left and right) of the tree node type. next pointer of a node point towards its ...

Question 447. Top View of Binary Tree The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, the Output top view of the binary tree from the left-most horizontal level to the rightmost horizontal level. Example   Example 1 Example 2 Types of ...

Question 448. Level of Each node in a Tree from source node Given a tree (an acyclic fully connected graph where constituent nodes are connected by bidirectional edges) and a source node. find the level of each node in a tree form source node. It is given that level of a node v with respect to the source is the distance between ...

Question 449. Find Duplicate Subtrees Duplicate Subtrees    Subtrees are said to be duplicate if they have the same node values and structure. Given a binary tree with n nodes. Find all the duplicate subtrees and return their root node. Example   Here, the subtrees 4 and 2->4 appear more than once therefore we will return root ...

Question 450. Symmetric Tree In Symmetric Tree problem we have given a binary tree, check whether it is a mirror of itself. A tree is said to be a mirror image of itself if there exists an axis of symmetry through a root node that divides the tree into two same halves. Example   Types ...

Question 451. Longest Common Prefix using Trie In the Longest Common Prefix using Trie problem we have given a set of strings, find the longest common prefix. i.e. find the prefix part that is common to all the strings. Example   Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”} Output: "tu" Input2: {"baggage", "banana", "batsmen"} Output: "ba" Input3: {"abcd"} Output: "abcd" ...

Question 452. Convert Sorted List to Binary Search Tree Problem   Given a linked list. The elements of the linked list are in increasing order. Convert the given linked list into a highly balanced binary search tree. A highly balanced binary search tree is a binary search tree in which the difference between the depth of two subtrees of any ...

Question 453. Validate Binary Search Tree Problem   In Validate Binary Search Tree problem we have given the root of a tree, we have to check if it is a binary search tree or not. Example : Output: true Explanation: The given tree is a binary search tree because all elements which are left to each subtree ...

Question 454. Path Sum What is Path Sum Problem?   In the Path Sum problem, we have given a binary tree and an integer SUM. We have to find if any path from the root to leaf has a sum equal to the SUM. Path sum is defined as the sum of all the nodes ...

Question 455. Level Order Traversal of Binary Tree Level Order Traversal of a given binary tree is the same as the BFS of the binary tree. Do we already know about what actually BFS is? if not then don’t need to feel bad just read the whole article and visit our previous articles for better understanding. BFS is a ...

Question 456. Tree Traversal (Preorder, Inorder & Postorder) First, we need to know about what is Traversal in Binary Tree. Traversal is a type of method in which we visit all the nodes exactly once in some specific manner/order. Basically there are two types of traversal in Binary Tree: Breadth-First Traversal Depth  First Traversal We already know about ...

Question 457. Deletion in a Binary Tree Do we already know about what actually Binary Tree is? Now in this post, we are focusing on how to delete a node whose value is given. We are sure that the value of the node which we want to delete is always present before deletion in BT. In Binary ...

Question 458. Unique Binary Search Trees Firstly we have to find the total number of counts to form a unique binary search tree. After it, we construct all possible unique BST. First of all, we have to know the construction of BST. In a Binary Search Tree, the nodes present in the left subtree wrt. any ...

Question 459. BFS vs DFS for Binary Tree Breadth First Search (BFS)   Do we already know about what actually BFS is? if not then don’t need to feel bad just read the whole article and visit our previous article on Breadth First Search for better understanding. BFS is a level order traversal in which we visit the nodes of ...

## Graph Questions Amazon

Question 460. Find the Town Judge Leetcode Solution Problem Statement   In this problem, we are given n people labelled from 1 to n. We are also given a 2d array trust[][] shows that trust[i]th people trusts trust[i]th people for each 0 <= i < trust.length. We have to find a person “town judge” who does not trust any ...

Question 461. Find the smallest binary digit multiple of given number Problem Statement   The problem “Find the smallest binary digit multiple of given number” states that you are given a decimal number N. So find the smallest multiple of N that contains only the binary digits ‘0’ and ‘1’. Example   37 111 A detailed explanation can be found below in the ...

Question 462. Minimum Operations to convert X to Y Problem Statement   The problem “Minimum Operations to convert X to Y” states that you are given two numbers X and Y, it is needed to convert X into Y using following operations: Starting number is X. Following operations can be performed on X and on the numbers that are generated ...

Question 463. Check if two nodes are on the same path in a Tree Problem Statement   The problem “Check if two nodes are on the same path in a Tree” states that you are given a n-ary tree (directed acyclic graph) rooted at root node with uni-directional edges between it’s vertices. You are also given a list of queries q. Each query in list ...

Question 464. Distance of nearest cell having 1 in a binary matrix Problem Statement   The problem “Distance of nearest cell having 1 in a binary matrix” states that you are given a binary matrix(containing only 0s and 1s) with at least one 1. Find the distance of the nearest cell having 1 in the binary matrix for all the elements of the ...

Question 465. Transpose Graph Problem Statement   The problem “Transpose graph” states that you are given a graph and you need to find the transpose of the given graph. Transpose: Transpose of a directed graph produces another graph with same edge & node configurations but the direction of all the edges have been reversed. Example   ...

Question 466. BFS for Disconnected Graph Problem Statement   The problem “BFS for Disconnected Graph” states that you are given a disconnected directed graph, print the BFS traversal of the graph. Example   The BFS traversal of the graph above gives: 0 1 2 5 3 4 6 Approach   Breadth first Search (BFS) traversal for Disconnected Directed Graph ...

Question 467. Minimum Steps to reach target by a Knight Description   The problem “Minimum Steps to reach target by a Knight” states that you are given a square chess board of N x N dimensions, co-ordinates of the Knight piece, and the target cell. Find out the minimum number of steps taken by the Knight piece to reach the target ...

Question 468. Iterative Depth First Traversal of Graph In iterative depth first traversal of graph problem, we have given a graph data structure. Write the program to print the depth first traversal of the given graph using the iterative method. Example   Input : 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 ...

Question 469. Evaluate Division In evaluate division problem we have given some equations, in the form, A/B = k, where A and B are strings and k is a real number. Answer some queries, if the answer does not exist return -1. Example   Input: equations: a/b = 2.0 and b/c = 3.0 queries: a/c ...

Question 470. Prim’s Algorithm Prim’s algorithm is used to find the Minimum Spanning Tree(MST) of a connected or undirected graph. Spanning Tree of a graph is a subgraph that is also a tree and includes all the vertices. Minimum Spanning Tree is the spanning tree with a minimum edge weight sum. Example   Graph Minimum ...

Question 471. Max Area of Island Problem Description: Given a 2D matrix, the matrix has only 0(representing water)  and 1(representing land) as entries. An island in the matrix is formed by grouping all the adjacent 1’s connected 4-directionally(horizontal and vertical). Find the maximum area of the island in the matrix. Assume that all four edges of ...

Question 472. Graph Cloning What is Graph Cloning?   Today we have with us a reference to an undirected graph. What do we have to do? Returning a deep copy of the provided graph. Let us look at the structure: The Class Node: It consists of the data value and the neighbors associated with each ...

Question 473. Topological Sorting Given a directed acyclic graph, topologically sort the graph nodes. Topological Sorting Example   Topological sorting of above graph is -> {1,2,3,0,5,4} Theory Topological Sorting is done for a Directed Acyclic Graph (DAG). A DAG has no cycles in it. ie, there is no such path starting from any node of ...

Question 474. Breadth First Search (BFS) for a Graph Breadth First Search (BFS) for a graph is a traversing or searching algorithm in tree/graph data structure. It starts at a given vertex(any arbitrary vertex) and explores all the connected vertex and after that moves to the nearest vertex and explores all the unexplored nodes and takes care that no ...

Question 475. Dijkstra Algorithm Dijkstra is the shortest path algorithm. Dijkstra algorithm is used to find the shortest distance of all nodes from the given start node. It logically creates the shortest path tree from a single source node, by keep adding the nodes greedily such that at every point each node in the ...

## Stack Questions Amazon

Question 476. Min Stack Leetcode Solution Problem Statement   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. ...

Question 477. Next Greater Element I Leetcode Solution Problem Statement   In this problem, we are given two lists in which first list is subset of second list. For each element of first list, we have to find out next greater element in the second list. Example nums1 = [4,1,2], nums2 = [1,3,4,2] [-1,3,-1] Explanation: for first element of list1 i.e. for 4 there ...

Question 478. Check if a given array can represent Preorder Traversal of Binary Search Tree The problem “Check if a given array can represent Preorder Traversal of Binary Search Tree” states that you are given a preorder traversal sequence. Now consider this sequence and find out if this sequence can represent a binary search tree or not? The expected time complexity for the solution is ...

Question 479. Form minimum number from given sequence The problem “Form minimum number from given sequence” states that you are given some pattern of I’s and D’s only. The meaning of I stands for increasing and for decreasing we are provided with D. The problem statement asks to print the minimum number which satisfies the given pattern. We have ...

Question 480. Range Queries for Longest Correct Bracket Subsequence You are given a sequence of some brackets subsequence, in other words, you are given brackets like ‘(’ and ‘)’ and you are given a query range as a starting point and ending point. The problem “Range Queries for Longest Correct Bracket Subsequence” asks to find out the maximum length ...

Question 481. Find Index of Closing Bracket for a Given Opening Bracket in an Expression Problem Statement   Given a string s of length/size n and an integer value representing the index of an opening square bracket. Find index of closing bracket for a given opening bracket in an expression. Example   s = "[ABC]" index = 0 8 s = "[C-[D]]" index = 3 5 s ...

Question 482. Design a stack that supports getMin() in O(1) time and O(1) extra space Design a stack that supports getMin() in O(1) time and O(1) extra space. Thus the special stack data structure must support all the operations of the stack like – void push() int pop() bool isFull() bool isEmpty() in constant time. Add an additional operation getMin() to return the minimum value ...

Question 483. Sort a stack using recursion Problem Statement   The problem “Sort a stack using recursion” states that you are given a stack data structure. Sort its elements using recursion. Only the below-listed functions of the stack can be used – push(element) – to insert the element in the stack. pop() – pop() – to remove/delete the ...

Question 484. Delete middle element of a stack Problem Statement   Given a data structure (stack). Write a program to delete the middle element of the given stack using the basic functions of the stack – push() – to insert an element in the stack. pop() – to remove/delete the top element from the stack. empty() – to check ...

Question 485. Sorting array using Stacks Problem statement   The problem “Sorting array using Stacks” states that you are given a data structure array a[ ] of size n. Sort the elements of the given array using stack data structure. Example   2 30 -5 43 100 -5 2 30 43 100 Explanation: The elements are sorted in ...

Question 486. Sort a stack using a temporary stack Problem Statement   The problem “Sort a stack using a temporary stack” states that you are given a stack data structure. Sort the elements of the given stack using a temporary stack. Example   9 4 2 -1 6 20 20 9 6 4 2 -1 2 1 4 3 6 5 ...

Question 487. Reverse individual words Problem Statement   The problem “Reverse individual words” states that you are given a string s. Now, print the reverse of all the individual words in the string. Example   s = "TutorialCup - changing the way of learning" puClairotuT - gnignahc eht yaw fo gninrael  s = "Reverse individual words" esreveR ...

Question 488. Remove brackets from an algebraic string containing + and – operators Problem Statement   You are given a string s of size n representing an arithmetic expression with parenthesis. The problem “Remove brackets from an algebraic string containing + and – operators” asks us to create a function that can simplify the given expression. Example   s = "a-(b+c)" a-b-c  s = a-(b-c-(d+e))-f a-b+c+d+e-f ...

Question 489. Implement a stack using single queue Problem Statement   The problem “Implement a stack using single queue” asks us to implement a stack (LIFO) data structure using a queue (FIFO) data structure. Here LIFO means Last In First Out while FIFO means First In First Out. Example   push(10) push(20) top() pop() push(30) pop() top() Top : 20 ...

Question 490. Check if a queue can be sorted into another queue using a stack Problem Statement   The problem “Check if a queue can be sorted into another queue using a stack” states that you are given a queue containing n elements, the elements in the queue are a permutation of numbers 1 to n. Check if this queue can be arranged in increasing order ...

Question 491. Form Minimum Number From Given Sequence Problem Statement   The problem “Form Minimum Number From Given Sequence states that you are given a string s of length/size n representing a pattern of characters ‘I’ i.e. increasing and ‘D’ i.e. decreasing only. Print the minimum number for the given pattern with unique digits from 1-9. For instance – ...

Question 492. Iterative Postorder Traversal Using Two Stacks Problem Statement   The problem “Iterative Postorder Traversal Using Two Stacks” states that you are given a binary tree with n nodes. Write the program for it’s iterative postorder traversal using two stacks. Example   Input   4 5 2 6 7 3 1 Input   4 2 3 1 Algorithm   Create ...

Question 493. Stack Permutations (Check if an array is stack permutation of other) Problem Statement   The problem “Stack Permutations (Check if an array is stack permutation of other)” states that you are given two arrays a[ ] and b[ ] of size n. All the elements of the array are unique. Create a function to check if the given array b[ ] is ...

Question 494. Iterative method to find ancestors of a given binary tree Problem Statement   “Iterative method to find ancestors of a given binary tree” problem states that you are given a binary tree and an integer representing a key. Create a function to print all the ancestors of the given key using iteration. Example   Input  key = 6 5 2 1 Explanation: ...

Question 495. Construct BST from given Preorder Traversal Given a pre-order traversal of a Binary Search Tree(BST), write an algorithm to construct the BST from given preorder traversal. Examples   Input   preOrder[] = {7, 5, 3, 6, 9} Output Inorder : 3 5 6 7 9 Input preOrder[] = {12, 6, 1, 35, 20} Output Inorder : 1 6 ...

Question 496. Print Ancestors of a Given Binary Tree Node Without Recursion Given a binary tree and a specific node or key. Print ancestors of a given binary tree node without recursion. Example   Input : key = 7 Output : 3 1 Input : key = 4 Output : 2 1 Algorithm for Ancestors of a Given Binary Tree Node   Create a class Node ...

Question 497. Find Maximum of Minimum for Every Window Size in a Given Array Given an array a[ ] of size n. For every window size that varies from 1 to n in array print or find maximum of minimum for every window size in a given array. Example   Input : a[ ] = {10, 20, 30, 50, 10, 70, 30} Output : 70 30 20 ...

Question 498. Iterative Depth First Traversal of Graph In iterative depth first traversal of graph problem, we have given a graph data structure. Write the program to print the depth first traversal of the given graph using the iterative method. Example   Input : 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 ...

Question 499. Minimum Bracket Reversals In minimum bracket reversals problem, we have given a string s containing an expression of characters ‘{‘ and ‘}’ only. Find the minimum number of bracket reversals needed to make an expression balanced. Example   Input : s = “}{” Output: 2 Input : s = “{{{” Output: The given expression can not ...

Question 500. Expression Contains Redundant Bracket or Not Given a string s containing an expression of operators, operands, and parenthesis. Find if the given string contains any unnecessary parenthesis without which the expression will still give the same result. In other words, we have to find that expression contains a redundant bracket or not. Redundant Bracket   If an ...

Question 501. Check if Two Expressions With Brackets are Same Given two strings s1 and s2 representing expressions containing addition operator, subtraction operator, lowercase alphabets, and parenthesis. Check if two expressions with brackets are the same. Example   Input  s1 = “-(a+b+c)” s2 = “-a-b-c” Output  Yes Input  s1 = “a-b-(c-d)” s2 = “a-b-c-d” Output No Algorithm to Check if Two ...

Question 502. Level order Traversal in Spiral Form In this problem we have given a binary tree,  print its level order traversal in a spiral form. Examples   Input Output 10 30 20 40 50 80 70 60 Naive Approach for Level order Traversal in Spiral Form   The idea is to do a normal level order traversal using a ...

Question 503. Min Stack In min stack problem we have to design a stack to implement the following functions efficiently, push(x) –> Push an element x to the stack pop() –> Removes the item on top of stack top() –> Return the element at top of stack getMin() –> Return the minimum element present ...

Question 504. Queue using Stacks In queue using a stack problem, we have to implement the following functions of a queue using the standard functions of stack data structure, Enqueue: Add an element to the end of the queue Dequeue: Remove an element from the start of the queue Example   Input: Enqueue(5) Enqueue(11) Enqueue(39) Dequeue()  ...

Question 505. Arithmetic Expression Evaluation We write Arithmetic expressions in following three notations – Prefix Notation In this notation, the operands are written after the operator. It is also known as Polish Notation. For instance: +AB is a prefix expression. Infix Notation In this notation, the operators are written between the operands. It is similar ...

Question 506. Check for Balanced Parentheses in an Expression Given a string s of length n. Check whether there is a closing parenthesis for every opening parentheses i.e. if all the parentheses are balanced. In other words, we can also say that, if we have a ‘}’, ‘)’ and ‘]’ for every ‘{‘, ‘(‘ and ‘[‘ respectively, the expression ...

Question 507. Evaluation of Postfix Expression In the Evaluation of the postfix expression problem, we have given a string s containing a postfix expression. Evaluate the given expression. Example   Input : s = “231*+9-” Output : -4 Input : s = “100 200 + 2 / 5 * 7 +” Output : 757 For Operands Having Single Digits   Algorithm ...

Question 508. Find if an Expression has Duplicate Parenthesis or Not Given a string containing balanced parenthesis. Find if the expression/string contains duplicate parenthesis or not. Duplicate Parenthesis   When an expression is in the middle of or surrounded by the same type of balanced parenthesis i.e. enclosed between the same type of opening and closing parenthesis more than once it is ...

Question 509. How to Implement Stack Using Priority Queue or Heap? Implement a stack with the help of a priority queue or a heap. Priority Queue : Priority queue data structure is similar to the queue or stack data structure with an addition of priority. Every element is given a priority number. In conclusion, the elements with high priority are prefered ...

Question 510. How to Efficiently Implement k Stacks in a Single Array? Design and implement a new data structure that Implement k Stacks in a Single Array. The new data structure must support these two operations – push (element, stack_number): that pushes the element in a given number of the stack. pop (stack_number): that pop out the top element from a given ...

Question 511. Find Maximum Depth of Nested Parenthesis in a String Given a string s. Write the code to print the maximum depth of nested parenthesis in the given string. Example Input : s = “( a(b) (c) (d(e(f)g)h) I (j(k)l)m)” Output : 4 Input : s = “( p((q)) ((s)t) )” Output : 3 Using Stack   Algorithm Initialize a string s of length ...

Question 512. Expression Evaluation In expression evaluation problem, we have given a string s of length n representing an expression that may consist of integers, balanced parentheses, and binary operations ( +, -, *, / ). Evaluate the expression. An expression can be in any one of prefix, infix, or postfix notation. Example   See ...

Question 513. How to Create Mergable Stack? We have to design and create a stack that performs the operations in constant time. Here we have one problem which is how to create mergable stack? Here we perform the below operation for merge two stacks. push(element): Insert the element in the stack. pop(): Remove the top element in ...

Question 514. The Stock Span Problem This problem “The Stock Span Problem” comes under the financial aspect. In this problem, we find the stock span for the stock price of each day. The maximum number of consecutive days just before any particular day for which the price of the stock of the days before it is ...

Question 515. Find Maximum Sum Possible Equal Sum of Three Stacks Given 3 arrays stack1[ ], stack2[ ] and stack3[ ] representing stacks and the starting index of these arrays are treated as their top. Find the common maximum sum possible in all the three stacks i.e. the sum of elements of stack1, stack2 and stack3 are equal. Removal of the ...

Question 516. Print Next Greater Number of Q queries In Print Next Greater Number of Q queries problem we have given an array a[ ] of size n containing numbers and another array q[ ] of size m representing queries. Each query represents the index in array a[ ]. For each query, i print the number from the array ...

Question 517. Check if an Array is Stack Sortable In check if an array is stack sortable problem we have given an array a[ ] of size n containing elements from 1 to n in random order. Sort the array in ascending order using a temporary stack following only these two operations – Remove the element at the starting ...

Question 518. Balanced Expression with Replacement In Balanced Expression with Replacement problem we have given a string s containing parenthesis i.e. ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’. The string also contains x at some places as a replacement of parenthesis. Check if the string can be converted into an expression with valid parenthesis after replacing all ...

Question 519. Trapping Rain Water In Trapping Rain Water problem we have given N non-negative integers representing an elevation map and the width of each bar is 1. We have to find the amount of water that can be trapped in the above structure. Example   Let’s understand that by an example For the above elevation ...

Question 520. Decode String Suppose, you are given an encoded string. A string is encoded in some kind of pattern, your task is to decode the string. Let us say, < no of times string occurs > [string ] Example   Input 3[b]2[bc] Output bbbcaca Explanation Here “b” occurs 3times and “ca” occur 2 times. ...

Question 521. Recursion What is Recursion? Recursion is simply defined as a function calling itself. It uses its previously solved sub-problems to compute a bigger problem. It is one of the most important and tricky concepts in programming but we can understand it easily if we try to relate recursion with some real ...

Question 522. Prefix to Infix Conversion In prefix to infix conversion problem, we have given expression in prefix notation. Write a program to convert it into an infix expression. Prefix Notation In this notation the operands are written after the operator. It is also known as Polish Notation. For instance : +AB is an prefix expression. ...

Question 523. Postfix to Infix Conversion In postfix to infix conversion problem, we have given expression in postfix notation. Write a program to convert the given notation in infix notation. Infix Notation In this notation, the operators are written between the operands. It is similar to how we generally write an expression. For instance: A + ...

Question 524. Prefix to Postfix Conversion In prefix to postfix conversion problem, we have given expression in prefix notation in string format. Write a program to convert the given notation in postfix notation. Prefix Notation In this notation, we write the operands after the operator. It is also known as Polish Notation. For instance: +AB is ...

Question 525. Postfix to Prefix Conversion In this problem, we have given a string that denotes the postfix expression. We have to do postfix to prefix conversion. Prefix Notation In this notation, we write the operands after the operator. It is also known as Polish Notation. For instance: +AB is a prefix expression. Postfix Notation In ...

Question 526. Binary Tree zigzag level order Traversal Given a binary tree, print the zigzag level order traversal of its node values. (ie, from left to right, then right to left for the next level and alternate between). Example   consider the binary tree given below Below is the zigzag level order traversal of the above binary tree Types ...

Question 527. Backspace String Compare In the backspace string compare problem we have given two Strings S and T, check if they are equal or not. Note that the strings contain ‘#’ which means backspace character. Examples   Input S = “ab#c” T = “ad#c” Output true (as both S and T converts to “ac”) Input ...

Question 528. Next greater element The next greater element is a problem in which we have given an array. This array containing N values(may be positive or negative). We need to find the first greater_element in the given array on its right side. If there is no greater_element then take -1. Input Format   First-line containing ...

Question 529. Infix to Postfix What is an infix expression? Expression in the form of ‘operand’ ‘operator’ ‘operand’ is called infix expression. Example:  a+b What is postfix expression? Expression in the form of ‘operand’ ‘operand’ ‘operator’ is called postfix expression. Example:  ab+ What is the need of infix to postfix conversion? Infix expression is easy ...

Question 530. Form Minimum Number from Given Sequence of D’s and I’s Problem Statement   In the “Form Minimum Number from Given Sequence of D’s and I’s” problem, we have given a pattern containing only I’s and D’s. I for increasing and D for decreasing. Write a program to print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat. Input Format   ...

Question 531. The Celebrity Problem Problem Statement   In the celebrity problem there is a room of N people, Find the celebrity. Conditions for Celebrity is- If A is Celebrity then Everyone else in the room should know A. A shouldn’t know anyone in the room. We need to find the person who satisfies these conditions. ...

Question 532. Next Greater Element in an Array Problem Statement   Given an array, we will find the next greater element of each element in the array. If there is no next greater element for that element then we will print -1, else we will print that element. Note: Next greater element is the element that is greater and ...

## Queue Questions Amazon

Question 533. Find Maximum Level sum in Binary Tree Problem Statement   The problem “Find Maximum Level sum in Binary Tree” states that you are given a binary tree with positive and negative nodes, find the maximum sum of a level in the binary tree. Example   Input 7 Explanation First Level : Sum = 5 Second Level : Sum = ...

Question 534. Implementation of Deque using Doubly Linked List Problem Statement   The problem “Implementation of Deque using Doubly Linked List” states that you need to implement the following functions of Deque or Doubly Ended Queue using a doubly linked list, insertFront(x) : Add element x at the starting of Deque insertEnd(x) : Add element x at the end of ...

Question 535. Iterative Method to find Height of Binary Tree Problem Statement   The problem “Iterative Method to find Height of Binary Tree” states that you are given a binary tree, find the height of the tree using the iterative method. Examples   Input 3 Input 4 Algorithm for Iterative Method to find Height of Binary Tree   The height of a tree ...

Question 536. Level order traversal using two Queues Problem Statement   The problem “Level order traversal using two Queues” states that you are given a binary tree, print its level order traversal line by line. Examples   Input 5 11 42 7 9 8 12 23 52 3 Input 1 2 3 4 5 6 Algorithm for Level Order Traversal ...

Question 537. Implement a stack using single queue Problem Statement   The problem “Implement a stack using single queue” asks us to implement a stack (LIFO) data structure using a queue (FIFO) data structure. Here LIFO means Last In First Out while FIFO means First In First Out. Example   push(10) push(20) top() pop() push(30) pop() top() Top : 20 ...

Question 538. Find the First Circular Tour that visits all the Petrol Pumps Problem Statement   The problem “Find the First Circular Tour that visits all the Petrol Pumps” states that there are N petrol pumps on a circular road. Given the petrol that every petrol pump has and the amount of petrol required to cover the distance between two petrol pumps. So you ...

Question 539. Check if X can give change to every person in the Queue Problem Statement   X is an ice cream seller and there are n people waiting in a queue to buy an ice cream. Arr[i] denotes the denomination ith person in the queue has, the possible values of denominations are 5, 10 and 20. If the initial balance of X is 0 ...

Question 540. Check if all levels of two Binary Tree are anagrams or not Problem Statement   The problem “Check if all levels of two Binary Tree are anagrams or not” says that you are given two Binary Trees, check if all the levels of the two trees are anagrams or not. Examples   Input true Input false Algorithm to Check if all levels of two ...

Question 541. Minimum sum of squares of character counts in a given string after removing k characters Problem Statement   The problem “Minimum sum of squares of character counts in a given string after removing k characters” states that you are given a string containing lower case characters only. You are allowed to remove k characters from the string such that in the remaining string the sum of ...

Question 542. First negative integer in every window of size k Problem Statement   The problem “First negative integer in every window of size k” states that you are given an array containing positive and negative integers, for every window of size k print the first negative integer in that window. If there is no negative integer in any window then output ...

Question 543. Queue based approach for first non-repeating character in a stream Problem Statement   The problem “Queue based approach for first non-repeating character in a stream” states that you are given a stream containing lower case characters, find the first non-repeating character whenever a new character is added to the stream, and if there is no non-repeating character return -1. Examples   aabcddbe ...

Question 544. Distance of nearest cell having 1 in a binary matrix Problem Statement   The problem “Distance of nearest cell having 1 in a binary matrix” states that you are given a binary matrix(containing only 0s and 1s) with at least one 1. Find the distance of the nearest cell having 1 in the binary matrix for all the elements of the ...

Question 545. An Interesting Method to generate Binary Numbers from 1 to n Problem Statement   The problem “An Interesting Method to generate Binary Numbers from 1 to n” states that you are given a number n, print all the numbers from 1 to n in binary form. Examples   3 1 10 11   6 1 10 11 100 101 110 Algorithm   The generation ...

Question 546. Find the largest multiple of 3 Problem Statement   The problem “Find the largest multiple of 3” states that you are given an array of positive integers(0 to 9). Find the maximum multiple of 3 that can be formed by rearranging the elements of the array. Examples   arr[] = {5, 2, 1, 0, 9, 3} 9 5 ...

Question 547. Check if the given array can represent Level Order Traversal of Binary Search Tree Problem Statement   The problem “Check if the given array can represent Level Order Traversal of Binary Search Tree” states that you are given a level order traversal of the binary search tree. And using the level order traversal of the tree. We need to efficiently find if the level order ...

Question 548. Number of siblings of a given Node in n-ary Tree Problem Statement   The problem “Number of siblings of a given Node in n-ary Tree” states that you are given an n-ary Tree and a target node. Find the number of siblings of the target node. Assume that node is always present in the tree and the first node is the ...

Question 549. Check if a queue can be sorted into another queue using a stack Problem Statement   The problem “Check if a queue can be sorted into another queue using a stack” states that you are given a queue containing n elements, the elements in the queue are a permutation of numbers 1 to n. Check if this queue can be arranged in increasing order ...

Question 550. Priority Queue using doubly linked list Problem Statement   The problem “Priority Queue using doubly linked list” asks to implement the following functions of priority queue using doubly linked list. push(x, p) : Enqueue an element x with priority p in the priority queue at appropriate position. pop() : Remove and return the element with highest priority ...

Question 551. Stack Permutations (Check if an array is stack permutation of other) Problem Statement   The problem “Stack Permutations (Check if an array is stack permutation of other)” states that you are given two arrays a[ ] and b[ ] of size n. All the elements of the array are unique. Create a function to check if the given array b[ ] is ...

Question 552. Minimum Steps to reach target by a Knight Description   The problem “Minimum Steps to reach target by a Knight” states that you are given a square chess board of N x N dimensions, co-ordinates of the Knight piece, and the target cell. Find out the minimum number of steps taken by the Knight piece to reach the target ...

Question 553. Implementation of Deque using circular array Problem Statement   “Implementation of Deque using circular array” asks to implement the following functions of a Deque(Doubly Ended Queue) using circular array, insertFront(x) : insert an element x at the front of Deque insertRear(x) : insert an element x at the rear of Deque deleteFront() : delete an element from ...

Question 554. Find the node with minimum value in a Binary Search Tree Given a Binary Search Tree, write an algorithm to find the node with the minimum value in a given binary search tree. Example   Input Output 5 Naive Approach   A simple approach is to do a tree traversal and find the node with the minimum value among all the nodes. This ...

Question 555. Minimum Bracket Reversals In minimum bracket reversals problem, we have given a string s containing an expression of characters ‘{‘ and ‘}’ only. Find the minimum number of bracket reversals needed to make an expression balanced. Example   Input : s = “}{” Output: 2 Input : s = “{{{” Output: The given expression can not ...

Question 556. Construct Complete Binary Tree from its Linked List Representation Given the linked list representation of a complete binary tree. The linked list is in the order of level order traversal of the tree. Write an algorithm to construct the complete binary tree back from its linked list representation. Example   Input 1 -> 2 -> 3 -> 4 -> 5 ...

Question 557. Queue using Stacks In queue using a stack problem, we have to implement the following functions of a queue using the standard functions of stack data structure, Enqueue: Add an element to the end of the queue Dequeue: Remove an element from the start of the queue Example   Input: Enqueue(5) Enqueue(11) Enqueue(39) Dequeue()  ...

Question 558. How to Implement Stack Using Priority Queue or Heap? Implement a stack with the help of a priority queue or a heap. Priority Queue : Priority queue data structure is similar to the queue or stack data structure with an addition of priority. Every element is given a priority number. In conclusion, the elements with high priority are prefered ...

Question 559. Priority Queue in C++ FIFO manner is used to implement a queue. In a queue, insertions are done at one end (rear) and deletion takes place at another end (front). Basically, the element enters first is deleted first. We implement a priority queue using c++ inbuilt functions. Characteristics of Priority Queue   A priority queue ...

Question 560. Priority Queue A priority queue is a type of data structure which is similar to a regular queue but has a priority associated with each of its element. Higher the priority earlier the element will be served. In some cases, there are two elements with the same priority then, the element enqueued ...

Question 561. Binary Tree zigzag level order Traversal Given a binary tree, print the zigzag level order traversal of its node values. (ie, from left to right, then right to left for the next level and alternate between). Example   consider the binary tree given below Below is the zigzag level order traversal of the above binary tree Types ...

Question 562. Queue Reconstruction by Height Problem Description of Queue Reconstruction by Height   Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person ...

Question 563. Level Order Traversal of Binary Tree Level Order Traversal of a given binary tree is the same as the BFS of the binary tree. Do we already know about what actually BFS is? if not then don’t need to feel bad just read the whole article and visit our previous articles for better understanding. BFS is a ...

Question 564. Breadth First Search (BFS) for a Graph Breadth First Search (BFS) for a graph is a traversing or searching algorithm in tree/graph data structure. It starts at a given vertex(any arbitrary vertex) and explores all the connected vertex and after that moves to the nearest vertex and explores all the unexplored nodes and takes care that no ...

## Matrix Questions Amazon

Question 565. Word Search Leetcode Solution Problem Statement   Given an m x n board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once. Example ...

Question 566. Unique Paths II Suppose a man standing in the first cell or the top left corner of “a × b” matrix. A man can move only either up or down. That person wants to reach his destination and that destination for him is the last cell of the matrix or bottom right corner. ...

Question 567. Find maximum length Snake sequence The problem “Find maximum length Snake sequence” states that we are provided with a grid containing integers. The task is to find a snake sequence with the maximum length. A sequence having adjacent numbers in the grid with an absolute difference of 1, is known as a Snake sequence. Adjacent ...

Question 568. Gold Mine Problem Problem Statement   The “Gold Mine problem” states that you are given a 2D grid having some non-negative coins placed in each cell of the given grid. Initially, the miner is standing at the first column but there is no restriction on the row. He can start in any row. The ...

Question 569. Minimum time required to rot all oranges Problem Statement   The problem “Minimum time required to rot all oranges” states that you are given a 2D array, every cell has one of the three possible values 0, 1 or 2. 0 means an empty cell. 1 means a fresh orange. 2 means a rotten orange. If a rotten ...

Question 570. Distance of nearest cell having 1 in a binary matrix Problem Statement   The problem “Distance of nearest cell having 1 in a binary matrix” states that you are given a binary matrix(containing only 0s and 1s) with at least one 1. Find the distance of the nearest cell having 1 in the binary matrix for all the elements of the ...

Question 571. Find pairs with given sum such that elements of pair are in different rows Problem Statement   “Find pairs with given sum such that elements of pair are in different rows” problem states that you are given a matrix of integers and a value called “sum”. The problem statement asks to find out all the pairs in a matrix that sums up to a given ...

Question 572. Common elements in all rows of a given matrix Problem Statement   “Common elements in all rows of a given matrix” problem state that, you are given a matrix of M*N. The problem statement asks to find out all the common elements in a given matrix in each row of the matrix in O(M*N) time. Example   arr[]={{12, 1, 4, 5, ...

Question 573. Collect maximum points in a grid using two traversals Problem Statement   We are given a matrix of size “n x m”, and we need to collect maximum points in a grid using two traversals. If we are standing at cell i,j then we have three options to go to cell i+1, j or i+1, j-1or i+1, j+1. That is ...

Question 574. Mobile Numeric Keypad Problem Problem Statement   In the mobile numeric keypad problem, we consider a numeric keypad.  We need to find all number of possible numeric sequences of given length such that you are only allowed to press buttons which are top, down, left, and right of the current button. You are not allowed ...

Question 575. Printing brackets in Matrix Chain Multiplication Problem Problem Statement   We need to find the order of multiplication of matrices such that the number of operations involved in the multiplication of all the matrices is minimized. Then we need to print this order i.e. printing brackets in matrix chain multiplication problem. Consider you have 3 matrices A, B, ...

Question 576. Largest rectangular sub-matrix whose sum is 0 Problem Statement   Find the maximum size sub-matrix in a 2D array whose sum is zero. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and find the matrix with ...

Question 577. Maximum sum rectangle in a 2D matrix Problem Statement   Find the maximum sum rectangle in a 2D matrix i.e. to find a sub-matrix with maximum sum. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and ...

Question 578. Matrix Chain Multiplication In the matrix chain multiplication II problem, we have given the dimensions of matrices, find the order of their multiplication such that the number of operations involved in multiplication of all the matrices is minimized. Consider you have 3 matrices A, B, C of sizes a x b, b x ...

Question 579. Maximal Square In the maximal square problem we have 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 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 ...

Question 580. Set Matrix Zeroes In the set matrix zeroes problem, we have given a (n X m) matrix, if an element is 0, set its entire row and column 0. Examples   Input: { [1, 1, 1] [1, 0, 1] [1, 1, 1] } Output: { [1, 0, 1] [0, 0, 0] [1, 0, 1] ...

Question 581. Flood Fill LeetCode In Flood Fill problem we have given a 2D array a[ ][ ] representing an image of size mxn with each value representing the color of the pixel at that co-ordinate. Also given the location or coordinates of a pixel and a color. Replace the color at a given location ...

Question 582. Max Area of Island Problem Description: Given a 2D matrix, the matrix has only 0(representing water)  and 1(representing land) as entries. An island in the matrix is formed by grouping all the adjacent 1’s connected 4-directionally(horizontal and vertical). Find the maximum area of the island in the matrix. Assume that all four edges of ...

Question 583. Unique Paths A m x n 2D  grid is given and you are standing at the topmost and leftmost cell in the grid. i.e. the cell located at (1,1). Find the number of unique paths that can be taken to reach a cell located at (m,n) from the cell located at (1,1) ...

Question 584. K-th Smallest Element in a Sorted Matrix In K-th Smallest Element in a Sorted Matrix problem, we have given an n x n matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the given 2D array. Example   Input 1: k = 3 and matrix = 11, 21, 31, 41 ...

Question 585. Matrix Chain Multiplication using Dynamic Programming Matrix Chain Multiplication is a method in which we find out the best way to multiply the given matrices. We all know that matrix multiplication is associative(A*B = B*A) in nature. So, we have a lot of orders in which we want to perform the multiplication. Actually, in this algorithm, ...

Question 586. Multiplication of Two Matrices Problem Statement   In the “Multiplication of Two Matrices” problem we have given two matrices. We have to multiply these matrices and print the result or final matrix. Here, the necessary and sufficient condition is the number of columns in A should be equal to the number of rows in matrix ...

Question 587. Check whether Strings are K Distance Apart or Not Problem Statement   Given two strings and an integer k, write a program to check whether the given strings are k distance apart or not. That is if any character is mismatched or any character is to be removed then it is known as k distance apart. Input Format   The first ...

Question 588. Find the Row with Maximum Number of 1’s Problem Statement   In the “Find the Row with Maximum Number of 1’s” problem we have given a matrix(2D array) containing binary digits with each row sorted. Find the row which has the maximum number of 1’s. Input Format   The first line containing two integers values n, m. Next, n lines ...

Question 589. The Celebrity Problem Problem Statement   In the celebrity problem there is a room of N people, Find the celebrity. Conditions for Celebrity is- If A is Celebrity then Everyone else in the room should know A. A shouldn’t know anyone in the room. We need to find the person who satisfies these conditions. ...

## Other Questions Amazon

Question 590. Kth Largest Element in a Stream Leetcode Solution Problem Statement   In this problem, we have to design a class KthLargest() that initially has an integer k and an array of integers. We need to write a parameterized constructor for it when an integer k and array nums are passed as arguments. The class also has a function add(val) that adds ...

Question 591. Remove Linked List Elements Leetcode Solution Problem Statement   In this problem, we are given a linked list with its nodes having integer values. We need to delete some nodes from the list which have value equal to val. The problem does not require to be solved in-place but we will discuss one such approach. Example List = ...

Question 592. Minimum Moves to Equal Array Elements Leetcode Solution Problem Statement   In this problem, we are given an array of integers. Also, we are allowed to perform a certain set of operations on this array. In one operation, we can increment ” n – 1″ (all elements except any one) elements in the array by 1. We need to ...

Question 593. Hamming Distance Leetcode Solution Problem Statement   In this problem, we are given two integers, A and B, and the goal is to find the hamming distance between the given integers. The integers are greater that/equal to 0 and less than 231    Example First Integer = 5 , Second Integer = 2 3 First Integer ...

Question 594. Count Good Nodes in Binary Tree Leetcode Solution Problem Statement   In this problem a binary tree is given with its root. A node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X. We have to return the number of good nodes in ...

Question 595. Number of Steps to Reduce a Number to Zero Leetcode Solution The problem Number of Steps to Reduce a Number to Zero Leetcode Solution states that given an integer. Find the minimum number of steps to convert the given integer to 0. You can perform either of the two steps, either subtract 1 or divide the integer by 2. The problem ...

Question 596. Design Parking System Leetcode Solution Problem Statement   In this problem, we have to design a parking lot. We have 3 kinds of parking spaces (big, medium and small). All these parking spaces has some fixed number of empty slots initially. Like, in big type of space, we can place at most b cars. In small ...

Question 597. Combinations Leetcode Solution The problem Combinations Leetcode Solution provides us with two integers, n, and k. We are told to generate all the sequences that have k elements picked out of n elements from 1 to n. We return these sequences as an array. Let us go through a few examples to get ...

Question 598. Intersection of Two Arrays II Leetcode Solution Problem Statement   In this problem two arrays are given and we have to find out the intersection of this two arrays and return the resultant array. Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Example ...

Question 599. Jewels and Stones Leetcode Solution The problem Jewels and Stones Leetcode Solution states that you are given two strings. One of them represents jewels and one of them represents stones. The string that contains jewels represents the characters that are jewels. We need to find the number of characters in the stones string that are ...

Question 600. Assign Cookies Leetcode Solution The problem Assign cookies Leetcode Solution provides with two arrays. One of the arrays represents the size of the cookies and the other represents the greediness of the children. The problem states that you are the parent of children, and you want the maximum number of children to be content. ...

Question 601. Majority Element Leetcode Solution Problem Statement   We are given an array of integers. We need to return the integer which occurs more than ⌊N / 2⌋ time in the array where ⌊ ⌋ is the floor operator. This element is called the majority element. Note that the input array always contains a majority element. ...

Question 602. Palindrome Linked List Leetcode Solution In the problem “Palindrome Linked List”, we have to check whether a given singly integer linked list is a palindrome or not. Example   List = {1 -> 2 -> 3 -> 2 -> 1} true Explanation #1: The list is palindrome as all elements from the start and back are ...

Question 603. Maximum Depth of Binary Tree Leetcode Solution Problem Statement   In the problem a binary tree is given and we have to find out the maximum depth of the given tree. A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 3 / ...

Question 604. Maximum Depth of N-ary Tree Leetcode Solution In this problem, we are given an N-ary tree, that is, a tree that allows nodes to have more than 2 children. We need to find the depth of a leaf farthest from the root of the tree. This is called maximum depth. Note that the depth of a path ...

Question 605. Rotate List Leetcode Solution The problem Rotate List Leetcode Solution provides us a linked list and an integer. We are told to rotate the linked list to the right by k places. So if we rotate a linked list k places to the right, in each step we take the last element from the ...

Question 606. Pow(x, n) Leetcode Solution The problem “Pow(x, n) Leetcode Solution” states that you are given two numbers, one of which is a floating-point number and another an integer. The integer denotes the exponent and the base is the floating-point number. We are told to find the value after evaluating the exponent over the base. ...

Question 607. Find the Difference Leetcode Solution Problem statement   In the problem “Find the Difference” we are given two strings s and t. String t is produced by randomly stuffing the characters of string s and adding one character at a random position. our task is to find out the character which was added in string t. ...

Question 608. Insert into a Binary Search Tree Leetcode Solution In this problem, we are given the root node of a Binary Search Tree containing integer values and an integer value of a node that we have to add in the Binary Search Tree and return its structure. After inserting the element into the BST, we have to print its ...

Question 609. Merge Two Sorted Lists Leetcode Solutions Linked lists are quite like arrays in their linear properties. We can merge two sorted arrays to form an overall sorted array. In this problem, we have to merge two sorted linked lists in place to return a new list which contains elements of both lists in a sorted fashion. Example   ...

Question 610. Permutations Leetcode Solution The problem Permutations Leetcode Solution provides a simple sequence of integers and asks us to return a complete vector or array of all the permutations of the given sequence. So, before going into solving the problem. We should be familiar with permutations. So, a permutation is nothing but an arrangement ...

Question 611. Minimum Depth of Binary Tree Leetcode Solution In this problem, we need to find the length of the shortest path from the root to any leaf in a given binary tree. Note that the “length of the path” here means the number of nodes from the root node to the leaf node. This length is called Minimum ...

Question 612. Count Primes Leetcode Solutions In this problem, we are given an integer, N. The goal is to count how numbers less than N, are primes. The integer is constrained to be non-negative. Example   7 3 10 4 Explanation Primes less than 10 are 2, 3, 5 and 7. So, the count is 4. Approach(Brute ...

Question 613. House Robber II Leetcode Solution In the “House Robber II” problem, a robber wants to rob money from different houses. The amount of money in the houses is represented through an array. We need to find the maximum sum of money that can be made by adding the elements in a given array according to ...

Question 614. Sqrt(x) Leetcode Solution As the title says, we need to find the square root of a number. Let say the number is x, then Sqrt(x) is a number such that Sqrt(x) * Sqrt(x) = x. If the square root of a number is some decimal value, then we have to return the floor value of ...

Question 615. Convert Sorted Array to Binary Search Tree Leetcode Solution Consider we are given a sorted array of integers. The goal is to build a Binary Search Tree from this array such that the tree is height-balanced. Note that a tree is said to be height-balanced if the height difference of left and right subtrees of any node in the ...

Question 616. Swap Nodes in Pairs Leetcode Solutions The goal of this problem is to swap nodes of a given linked list in pairs, that is, swapping every two adjacent nodes. If we are allowed to swap just the value of the list nodes, the problem would be trivial. So, we are not allowed to modify the node ...

Question 617. House Robber Leetcode Solution Problem Statement   In this problem there are houses in a street and House robber has to rob these houses. But the problem is that he can’t rob more than one house successively i.e which are adjacent to each other. Given a list of non-negative integers representing the amount of money ...

Question 618. Happy Number Leetcode Solution Problem Statement   The problem is to check whether a number is happy number or not. A number is said to be happy number if replacing the number by the sum of the squares of its digits, and repeating the process makes the number equal to 1. if it does not ...

Question 619. Valid Anagrams In the problem “Valid Anagrams” we have given two strings str1 and str2. Find out that both the strings are anagrams or not. If they are anagrams return true else return false. Example   Input: str1 = “abcbac” str2 = “aabbcc” Output: true Explanation: Since str2 can be formed by rearranging ...

Question 620. Contiguous Array Given an array consisting of number 0’s and 1’s only. We have to find the length of the longest contiguous sub-array consisting o’s and 1’s equally. Example   Input arr = [0,1,0,1,0,0,1] Output 6 Explanation The longest contiguous sub-array is marked in red [0,1,0,1,0,0,1] and its length is 6. Algorithm   Set ...

Question 621. Union and Intersection of two Linked Lists Given two linked lists, create another two linked lists to get union and intersection of the elements of existing lists. Example   Input: List1: 5 → 9 → 10 → 12 → 14 List2: 3 → 5 → 9 → 14 → 21 Output: Intersection_list: 14 → 9 → 5 Union_list:   ...

Question 622. Lemonade Change Leetcode Solution This post is on Lemonade Change Leetcode Solution Problem statement   In the problem ” Lemonade Change” there is a queue of customers. They want to buy lemonade from us which costs 5 rupees. The customers can give us 5 rupees, 10 rupees, or 20 rupees. We want to return the ...

Question 623. Valid Perfect Square Leetcode Solution This post is on Valid Perfect Square Leetcode Solution Problem statement   In the problem “Valid Perfect Square” we are given a number “num” and we need to check if this number is a perfect square or not. We have to check this without using the built-in sqrt function. If the ...

Question 624. Round Robin Scheduling The Round Robin scheduling is very much similar to FCFS. The only difference between RR and FCFS scheduling is, RR is preemptive scheduling whereas FCFS is non-preemptive scheduling. Every process is allocated to CPU in the ready queue for a single time slice. Here, a ready queue is similar to ...

Question 625. Maximum number of segments of lengths a, b and c The problem “Maximum number of segments of lengths a, b and c” states that you are given a positive integer N, and you need to find the maximum number of segments of lengths a,b, and c that can be formed using N. Example   N = 7 a = 5, b ...

Question 626. Best Time to Buy and Sell Stock with Cooldown Leetcode Solution Problem statement   In the problem “Best Time to Buy and Sell Stock with Cooldown” we are given an array where each element in the array contains the price of the given stock on that day. There is no restriction on the number of transactions. The definition of the transaction is ...

Question 627. Sequences of given length where every element is more than or equal to twice of previous The problem “Sequences of given length where every element is more than or equal to twice of previous” provides us with two integers m and n. Here m is the largest number that can exist in the sequence and n is the number of elements that must be present in the ...

Question 628. Count ways to reach the nth stair using step 1, 2 or 3 The problem “Count ways to reach the nth stair using step 1, 2, or 3” states that you are standing on the ground. Now you need to reach the end of the staircase. So how many ways are there to reach the end if you can jump only 1, 2, ...

Question 629. Find postorder traversal of BST from preorder traversal Problem Statement   The problem “Find postorder traversal of BST from preorder traversal” states that you are given preorder traversal of a binary search tree. Then using the given input find the postorder traversal. Example      preorder traversal sequence: 5 2 1 3 4 7 6 8 9 1 4 3 ...

Question 630. Count even length binary sequences with same sum of first and second half bits The problem “Count even length binary sequences with same sum of first and second half bits” states that you are given an integer. Now find out the number of ways to construct a binary sequence of size 2*n such that the first half and second half have the same number ...

Question 631. Print Maximum Length Chain of Pairs Problem Statement   The problem “Print Maximum Length Chain of Pairs” states that you are given some pairs of numbers. It is given that in each pair, the first number is smaller than the second number. Now you need to find the longest chain such that the second number of preceding ...

Question 632. Print n terms of Newman-Conway Sequence Problem Statement   The problem “Print n terms of Newman-Conway Sequence” states that you are given an integer “n”. Find the first n terms of Newman-Conway Sequence then print them. Example n = 6 1 1 2 2 3 4 Explanation All the terms which are printed follow the Newman-Conway Sequence ...

Question 633. Remove Duplicates from Sorted List II The problem “Remove Duplicates from Sorted List II” states that you are given a linked list that may or may not have duplicate elements. If the list has duplicate elements then remove all of their instances from the list. After performing the following operations, print the linked list at the ...

Question 634. Write a function to get the intersection point of two Linked Lists Problem Statement   The problem “Write a function to get the intersection point of two Linked Lists” states that you are given two linked lists. But they are not independent linked lists. They are connected at some point. Now you need to find this point of intersection of these two lists. ...

Question 635. Newman-Conway Sequence Problem Statement   The problem “Newman-Conway Sequence” states that you are given an input integer “n”. Then you need to print first nth element of the Newman-Conway Sequence. Example   n = 6 4 n = 10 6 Explanation Since the output elements represent the sixth and tenth element of the Newman-Conway ...

Question 636. Delete Nth node from the end of the given linked list Problem Statement   The problem “Delete Nth node from the end of the given linked list”  states that you are given a linked list with some nodes. And now you need to remove nth node from the end of the linked list. Example   2->3->4->5->6->7 delete 3rd node from last 2->3->4->6->7 Explanation: ...

Question 637. Print Fibonacci sequence using 2 variables Problem Statement   The problem “Print Fibonacci sequence using 2 variables” states that you need to print the Fibonacci sequence but there is a limitation of using only 2 variables. Example   n = 5 0 1 1 2 3 5 Explanation The output sequence has the first five elements of the ...

Question 638. Cutting a Rod Problem Statement   The problem “Cutting a Rod” states that you are given a rod of some particular length and prices for all sizes of rods which are smaller than or equal to the input length. That is we know the price for rods of length from 1 to n, considering ...

Question 639. Largest divisible pairs subset Problem Statement   The problem “Largest divisible pairs subset” states that you are given an array of n distinct elements. Find the length of largest such that each pair of the subset has the larger element divisible by smaller elements. Example   array = {1, 2, 4, 5, 8, 9, 16} 5 ...

Question 640. Check if any two intervals overlap among a given set of intervals Problem Statement   The problem “Check if any two intervals overlap among a given set of intervals” states that you are given some set of intervals. Each interval consists of two values, one is starting time and the other is ending time. The problem statement asks to check if any of ...

Question 641. Friends Pairing Problem Problem Statement   The “Friends Pairing Problem” states that there are N friends. And each them can remain single or be paired up with each other. But once a pair is made, those two friends can not take part in pairing. So, you need to find the total number of ways ...

Question 642. Happy Number Problem Statement   What is a happy number? A number is a happy number if we can reduce a given number to 1 following this process: -> Find the sum of the square of the digits of the given number. Replace this sum with the old number. We will repeat this ...

Question 643. Palindrome Number Problem Statement   the problem “Palindrome Number” states that you are given an integer number. Check if it is a palindrome or not. Solve this problem without converting the given number into a string. Example   12321 true Explanation 12321 is a palindrome number because when we reverse 12321 it gives 12321 ...

Question 644. Tiling Problem Problem Statement   The “Tiling Problem” states that you have a grid of size 2 x N and a tile of size 2 x 1. So, find the number of ways to tile the given grid. Example   3 2 Explanation: Approach for Tiling Problem   We can solve this problem by using recursion. ...

Question 645. Page Replacement Algorithms in Operating Systems What is Page Replacement?   The modern operating systems use paging for memory management and many times there is a need for page replacement. Page replacement is the process of replacing a page that is currently present in the memory with a page that is needed but is not present in ...

Question 646. Linked List Cycle Problem Statement   “Linked List Cycle” problem states that you are given a linked list. Find if it contains any loop or not?  Linked list with cycle Example   1->2->3 No Loop Explanation: The linked list does not contain any loop because if it did then there would’ve been two no des ...

Question 647. Boolean Parenthesization Problem Problem Statement   “ Boolean Parenthesization Problem ” states that we are given a sequence of true and false, and some boolean operators( AND, OR, XOR) in between them. We need to find the number of ways to parenthesize the given sequence such that the entire sequence results in TRUE. In ...

Question 648. Count pairs from two linked lists whose sum is equal to a given value Problem Statement   Problem “Count pairs from two linked lists whose sum is equal to a given value” state that you are given two linked lists and an integer value sum. The problem statement asked to find out how many total pair has a sum equal to the given value. Example   ...

Question 649. How to print maximum number of A’s using given four keys Problem Statement   How to print maximum number of A’s using given four keys, this problem states that you have the option to choose which key to press. The keys perform the following tasks: Key1 – Prints ‘A’ on screen Key2 – Select the whole screen. Key3 – Copy the selected ...

Question 650. Count items common to both the lists but with different prices Problem Statement   You are given two lists. Each of which index contains the name of the item and its price. The problem statement asks to count items common to both the lists but with different prices, which is to find out how many numbers of items are common in both ...

Question 651. A Space Optimized DP solution for 0-1 Knapsack Problem Problem Statement   We are given a knapsack which can hold some weight, we need to pick some of the items out of given items with some value. The items should be picked such that the value of the knapsack ( total value of picked up items ) should be maximized. ...

Question 652. Minimum number of jumps to reach end Problem Statement   Suppose you have an array of integers and each element of an array indicates each number as maximum jumps that can be taken from that point. Your task is to find out the minimum number of jumps to reach end, i.e. minimum of jumps that can be taken ...

Question 653. Huffman Coding We have a message that we want to deliver. We want the message to be of least size possible so that the costs incurred in sending the message is low.  Here we use the Huffman Coding concept to reduce the size of the message. Let’s assume that we have the ...

Question 654. Data Structure Designing Listening to Data Structure Designing, A lot of people might want to run away looking at the title itself. Those who know me know that I am not leaving until I explain the concept entirely. Embark with me on a journey to learn a problem and a few ideas on ...

Question 655. Longest Increasing Subsequence We are provided with an array of integers that is unsorted and we have to find the longest increasing subsequence. The subsequence need not be consecutive The subsequence shall be increasing Let’s understand that better by a few examples. Example   Input [9, 2, 5, 3, 7, 10, 8] Output 4 ...

Question 656. K-th Distinct Element in an Array You are given an integer array A, print k-th distinct element in an array. The given array may contain duplicates and the output should print k-th distinct element among all unique elements in an array. If k is more than a number of distinct elements, then report it. Example   Input: ...

Question 657. Swap Nodes In Pairs In swap nodes in pairs problem, we have given a linked list consisting of n nodes. Swap every node at even index with it’s a right adjacent node at odd index() considering index starting from 0. Example   Input : 1->2->3->4->NULL Output : 2->1->4->3->NULL Input : 1->2->3->4->5->6->7->NULL Output : 2->1->4->3->6->5->7->NULL Iterative Method   Algorithm Create a ...

Question 658. Intersection of Two Arrays In intersection of two arrays problem, we have given two arrays, we need to print their intersection(common elements). Example   Input arr1[] = {1, 2, 2, 1} arr2[] = {2, 2} Output {2, 2} Input arr1 = {4, 9, 5} arr2 = {9, 4, 9, 8, 4} Output {4, 9} Algorithm ...

Question 659. Leetcode Permutations In this leetcode problem premutation we have given an array of distinct integers, print all of its possible permutations. Examples   Input arr[] = {1, 2, 3} Output 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Input arr[] = {1, 2, ...

Question 660. Sudoku Solver In the sudoku solver problem we have given a partially filled (9 x 9) sudoku, write a program to complete the puzzle. Sudoku must satisfy the following properties, Every number(1-9) must appear exactly once in a row and once in a column. Every number(1-9) must appear exactly once in a ...

Question 661. MiniMax Algorithm Everyone might be wondering. Argh, another new MINIMAX ALGORITHM. Why do we need it? Let’s know to play a game of chess or tic-tac-toe we have often wondered if there was an algorithm to win the game. Explanation   A lot of times we might have wondered if It was possible to ...

Question 662. Target Sum “Target Sum” is a special problem for all the DPHolics I have with me today. There ain’t no need to worry I am going to abandon the rest of my lovely readers. We all have gone through the classic KnapSack problem where we try to find the maximum number of ...

Question 663. Counting Bits All about Counting Bits! Humans have a problem communicating with the computers they made. Why? Humans speak and understand the language they have come to speak and listen to over the years but they taught the poor computer 0’s and 1’s. So today, Let’s teach our computer to count the ...

Question 664. Merge K Sorted Linked Lists Merge K sorted linked lists problem is so famous as per the interview point of view. This question asks so many times in big companies like Google, Microsoft, Amazon, etc.  As the name suggests we’ve been provided with k sorted linked lists. We have to merge them together into a ...

Question 665. OSI Model This model was developed in 1983 by the International Standards Organization (ISO). This was the first step taken to standardized the international protocols used in various layers. As it deals with connecting open systems, that is, systems that are open for communication with other systems, the model is called the ...

Question 666. Nth Catalan Number In the Nth Catalan number problem, we have given an integer n. Find the first n Catalan numbers. Catalan numbers are a series of positive integers which is seen in many counting problems. They are used to count – BSTs (Binary search trees) with n keys. Certain types of lattice ...

Question 667. Merge Two Sorted Linked Lists In merge two sorted linked lists we have given head pointer of two linked lists, merge them such that a single linked list is obtained which has nodes with values in sorted order. return the head pointer of the merged linked list. Note: merge the linked list in-place without using ...

Question 668. Find Median from data Stream In Find Median from the data Stream problem, we have given that integers are being read from a data stream. Find the median of all the elements read so far starting from the first integer till the last integer. Example   Input 1: stream[ ] = {3,10,5,20,7,6} Output : 3 6.5 ...

Question 669. House Robber The House Robber Problem states that, in a neighborhood in a city, there is a single row of n houses. A thief is planning to carry a heist in this neighborhood. He knows how much gold is concealed in each of the houses. However, in order to avoid triggering an ...

Question 670. Sliding Window Maximum In Sliding Window Maximum problem we have given an array nums, for each contiguous window of size k, find the maximum element in the window. Example   Input nums[] = {1,3,-1,-3,5,3,6,7} k = 3 Output {3,3,5,5,6,7} Explanation Naive Approach for Sliding Window Maximum   For every contiguous window of size k, traverse ...

Question 671. Word Break Word Break is a problem that beautifully illustrates a whole new concept. We have all heard of compound words. Words made up of more than two words. Today we have a list of words and all we’ve got to do is check if all the words from the dictionary can ...

Question 672. Hamming Distance What is Hamming Distance?   Hamming distance is Technically defined as the number of bits in the same position that differs in two numbers. Let us delve into a new way of finding the distance between two numbers. Example   Input To find the hamming distance between 4 and 14 4 and ...

Question 673. First Bad Version We all have heard the saying “Bad Apple Ruins The Bunch”.First Bad Version is a problem that beautifully illustrates the same. Today we have a problem which is First Bad Version. One of the interns has made an nth bad commit due to which commits from n+1 have all been ...

Question 674. Kruskal Algorithm What is Kruskal Algorithm?   Kruskal’s algorithm is used to find the minimum spanning tree(MST) of a connected and undirected graph. Example Graph Minimum Spanning Tree(MST) Algorithm   Kruskal’s algorithm is a greedy algorithm to find the minimum spanning tree. Sort the edges in ascending order according to their weights. At every ...

Question 675. Merge Two Sorted Lists Leetcode What is merge two sorted lists problem on leetcode?   This is so interesting question asked so many times in compnies like Amazon, Oracle, Microsoft, etc. In this problem(Merge Two Sorted Lists Leetcode), we have given two linked lists. Both linked lists are in increasing order. Merge both linked list in ...

Question 676. Reverse Nodes in K-Group Problem   In Reverse Nodes in K-Group problem we have given a linked list, Reverse the linked list in a group of k and return the modified list. If the nodes are not multiple of k then reverse the remaining nodes. The value of k is always smaller or equal to ...

Question 677. LRU Cache Implementation Least Recently Used (LRU) Cache is a type of method which is used to maintain the data such that the time required to use the data is the minimum possible. LRU algorithm used when the cache is full. We remove the least recently used data from the cache memory of ...

Question 678. Merge Sort What is merge sort?   Merge Sort is a Recursive Procedure. It is also a divide and conquers algorithm. Now we need to know what divide and conquer algorithm is? It’s a type of procedure in which we divide the problem into subproblems and divide them until we find the shortest ...

Question 679. Valid Sudoku Valid Sudoku is a problem in which we have given a 9*9  Sudoku board. We need to find the given Sudoku is valid or not on the basis of the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Every of the 9 3x3 sub-boxes ...

Question 680. Palindrome Partitioning Palindrome Partitioning is a DP problem. In this problem, Given a string S. Partition S such that every substring of the partition is a palindrome.  We need to print the minimum cuts needed for a palindrome partitioning of S. Input Format   Only a single line containing string S. Output Format   ...

Question 681. Add two numbers Add two numbers is a problem in which we have given two non-empty linked list representing a non-negative integer. The digit are store in reverse order and every node must contain only a single digit. Add the two numbers and print the result by using a linked list. Input Format   ...

Question 682. Sieve of Eratosthenes Sieve of Eratosthenes is an algorithm in which we find out the prime numbers less than N. Here N is an integer value. This is an efficient method to find out the prime numbers to a limit. By using this we can find out the prime numbers till 10000000. Here ...

Question 683. N queen problem N queen problem using the concept of Backtracking. Here we place queen such that no queen under attack condition. The attack condition of the queens is if two queens are on the same column, row, and diagonal then they are under attack. Let’s see this by the below figure. Here ...

Question 684. Alien Dictionary Alien Dictionary is a type of problem in which we have N-words and they are sorted in alien dictionary order. We need to find the order of the characters. The alien language is also used the lowercase letters but the order of the letters is different. Let’s see how we ...

Question 685. Last Stone Weight Last Stone Weight is a problem in which we have a set of stones having some positive weights. Now we perform a task on it till we left 1 stone or no stone. We always pick two stones having the highest weight_value and smash them together. Let’s suppose the weight ...

Question 686. Climbing stairs Problem Statement   The problem “Climbing stairs” states that you are given a staircase with n stairs. At a time you can either climb one stair or two stairs. How many numbers of ways to reach the top of the staircase? Example   3 3 Explanation There are three ways to climb ...

Question 687. Serialize and Deserialize Binary Tree We have given a binary tree containing N number of nodes where each node has some value. We need to serialize and deserialize the binary tree. Serialize The process of storing a tree in a file without disturbing its structure is called serialization. DeserializeSerialize and Deserialize Binary Tree The process ...

Question 688. Reverse a linked list Problem Statement   The problem “reverse a linked list” states that we are given the head of the linked list. We have to reverse the linked list by changing the links between them and return the head of the reversed linked list. Example   10->20->30->40->NULL NULL<-10<-20<-30<-40 Explanation We have reversed the linked ...

Question 689. Maximum Length of Chain Pairs Problem Statement   In the maximum length of chain pairs problem we have given n pairs of numbers, find the longest chain in which (c, d) can follow (a, b) if b < c. In the given pairs the first element is always smaller than the second.  Example   Input [{12, 14}, ...

Question 690. Find Pair with Given Difference Problem Statement   In the given unsorted array, find the pair of elements in the given array with given difference n. Example   Input arr[] = {120, 30, 70, 20, 5, 6}, difference(n) = 40 Output [30, 70] Explanation Here the difference of 30 and 70 is equal to the value of ...

Question 691. Detect a loop in the Linked List Problem Statement   In the “Detect a loop in the Linked List” problem we have given a linked list. Find whether there is loop or not. If there is a loop in the linked list then some node in the linked list will be pointing to one of the previous nodes ...

Question 692. Find Nth Node Problem Statement   In the “Find Nth Node” problem we have given a linked list to find the nth node. The program should print the data value in the nth node. N is the input integer index. Example   3 1 2 3 4 5 6 3 Approach   Given a linked list ...

Question 693. Swap Kth Node from beginning with Kth Node from End Problem Statement   In the “Swap Kth Node from beginning with Kth Node from End” problem, we have given a linked list. Swap kth node from beginning_with kth node from the end. We should not swap the values, we should swap pointers. Example   2 1 2 3 4 5 6 1 ... 