# Find peak element in array

Today’s problem is to find peak element in array. A peak element is defined as an element which is not smaller than its neighbors.Mathematically, ith element is called as peak following property holds true:

For first element and last elements of array, left and right neighbors respectively, are considered as negative infinity. Given an input array with non sorted integers, find peak element in it. For an array which is all sorted elements, last element will be peak. For an array which is all reversed sorted elements, first element will be peak.

## Methods to find peaks in array

Simple approach would be to scan through array and for every element, check for the above mentioned property. As soon as some element satisfy the condition, return the index.

In worst case we would end up scanning whole array (in case array integers are all sorted), which will give us complexity of O(N). Can we do better than this?

If a given number is not peak, there are two cases:
1. Either we are rising towards right, that means A[i+1] > A[i]
2. Or we are falling from left, that means A[i-1] > A[i].

With above two cases, we can safely say that in first case, there would be some peak in right sub array and in second case there would be some peak in left sub array. How come?

Let’s say we divide the whole array in two parts, having m and n elements each.

```X = A[0], A[1], ........A[m-1], A[m]
Y = A[m+1], A[m+2]..........A[n-1]
```

If A[m] > A[m-1] && A[m] > = A[m+1], mth element is peak element, return it.

Now if A[m] < A[m+1], i.e last element of X is less than first element of Y. In that case, there is possibility that either A[m+1] is peak, or some subsequent element would be.In worst case it would be the last element.

If A[m] < A[m-1], that is last element of X is less that second last element of X. In that case, either A[m-1] is peak or some element preceding it would surely will be. In worst case, first element will be the peak.
Now question is how to select m? Let’s do it with binary search which will reduce our complexity to O(log N).

## Find peaks in array implementation

```int findPeakElement(int a[], int start,int size){

int mid =  (start + size)/2;

if((mid == 0 || a[mid] > a[mid-1]) &&
(mid == size-1 || a[mid] > a[mid+1])){
return mid;
}
else if(a[mid] < a[mid+1])
return findPeakElement(a,mid+1, size);
else
return findPeakElement(a,0, mid-1);
}
```

Complexity of algorithm to find peak element in array is is O(log N).

# Move zeros to end of array

This is very commonly asked interview problem and requires bit comfort with array indixes to solve it. Problem statement is : given an array which contains random numbers, including zeros. We have to move zeros at the end of the array. For example input array is

Output array is

### Move zeros at the end of array

Basic idea is to scan through array, whenever we find a zero, move all successive elements accordingly. We wont be moving all elements every time we hit zero. Trick is similar to problem where we delete specific characters from a string. For complete explanation refer to this post.
For above example, at some point, below will be state of array and other variables

By the time we reach at the end of the array, we may have difference between the last element of the array and size of given input array. That will be the number of zeros in input array. Fill all those spots with zero.

## Move zeros to end implementation

```#define MAX_ELEM 10
void move_zeroes(int a[], int size){
int i, dest = 0;

for(i =0; i<size; i++){
if(a[i] != 0){
a[dest++] = a[i];
}
}
for(i= dest; i<size; i++){
a[i] = 0;
}
printf("\n");
for(i= 0; i<size; i++){
printf("%d ", a[i]);
}
}

//Driver program
int main(){
int a[] = {0,1,3,4,0,0,0,5,6,7};
int size = sizeof(a)/sizeof(a[0]);
move_zeroes(a, size);
return 0;
}
```

Complexity of algorithm to move zeroes at end of array is O(N).
There is another problem which can be solved with same approach.
Problem is to delete consecutive duplicate elements except from the first in an array. For example, input array is {0,1,1,3,3,5,0,0,6,6}
Output should be {0,1,3,5,0,6}

```void remove_duplicates(int a[], int size){
int i=0, dest =-1;

while(i < size-1){
if(a[i] != a[i+1]){
if(dest != -1)
a[dest++] = a[i+1];
}
else{
if(dest == -1)
dest = i+1;
}
i++;
}
for(i= 0; i<dest; i++){
printf("%d ", a[i]);
}
}
```

# Sliding Window Algorithm

Given a larger integer buffer/array (say size, x), window size (say, n) and a number (say, k). Windows starts from the 1stelement and keeps shifting right by one element.The objective is to find the minimum k numbers present in each window. This is commonly solved using sliding window algorithm.
This problem regularly features in programming interview questions. Basic concept is very simple, but some more variables thrown into question, that makes it more interesting.

Given an array of integers, how do we find K smallest or largest elements?  There are a few ways to do so.

Quicksort
First way is to use quick sort, when pivot is at Kth position, all elements on right side are greater than pivot, hence, all elements on the left side automatically become K smallest elements of given array.

Array with K+1 elements
Keep an array of K elements, Fill it with first K elements of given input array.
Now from K+1 element, check if the current element is less than the maximum element in the auxiliary array, if yes, add this element into array.
Only problem with above solution is that we need to keep track of maximum element. Still workable.How can we keep track of maximum element in set of integer? Think heap. Think Max heap.

Heaps
Great! In O(1) we would get the max element among K elements already chose as smallest K elements . If max in current set is greater than newly considered element, we need to remove max and introduce new element in set of K smallest element. Heapify again to maintain the heap property.Now we can easily get K minimum elements in array of N.

## Sliding window algorithm to find Kth smallest element.

Rest of the problem is just to adjust our array consideration w.r.t to start and end index in bigger array.
Following figures explain how window slides and how heap is updated.
1. Window starts at index 0 and ends at N. We take K minimum elements among N elements and store in max heap.

2. Now window moves one step ahead, so heap is updated again.

3. Again windows slides forward but this time, max heap is not updated.

## Sliding window algorithm implementation

```#include<stdio.h>
#include<stdlib.h>
#include <math.h>

typedef struct node {
struct node * left;
struct node * right;
int data;
} heapNode;

int leftChild(int i){
return 2*i + 1;
}

int rightChild(int i){
return 2*i + 2;
}

void swapPtr(heapNode *a[], int i, int largest){
heapNode *temp = a[i];
a[i] = a[largest];
a[largest] = temp;
}

/* This function heapifies heap after removal of root
or at time of building heap from an array */
void maxHeapify(heapNode *a[], int i, int len){
int largest = i;

int left = leftChild(i);
int right = rightChild(i);

if(left <= len && a[i]->data <a[left]->data){
largest = left;
}
if(right <= len && a[largest]->data < a[right]->data){
largest = right;
}
if(largest != i){
swapPtr(a, i, largest);
maxHeapify(a, largest, len);
}
}

/* Building heap from given elements */
void buildMaxHeap(heapNode *a[], int len){
int i = len/2 +1;

for(; i>=0; i--){
maxHeapify(a,i, len);
}
}

/* This function allocates node of heap */
heapNode * createNode(int data){
heapNode *node = (heapNode *)(malloc)(sizeof(heapNode));

if(node)
node->data = data;

return node;
}

/* This function is real implementation of the sliding window algorithm */
void slidingWindowAlgorithm(int buffer[], int N, int K, int bufferLen){

int i = 0, j = 0, s;
heapNode *maxHeap[K+1];
int num = K;

for(int j=0 ; j + N < bufferLen; j++){
/* Put K element from N element window */
for(int i=0;i < K; i++){
/* Since we wold be doing for every window,
avoiding reallocation of node */
if(maxHeap[i]){
maxHeap[i]->data = buffer[i+j];
}
else{
maxHeap[i] = createNode(buffer[i+j]);
}
}
/* Build min heap with those entered elements */
buildMaxHeap(maxHeap,K-1);

/*Now for all remaining N-K-1 elements in window,
check if they fit in max heap */
for(int i=K+j; i< N+j; i++){
heapNode * root = maxHeap[0];
if(buffer[i] < root->data){
root->data = buffer[i];
maxHeapify(maxHeap, 0, K-1);
}
}

/*Print the current max heap, it will contain K smallest
element in current window */
printf("K minimum elements in this window :");
for(int x=0; x < K; x++){
printf("%d ", maxHeap[x]->data);
}
}
}
/* Driver Program to execute above code */
int main(){
int buffer[10] = {1,4,5,6,3,2,4,8,9,6};

int K= 4;
int N =5;

int size = sizeof(buffer)/ sizeof(buffer[0]);

slidingWindowAlgorithm(buffer,N, K,size);
return 0;
}
```

Output of above code for input in figure would be with window as 5 and K=4

``` Current window : 1 4 5 6 3
4 Minimum elements in current sliding window : 5 4 3 1

Current window : 4 5 6 3 2
4 Minimum elements in current sliding window : 5 3 4 2

Current window : 5 6 3 2 4
4 Minimum elements in current sliding window : 5 4 3 2

Current window : 6 3 2 4 8
4 Minimum elements in current sliding window : 6 4 2 3

Current window : 3 2 4 8 9
4 Minimum elements in current sliding window : 8 3 4 2
```

Worst case complexity of sliding window algorithm would be O(n K). K is included as it takes O(K) complexity to build heap of K elements.

One more question which is asked usually on the same concept is find maximum element in sliding window.

In this case, we would maintain a min heap or priority queue. With first K (window size) elements, create a max heap. For next element onward,  remove all the elements which are falling out of the window and then add the new element in max heap. New element will be placed at correct position by heapify. And for each window we can return root of max heap. Solution is simple using C++ priority_queue class. Since we need index for removal of element and real element from priority queue priority decision, we will store both information as a pair. Again we have pair class in C++.

```#include <iostream>
#include <queue>
using namespace std;

typedef pair<int, int> Pair;

void slidingWindowMax(int buffer[], int n, int w, int output[]) {
priority_queue<Pair> Q;
/* first push W elements in priority queue
See we are putting the real value and index */
for (int i = 0; i < w; i++)
Q.push(Pair(buffer[i], i));
//Now for each new element
for (int i = w; i < n; i++) {
// Take the top of the heap and that will be max for previous window.
Pair p = Q.top();
output[i-w] = p.first;
// remove all elements which are falling out of window
while (p.second <= i-w) {
Q.pop();
p = Q.top();
}
// Push new element in queue
Q.push(Pair(buffer[i], i));
}
output[n-w] = Q.top().first;
}
int main() {

int a[]={3,5,4,2,-1,4,0,-3};
int n = sizeof(a)/sizeof(a[0]);
int output[n];

slidingWindowMax(a,n,4,output);
return 0;
}
```

Another good solution which gives us O(n) complexity is using dequeue. Dequeue is a data structure, like a queue only where insertion and deletion can happen at both ends, that is at the end or front.
How does deque help here? We can represent window as a deque where elements are taken from front and deleted from end. Only thing is we need to find the maximum every time in deque, because that is what the ask of the problem is. Is there as way that we can get the maximum in the window at front of deque? Consider this: We have a window which has elements [4,9,3] and when we slide window, we get new element as 11. 4 will be taken out of the deque and 11 inserted at the back. But wait a second. Is there a possibility that 9 or 3 can be maximum in window till 11 is present in deque? No, so why to keep these redundant data in deque. Idea here is to pop out all elements from deque which are smaller than current element and keep that element and elements which are greater than it. Hence in our example,we will keep only 11 in deque. Generalized idea is:

Consider i and j where i>j and a[i]>a[j], then there is no way a[j] can be maximum in window which contains a[i], hence can be removed from deque

So every time front of deque will contain the maximum in that window. Doubts? Just execute above mentioned algorithm on A = [3,5,4,2,-1,4,0,-3].

```Window                  Queue      Max
[3 5 4 2 ] -1 4 0 -3     5 4 2 -1   5
3 [5 4 2 -1 ] 4 0 -3     4          5
3 5 [4 2 -1 4 ] 0 -3     4 0        4
3 5 4 [2 -1 4 0 ] -3     4 0 -3     4
```

Implementation is very easy. I am using C++ as deque is easily available there.

```#include <iostream>
#include<deque>
using namespace std;

void slidingWindow(int buffer[], int n, int w, int output[])
{
deque<int> Q;
int i;
/*Initialize deque Q for first window, put all W elements, however also
removing elements which cannot be maximum in this window */
for (i = 0; i < w; i++)
{
//This is where we are removing all less than elements
while (!Q.empty() && buffer[i] >= buffer[Q.back()])
Q.pop_back();
// Pushing the index
Q.push_back(i);
}

for (i = w; i < n; i++)
{
output[i-w] = buffer[Q.front()];

//update Q for new window
while (!Q.empty() && buffer[i] >= buffer[Q.back()])
Q.pop_back();

//Pop older element outside window from Q
while (!Q.empty() && Q.front() <= i-w)
Q.pop_front();

//Insert current element in Q
Q.push_back(i);
}
output[n-w] = buffer[Q.front()];
}

int main(){
int a[]={3,5,4,2,-1,4,0,-3};
int n = sizeof(a)/sizeof(a[0]);
int output[n];

slidingWindow(a,n,4,output);
return 0;
}
```

Complexity of sliding window algorithm to find maximum in a window is O(n) as there are as many as 2n insert and delete operations on deque. Why?

# Merge K sorted arrays (K-way merge sort)

Given K sorted arrays each having N elements, merge them all in one N*K size array in sorted order. This process is called as K-way merge sort or merge k sorted arrays and used in external merge sort as explained here:Merge sort algorithm

## Merge K sorted array

Since all input arrays are already sorted, candidate for first position in output array will be among first elements of input arrays. How can we find the minimum among all elements at first index of each array? Easy, take those K elements (there are K array, hence K first elements) and build min heap. The root of min heap is least element in all arrays and hence should be the first element in output array.

Great, we have first element selected for output. Also, we have K-1 element min heap. Now what? Now, get second element of array from which the minimum first element was selected.

For this to happen, we need to know which element was selected from which array. Maintain this information with element to point to array it came from and what was position of element. To store additional information, we need complex structure rather than primitive integer. We will use struct available in c, heap will be now of structures and not integers. This comes with more problems, we will see later in post.

Now, based on information stored in heap structure, get next element from appropriate array (we have stored array number in information in heap node). If we have not already considered all elements of that array, put next element at root of min heap and again heapify. This step will gives us second least element in all K elements.
Follow this procedure for N*K times. Once an array elements are considered, we need to replace min heap root with INT_MAX so that it is not considered again.

## Algorithm to merge K sorted arrays

1. Build min heap with first element of all K arrays.
2. Pick root of min element and put it in output array.
3. If there are remaining elements in array, put next element at root of min heap and heapify again
4. If all elements of an array are already considered, put INT_MAX and heapify again.
5. Repeat step 2,3,4 for N*K times.

## Merge K sorted arrays : Implementation

```#include<stdio.h>
#include<stdlib.h>
#define INT_MAX 1000

typedef struct heapNode{
int data;
int arrayNum;
int itemNum;
} heapNode ;

int leftChild(int i){
return (i*2)+1;
}
int rightChild(int i){
return (2*i)+2;
}

heapNode * createNode( int data, int arrayNum, int itemNum){
heapNode * newNode = (heapNode *)malloc(sizeof(heapNode));
newNode->data = data;
newNode->arrayNum = arrayNum;
newNode->itemNum = itemNum;

return newNode;
}

void swap(heapNode * a[], int i, int j){
heapNode * temp = a[i];
a[i] = a[j];
a[j] = temp;
}

void minHeapify(heapNode * a[], int i, int len){
int smallest =i;
int left, right;

left = leftChild(i);
right = rightChild(i);

if(left <= len && a[i]->data > a[left]->data){
smallest = left;
}
if(right <= len && a[smallest]->data > a[right]->data){
smallest = right;
}
if(smallest != i){
swap(a, i, smallest);
minHeapify(a, smallest, len);
}
}

void buildHeap(heapNode *a[], int len){
int i = len/2 +1;
for(; i>=0; i--){
minHeapify(a,i, len);
}
}

void mergeKSortedArrays(int a[5][5], int N, int K, int result[]){
int i;
heapNode *minHeap[K];
/* Put all elements in an array */
for(i=0;i<K; i++){
minHeap[i] = createNode(a[i][0], i, 0);
}

/* Build min heap with those entered elements */
buildHeap(minHeap,K-1);

/* Now we have to take every element one by one and replace
root with that and heapify again */
for(i=0; i<N*K; i++){
heapNode * minNode = minHeap[0];

/* Put the root of min heap in result array */
result[i] = minNode->data;
/* If there are elements to be considered in that array */
if(minNode->itemNum + 1< N){
minHeap[0] = createNode(
a[minNode->arrayNum][minNode->itemNum + 1],
minNode->arrayNum, minNode->itemNum + 1
);
}
/* else put INT_MAX at root */
else{
minHeap[0] = createNode(INT_MAX, minNode->arrayNum,
minNode->itemNum + 1);
}
/* Heapify again */
minHeapify(minHeap, 0, K-1);
}
}

int main(){

int N = 5;
int K = 4;
int a[4][5] = {
2,3,5,6,7,
4,7,8,9,10,
3,5,11,13,45,
1,4,5,7,8
};

int result[K*N];
mergeKSortedArrays(a, N, K, result);

for(int i=0; i<N*K; i++){
printf("%d  ", result[i]);
}

return 0;
}

```

Complexity of algorithm to merge k sorted arrays or K-way merge of arrays will be O(N * K * logN).

# Bit wise operations on numbers

In previous post we discussed basics on bit wise operations. In this post we would take some classic interview questions which can be easily solved if we apply some bit manipulations.These three problems are :

1. Find a missing number in an array
2. Find a missing and duplicate number in an array
3. Find the rightmost bit set in a number

# Find missing number in an array

Given a set of N numbers ranging from 1 to N, one number is missing, find the missing number.Numbers are non-sorted order.
We can easily find the element by having a hash key being numbers in set and increasing the count of the index whenever we encounter number in given set.
This approach required O(N) extra space. We want to avoid that extra space usage. Let’s look at XOR operation first.
0 XOR 0 = 0
0 XOR 1  = 1
1 XOR 0  = 1
1 XOR 1  = 0
Given above rules, we can derive that A XOR A = 0 because this will always make number of ones as even. For example, 9 XOR 9 = 1001 XOR 1001 = 0000.  Do we get some hint?
We know that range of numbers is 1 to N, if XOR all numbers from 1 to N let’s call result as X. and then XOR all numbers which are actually present in set, call it Y and then if we XOR both X and Y, we get the missing number as all the numbers from 1 to N which are present in set will cancel each other. Example, Range is 1 to 5 and  Set as  {1,3,4,5} = {0001, 0011, 0100, 0101}
`Step 1 : XOR all numbers 1 to n`
X =0001 XOR 0010 XOR 0011 XOR 0100 XOR 0101 =  0001
`Step 2 : XOR all numbers in set`
Y = 0001 XOR 0011 XOR 0100 XOR 0101 =  0011
`Step 3 XOR X and Y`
Result  =  0001 XOR 0011 = 0010 = 2 which is over missing element.

Code for above example is as follows

# Find the missing and duplicate number

Given a set of numbers range from 1 to N, one number is missing and one number is duplicate.
Let’s work on an example:  A  = {1,2,3,3,4,5} Range as 5
`Step 1 : XOR all numbers 1 to 5`

X =0001 XOR 0010 XOR 0011 XOR 0100 XOR 0101 =  0001

`Step 2 : XOR all numbers in set`
Y = 0001 XOR 0010 XOR 0011 XOR 0011 XOR 0100 XOR 0101 =  0010
` Step 3 XOR X and Y as Z`

Result  =  0001 XOR 0010 = 0011 Same logic mentioned above goes for this problem too.One more problem which uses similar logic is “Find a number which occurs odd number of times in given input set”

# Find the position of right most set bit

Example : Let be the number be 18 = 00010010
Now if reset all bits except the LSB bit which is set and then take log (base 2), we can get the position of LSB which is set. We can do that by  x & !(x-1)
log2(2) = 1, that is the position of LSB set.
Hence our return value becomes log2(x &!(x-1))
In next post we would discuss couple of more problems on bitwise operations like finding two duplicate elements in a given input set etc.