Arrays

Finding Missing Number in an Increasing Sequence

Problem Statement You are given an array which contains an increasing sequence of numbers from 1 to N. There is one number missing in the sequence. The task at hand is find the missing number in minimum running time. Input: An array A of numbers in increasing order, with one number missing. Output: The missing integer Constraint: The sequence is strictly increasing. The algorithm should finish in minimum time. Approach for Finding Missing Number At first, it looks like a simple problem which can be solved in O(N) time. Indeed it is. Here are the steps: Start traversing from the...
Read More

Maximum Element Sliding Window

A very interesting problem indeed! Often asked in Interviews in various forms and we will discuss one of these forms here in this post. Problem Statement - Maximum Element Sliding Window Given a stream or array of elements (preferably integers). Find the elements with maximum value in a window of length K where the window slides by one step to the right every time. What is a Sliding Window? Given an array A, a sliding window of length K is a range of fixed size K in the array such that the range slides to the right by one index. Here is a diagram to explain how sliding window will look...
Read More

Count Triangles formed by the elements of array

Problem Statement Given a sorted array of distinct integers, each of these integers can represent a length. The task at hand is to count the number of possible triangles which can be made through these lengths. Of course, if you chose one length to be one side of the triangle, you cannot use that length again in the same triangle. This means, no triangle contains the same length more than once. Important Note: For given sides of lengths a, b and c. A triangle can only be formed if sum of any two sides is greater than the third side. This is called the triangle inequality. The sum of any...
Read More

Save the largest area

Problem Statement In the historic city of Technisia there are rectangular monuments made of stones. The monuments are placed on the ground in such a way that they all lie in one row. The width of each monument is one unit and the length may vary.  The population of the city is growing and people need empty spaces to build houses and markets. The mayor decides to demolish the monuments and presents a demolition schedule. You being a monument lover, would like to preserve the most of what can be preserved, hence you start finding a solution to save the largest area. Upon your request the may...
Read More

Cursed Trees – Interview Question

Problem Statement This is an awesome interview question which tests our ability to extensively use data structures. We are given an array of trees with different heights. The trees have a curse upon them, they do not grow any more and for a given pair of trees, if a tree is taller than the one to its left then the tree will die in a year. The task at hand is to find out, the number of years after which no trees will die. Explanation Year 1 : At the end of the first year the trees with height 6 , 14 and 10 will die. All of these trees have a smaller tree to their left and the r...
Read More