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

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

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