Given a 2d matrix, filled with 1 and 0. Find the maximum sub-matrix that has only 1’s and return the area.
Given matrix: Maximum sub-matrix: To solve this problem, we shall use Dynamic Programming. For the given M * N matrix, we shall take another M * N matrix to fill the data. We shall call that array as dp_arr[m][n]. Then when filling each element in the matrix, if the value of the element is 1, […]
You are given an unsorted array, and a key number, find the largest number of that key position.
array = { 3, 7, 6, 5, 2, 9, 4} key = 3 Solution = 6. Question explanation: First sort the above array: {2, 3, 4, 5, 6, 7, 9} So the keyth largest element is “6”. Because 9 is first largest Because 7 is second largest Because 6 is third largest Solution explanation: We […]
Given the heights of histogram using an array, you need to find the largest area rectangle in that histogram. Solution in C++
Question explanation: A histogram is a bar graph, where each unit is 1. You are given an array representing the height of the histogram. You need to find the maximum area of the histogram. Suppose given array is as below: { 4, 2, 5, 4, 5, 1} The histogram can be shown as below: So […]
Given an array and a key element, find the number of continuous elements whose sum is greater than the key element.
Example: array = {1, 2, 3, 4, 5, 6, 7, 8, 9}; k = 30 Output: 4 This is because the sub array [6, 7, 8, 9] This problem can be solved with “two pointers with sliding window approach” solution. Algorithm: Step 1: Increase right pointer till the sum is greater than or equal to […]
Given 2 strings, check if they are isomorphic strings.
2 strings are said to be isomorphic, if one letter in the first string can be replaced by another letter in the second string. Example 1: string_1 = add string_2 = egg Output: True Here “a” can be replaced by “e” and “d” can be replaced by “g”. Example 2: string_1 = foo string_2 = […]
Given an array, find the majority element, solution in C++
A majority element, is an element that is repeated more than half of the times. Example: [1, 2, 3, 4, 4, 4, 4, 4, 5] Output: 4. Total number of elements are 9, and 4 is repeated 5 times. It has repeated more than half of the times. We can solve this problem by using […]
Find the minimum element from an array that is sorted and is rotated, solution in C++
Example 1: Input: [3,4,5,6,7,1,2] Output: 1 We shall use 2 pointers to solve this problem. Below are steps how the solution works: 1. Frist we check arr[start] < arr[end], then we return the arr[start] value. 2. Else 3. Compute the mid element 4. If arr[mid] > arr[start], then we know that the rotation is in […]
Given an integer array, find the maximum product made from continuous elements in that array. Solution in C++
Example 1: Input: [2,3,-1,3] Output: 6 Explanation: [2,3] are continuous and has the largest product 6. The steps of the working of the solution is as below: 1. Take 2 variables “front_product” and “back_product”. 2. front_product will always calculate from front of the array. 3. back_product will always calculate from back of the array. 4. […]
You are given a sentence, reverse the string word by word
Example: Input: “prodevelopertutorial is a good website”, Output: ” website good a is prodevelopertutorial”. The solution is as follows: Step 1: Reverse the whole string. Step 2: Reverse individual words in the string. Along with the above 2 steps, we need to remove leading and trailing spaces, and extra spaces in between the words. Solution […]
Given an expression in reverse polish notation, evaluate it and get the output in C++
In reverse polish notation, operands will be first followed by operators. For example, 2 – 3 in reverse polish notation will be 2 3 – 4 + 5 – 6 will be written as 4 5 + 6 – Solution explanation: We can solve this by using stacks. Consider example below: 5 4 + 6 […]