In last post, we discussed inversions in array. One more problem on similar lines, given an array of integers, find all leaders in array. First of all, let’s understand what is a leader. Leader is an element in array which is greater than all element on right side of it. For example:
In array below element 8, 5 and 4 are leaders. Note that element at index 6 is leader by not at index 1. Another example, in this there are only two leaders which is 10 and 9. Clarifying question which becomes evident in example is that if last element is considered as leader? Based on answer from interviewer, function should print or not last element.

## Leaders in array : thought process

What is brute force approach? Scan through all elements in array one by one and check if there is any greater element on right side. If there is no such element, number is leader in array.

```package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
* Created by sangar on 7.4.18.
*/

for(int i=0; i<a.length; i++){
int j = 0;
for(j=i+1; j<a.length; j++){
if(a[i] < a[j]){
break;
}
}
}

}

public static void main(String[] args) {
int a[] = new int[]{90, 20, 30, 40, 50};
}
}
```

Complexity of brute force solution to find leaders in array is O(n2).

Let’s go to basics of question: All elements on right side of an element should be less than it for that element to be leader. Starting from index 0, we can assume that A is leader and move forward. Remove `A` if `A > A` as A is not leader anymore. Now, if `A > A`, then A cannot be leader.
What if `A < A`, then A may still be leader and A may also be.
What if `A > A`, then A cannot be leader. Can A be leader? Depends if A is less or more than A. For each element, we are going back to all previous candidate leaders in reverse way and drop all candidates which are less than current element. Does it ring bell?Well, data structure which supports this kind of operation Last In First Out, is stack.
Stack supports two operations : push and pop. Question is when to push and pop and elements from stack for our problem.

Push element if it less than top of stack. If top of stack is less than current element, pop elements from stack till an element which is greater than current element. When entire array is scanned, stack will contain all leaders.

• Start with empty stack. Push first element of array on to it.
• For each element in array
• Till current element is greater than top, pop element.
• Push current element on to stack.
•  At the end of processing, stack will contain all leaders.

## Leaders in array : Implementation using stack

```package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
* Created by sangar on 7.4.18.
*/

Stack<Integer> s = new Stack();
s.push(a);

for(int i=1; i<a.length; i++){
while(s.peek() < a[i]){
s.pop();
}
s.push(a[i]);
}

while (!s.empty()){
}
}
public static void main(String[] args) {
int a[] = new int[]{90, 20, 30, 40, 50};
}
}
```

Complexity of algorithm using stack to find leaders in array is O(n) with extra O(n) space complexity.

Scanning array in reverse
How can we avoid the additional space used by stack? When we are scanning forward, there are chances that some element going forward will be current candidate leader. That is why we keep track of all candidate leaders. How about scanning array from end, in reverse order. Start with last index and keep track of maximum we saw till current index. Check if element at current index is greater than current max, save it as leader and change current max to current element.

##### Algorithm to find leaders without extra space
• Set current max as last element of array.
• For i = n-1 to 0 index of array
• if a[i] greater than current max
• Change current max to a[i]

### Leaders in array implementation without extra space

```package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
* Created by sangar on 7.4.18.
*/

int currentMax = Integer.MIN_VALUE;
for(int i=a.length-1; i>=0; i--){
if(a[i] > currentMax ){
currentMax = a[i];
}
}

}
public static void main(String[] args) {
int a[] = new int[]{90, 20, 30, 40, 50};
}
}

```

Complexity of reverse array algorithm to find leaders in array is O(n) with no added space complexity.

Please share you views,suggestion, queries or if you find something wrong. If you want t contribute to algorithms and me, please reach out to us on communications@algorithmsandme.com

# Pair with given sum in array

Given an array a[] and a number X, find two elements or pair with given sum X in array. For example:

```Given array : [3,4,5,1,2,6,8] X = 10
Answer could be (4,6) or (2,8).```

Before looking at the post below, we strongly recommend to have pen and paper and git it a try to solve it.

## Pair in array with given sum : thought process

Ask some basic questions about the problem, it’s a good way to dig more into problem and gain more confidence. Remember interviewers are not trained interrogators, they slip hint or two around solution when you ask relevant questions.

• Is it a sorted array ? If not, think additional complexity you would be adding to sort it
• If duplicates present in array?
• Whether returning first pair is enough or should we return all such pairs with sum equal to X?
• If there can be negative numbers in array?

This problem is used regularly in interviews because it tests so many things about your programming knowledge.
It validates that if you can traverse array properly, with both lower and higher bounds. It also checks your optimizing ability once you got a working solution. Can you work with additional constraints? Are you able to work with more than one data structure like array and hash together to solve a problem?

## Find pairs with given sum : Using sorting

Let’s go with an assumption that input is sorted array and if not, we will sort it? If you want to know how to sort an array efficiently,refer Quick sort or Merge sort
With sorted array, we can apply below algorithm to find a pair with given sum.

1. Initialize two variable `left` = 0 and `right` = array.length-1, These variable are used to traverse array from two ends of array.
2. While two variables left and right do not cross each other,
3. Get sum of elements at index left and right, i.e `A[left] + A[right]`
4. If sum is greater than X, move towards left from end i.e decrease right by 1
5. Else if sum is less than X,then move towards right from start, i.e increment left
6. At last, if sum is equal to X, then return `(left, right)` as pair.

##### Example

Let’s see how this works with an example and then we will implement it. Given an array as shown and sum = 17, find all pair which sum as 17. Initialization step, left = 0 and right = array.length – 1 A[left] + A[right] = 20 which is greater than sum (17), move right towards left by 1. Again, A[left] + A[right] = 18 which is greater than sum (17), move right towards left by 1. At this point, A[left] + A[right] is less than sum(17), hence move left by 1 Now, A[left] + A[right]  is equal to sum and so add this pair in result array. Also, decrease right by 1, why? At this point, A[left] + A[right] is less than sum(17), hence move left by 1 Again, A[left] + A[right] is less than sum(17), hence move left by 1 A[left] + A[right]  is equal to sum and so add this pair in result array. Also, decrease right by 1. Since, left and right point to same element now, there cannot be a pair anymore, hence return. ```package com.company;

import javafx.util.Pair;

import java.util.ArrayList;

/**
* Created by sangar on 5.4.18.
*/
public class PairWithGivenSum {
public static ArrayList<Pair<Integer, Integer>> pairWithGivenSum(int[] a, int sum){
int left = 0;
int right = a.length - 1;

ArrayList<Pair<Integer, Integer>> resultList = new ArrayList<>();

while(left < right){
/*If sum of two elements is greater than
sum required, move towards left */
if(a[left] + a[right] > sum) right--;
/*
If sum of two elements is less than
sum required, move towards right
*/
if(a[left] + a[right] < sum) left++;
if(a[left] + a[right] == sum){
right--;
}
}
return resultList;
}
public static void main(String[] args) {
int a[] = new int[] {10, 20, 30, 40, 50};

ArrayList<Pair<Integer, Integer>> result = pairWithGivenSum(a,50);
for (Pair<Integer, Integer> pair : result ) {
System.out.println("("+ pair.getKey() + "," + pair.getValue()  + ")");
}
}
}
```

Complexity of this algorithm to find a pair of numbers in array with sum X is dependent on sorting algorithm used. If it is merge sort, complexity is `O(n log n)` with added space complexity of `O(n)`. If quick sort is used, worst case complexity is `O(n2)` and no added space complexity.

## Find a pair with given sum in array : Without sorting

In first method,  array is modified, when it is not already sorted. Also, Preprocessing step (sorting) dominates the complexity of algorithm. Can we do better than `O(nlogn)` or in other words, can we avoid sorting?

Additional constraint put on problem is that  you cannot modify original input.  Use basic mathematics, if A + B = C, then A = C-B.  Consider B is each element for which we are looking for A. Idea is to scan entire array and find all A’s required for each element. Scan array again and check there was B which required current element as A.
To keep track of required A values, we will create an hash, this will make second step O(1).
We can optimize further by scanning array only once for both steps.

1. Create an hash
2. Check element at each index of array
2.a If element at current index  is already in hash. return pair of current index and value in hash
2.b If not, then subtract element from sum and store (sum-A[index], index) key value pair in hash.

This algorithm scans array only once and does not change input. Worst case time complexity is O(n), hash brings additional space complexity. How big should be the hash? Since, all values between sum-max value of array and sum-min value of array will be candidate A’s hence hash will be of difference between these two values.

This solution does not work in C if there are negative numbers in array. It will work in languages which have HashMaps in-built. For C, we have to do some preprocessing like adding absolute of smallest negative number to all elements. That’s where our fourth question above helps us to decide.

### Pairs with given sum : implementation

```package com.company;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashMap;

/**
* Created by sangar on 5.4.18.
*/
public class PairWithGivenSum {
public static ArrayList<Pair<Integer, Integer>> pairsWithGivenSum2(int[] a, int sum){
int index = 0;
ArrayList<Pair<Integer, Integer>> resultList = new ArrayList<>();

HashMap<Integer, Integer> pairMap = new HashMap<>();
for(int i=0; i< a.length; i++){
if(pairMap.containsKey(a[i])){
}
pairMap.put(sum-a[i], i);
}
return resultList;
}
public static void main(String[] args) {
int a[] = new int[] {10, 20, 30, 40, 50};

ArrayList<Pair<Integer, Integer>> result = pairsWithGivenSum2(a,50);
for (Pair<Integer, Integer> pair : result ) {
System.out.println("("+ pair.getKey() + "," + pair.getValue()  + ")");
}
}
}

```

Please share if there is some error or suggestion to improve. We would love to hear what you have to say. If you want to contribute to learning process of other by sharing your knowledge, please write to us at communications@algorithmsandme.com

# Find Minimum  in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array.  Problem today is bit different, there is no key to find first of all. Ask of problem is to find minimum in sorted rotated array.

To understand problem, first let’s understand what is sorted array and then what is sorted rotated array.

An array is called sorted where for all i and j such that i < j, A[i] <= A[j]. A rotation happens when last element of array is push at the start and all elements of array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again, all elements are moved to right, it’s rotation by 2 and so on.

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

## Find minimum in sorted rotated array : Thought process

As always, first come up with a brute force solution without worrying about any optimizations as of now. Simplest way would be to scan through array and keep track of minimum. Complexity of this method is O(N), however, what is the fun if we do it in O(N) time complexity ?

In brute force solution, we did not use the fact that array is sorted and then rotated. Let’s forget about rotation and concentrate only in sorted part.

What is minimum element in sorted array? Obviously, it is the first element of array. We see that all the elements on right side of minimum elements are greater than minimum.

What will happen if start rotating array now, is the condition that all the elements on right of minimum element are greater than it still hold? Yes, it does. Either there will be no element on right side of minimum or the will be definitely greater than it.

So, idea is we randomly pick an element and see if elements on right side of it are greater. No need to go through each element, compare selected element with last index element, if last index element is greater, selected element can be minimum. (Remember we are working sorted array!).
Start comparing with middle element. What information comparison between middle and end element gives us?
Array could have been in two ways : It is rotated more than half or it is rotated less than half.
If middle element is less than last element, array is rotated less than half, and hence, minimum element should be on the left half of array. If middle element will be greater than last element, array is rotated more than half, hence minimum element should be in right part of array. What if middle element is the minimum element? See if element on left and right of mid are both greater than element at mid, mid is index of minimum element.
Let’s take an example and see how this method works and then come up with concrete algorithm to find minimum in sorted rotated array. For example, array is given as below. First, we find the mid, check if mid is minimum?  A[mid] > A[mid-1], so it cannot be minimum element. So, see if array is rotated more than half or less than half.
Since, A[mid] > A[end], array is rotated more than half and hence, minimum should be on the right side. We will discard the left subarray and focus on right subarray to find minimum. Again, find the mid, is mid the minimum? No, so compare it with end, since, A[mid] < A[end],  minimum should be on the left side, discard right subarray.  Find mid again and this time mid satisfy the condition : A[mid-1] and A[mid+1] both are greater than A[mid], hence, A[mid] should be the minimum element. Can you come up with execution trace when array is not rotated more than half to start with?

## Minimum in sorted rotated array : Algorithm

1. Find mid = start + (end- start) /2
2. See if mid is minimum element i.e is A[mid] < A[mid-1] and A[mid] < A[mid+1]. If yes, return mid
3. Else if A[mid] > A[end]:
• Array is rotated more than half, minimum should be on right subarray
• Continue with subarray with start =  mid+1
4. Else if A[mid] < A[end]:
• Array is rotated less than half, minimum should be on left subarray
• Continue with subarray with end = mid-1

### Minimum in sorted rotated array implementation

```package com.company;

/**
* Created by sangar on 22.3.18.
*/
public class SortedRotatedArray {

public static int findMinimumIterative(int[] input, int start, int end) {

while (start < end) {
int mid = start + (end - start) / 2;

if (mid == 0 || (input[mid] <= input[mid+1]
&& input[mid] < input[mid-1])) return mid;
else if (input[mid] > input[mid]) {
/* Array is rotated more than half, hence minimum
should be in right sub-array
*/
start  = mid + 1;
} else {
/* Array is rotated less than half, hence minimum
should be in left sub-array
*/
end  = mid - 1;
}
}
return start;
}
public static void main(String[] args) {
int[] input = {10,11,15,17,3,3,3,3,3,3};

int index = findMinimumIterative(input,0, input.length-1);
System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

}
}
```

Recursive implementation of same function

```package com.company;

/**
* Created by sangar on 22.3.18.
*/
public class SortedRotatedArray {

public static int findMinimumRecursive(int[] input, int start, int end){

if(start < end){
int mid = start + (end - start) / 2;

if(mid == 0 || (input[mid] < input[mid-1]
&& input[mid] <= input[mid+1] ) ) return mid;

else if(input[mid] > input[end]){
/* Array is rotated more than half and hence,
search in right subarray */
return findMinimumRecursive(input, mid+1, end);
}else {
return findMinimumRecursive(input, start, mid - 1);
}
}
return start;
}

public static void main(String[] args) {
int[] input = {3,10,11,15,17,18,19,20};

int index = findMinimumRecursive(input,0, input.length-1);
System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

}
}
```

Complexity of algorithm to find minimum in sorted rotated array is O(log N), with recursive implementation having implicit space complexity of O(log N).

What did we learn from this problem?
First learning is to always go for brute force method. Second, try to draw the effect of any additional operations which are done on original array. In sorted rotated array, try to have rotation one by one and see what impact it has on minimum element? Try to classify individual class and design your algorithm. In this problem, we identify that based on how many times array is rotated, minimum can be in right or left subarray from middle and that gave idea for discarding half of the array.

Please share if there is something wrong or missing, or any improvement we can do. Please reach out to us if you are willing to share your knowledge and contribute to learning process of others.

# Find element in sorted rotated array

To understand how to find element in sorted rotated array, we must understand first, what is a sorted rotated array? An array is called sorted where for all i and j such that i < j, A[i] <= A[j]. A rotation happens when last element of array is push at the start and all elements on array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again all elements are moved to right again, it’s rotation by 2 and so on.

Question which is very commonly asked in Amazon and Microsoft initial hacker round interviews or telephonic interviews : Given a sorted rotated array, find position of an element in that array. For example:

A = [2,3,4,1] Key = 4, Returns 2 which is position of 4 in array

A = [4,5,6,1,2,3] Key = 4 returns 0

## Find element in sorted rotated array : Thought process

Before starting with any solution, it’s good to ask some standard questions about an array problem, for example, if duplicate elements are allowed or if negative numbers are allowed in array? It may or may not change the solution, however, it gives an impression that you are concerned about input range and type.

First thing to do in interview is come up with brute force solution, why? There are two reasons : first, it gives you confidence that you have something solved, it may not be optimal way but still you have something. Second, now that you have something written, you can start looking where it takes most of time or space and attack the problem there. It also, helps to identify what properties you are not using which are part of the problem and help your solution.

First thing first, what will be the brute force solution? Simple solution will be to scan through the array and find the key. This algorithm will have `O(N)` time complexity.

There is no fun in finding an element in sorted array in O(N) 🙂 It would have been the same even if array was not sorted. However, we already know that our array is sorted. It’s also rotated, but let’s forget about that for now. What do we do when we have to find an element in sorted array? Correct, we use binary search.

We split the array in middle and check if element at middle index is the key we are looking for? If yes, bingo! we are done.

If not, if A[mid] is less that or greater than key. If it is less, search in right subarray, and it is greater, search in left subarray. Any which way, our input array is reduced to half. Complexity of binary search algorithm is `log (N)`. We are getting somewhere 🙂

### Sorted rotated array

However, our input array in not a plain sorted array, it is rotated too. How does things change with that. First, comparing just middle index and discarding one half of array will not work. Still let’s split the array at middle and see what extra conditions come up?
If `A[mid]` is equal to key, return middle index.
There are two broad possibilities of rotation of array, either it is rotated more than half of elements or less than half of elements. Can you come up with examples and see how array looks like in both the cases?  If array is rotated by more than half of elements of array, elements from start to mid index will be a sorted.

If array is rotated by less than half of elements of array, elements from mid to end will be sorted.

Next question, how do you identify the case, where array is rotated by more or less than half of elements? Look at examples you come up with and see if there is some condition?

Yes, the condition is that if `A[start] ` < `A[mid]`, array is rotated more than half and if A[start] > `A[mid]`, it is rotated by less than half elements.  Now, that we know, which part of array is sorted and which is not. Can we use that to our advantage?

Case 1 : When array from start to mid is sorted. We will check if `key > A[start]` and `key < A[mid]`. If that’s the case, search for key in `A[start..mid]`. Since, `A[start..mid]` is sorted, problem reduces to plain binary search. What if key is outside of start and middle bounds, then discard A[start..mid] and look for element in right subarray. Since, `A[mid+1..right]` is still a sorted rotated array, we follow the same process as we did for the original array.

Case 2 : When array from mid to end is sorted. We will check if `key >A[mid]` and `key < A[end]`. If that’s the case, search for key in A[mid+1..end]. Since, `A[mid+1..end]` is sorted, problem reduces to plain binary search. What if key is outside of mid and end bounds, then discard `A[mid..end]` and search for element in left subarray. Since, `A[start..mid-1]` is still a sorted rotated array, we follow the same process as we did for the original array.

Let’s take an example and go through the entire flow and then write concrete algorithm to find element in sorted rotated array.

Below is sorted rotated array given and key to be searched is 6. We know, A[start] > A[mid], hence check if searched key fall under range A[mid+1..end]. In this case, it does. Hence, we discard A[start..mid].

At this point, we have to options:  either fallback to traditional binary search algorithm or continue with same approach of discarding based on whether key falls in range of sorted array. Both methods work. Let’s continue with same method.

Again find middle of array from middle +1 to end. A[mid] is still not equal to key. However, A[start] < A[mid]; hence, array from A[start] to A[middle] is sorted. See if our key falls between A[start] and A[mid]? Yes, hence, we discard the right sub array A[mid..End]

Find the middle of remaining array, which is from start to old middle – 1. Is A[mid] equal to key? No. Since, A[start] is not less than A[mid], see if key falls under A[mid+1..end], it does, hence discard the left subarray.

Now, new middle is equal to key are searching for. Hence return the index. Similarly, we can find 11 in this array. Can you draw the execution flow that search?

## Algorithm to find element in sorted rotated array

1. Find mid =  (start + end)/ 2
2. If A[mid] == key; return mid
3. Else, if A[start] < A[end]
• We know, left subarray is already sorted.
• If A[start] < key and A[mid] > key :
• Continue with new subarray with start and end = mid – 1
• Else:
• Continue with new subarray with start = mid + 1 and end
4. Else
• We know, right subarray is sorted.
• If A[mid] < key and A[end] > key :
• Continue with new subarray with start  = mid + 1 and end
• Else:
• Continue with new subarray with start and end = mid – 1

### Find element in sorted rotated array : Implementation

```package com.company;

/**
* Created by sangar on 22.3.18.
*/
public class SortedRotatedArray {

public static int findElementRecursive(int[] input, int start, int end, int key){

if(start <= end){
int mid = start + (end - start) / 2;

if(input[mid] == key) return mid;

else if(input[start] <= input[mid]){
/*Left sub array is sorted, check if
key is with A[start] and A[mid] */
if(input[start] <= key && input[mid] > key){
/*
Key lies with left sorted part of array
*/
return findElementRecursive(input, start, mid - 1, key);
}else{
/*
Key lies in right subarray
*/
return findElementRecursive(input, mid + 1, end, key);
}
}else {
/*
In this case, right subarray is already sorted and
check if key falls in range A[mid+1] and A[end]
*/
if(input[mid+1] <= key && input[end] > key){
/*
Key lies with right sorted part of array
*/
return findElementRecursive(input, mid + 1 , end, key);
}else{
/*
Key lies in left subarray
*/
return findElementRecursive(input, start, mid - 1, key);
}
}
}
return -1;
}

public static void main(String[] args) {
int[] input = {10,11,15,17,3,5,6,7,8,9};

int index = findElementRecursive(input,0, input.length-1, 6);
System.out.print(index == -1 ?

}
}
```

Iterative implementation

```package com.company;

/**
* Created by sangar on 22.3.18.
*/
public class SortedRotatedArray {

public static int findElementIteratve(int[] input, int start, int end, int key) {

while (start <= end) {
int mid = start + (end - start) / 2;

if (input[mid] == key) return mid;

else if (input[start] <= input[mid]) {
/*Left sub array is sorted, check if
key is with A[start] and A[mid] */
if (input[start] <= key && input[mid] > key) {
/*
Key lies with left sorted part of array
*/
end = mid - 1;
} else {
/*
Key lies in right subarray
*/
start  = mid + 1;
}
} else {
/*
In this case, right subarray is already sorted and
check if key falls in range A[mid+1] and A[end]
*/
if (input[mid + 1] <= key && input[end] > key) {
/*
Key lies with right sorted part of array
*/
start = mid + 1;
} else {
/*
Key lies in left subarray
*/
end  = mid - 1;
}
}
}
return -1;
}

public static void main(String[] args) {
int[] input = {10,11,15,17,3,5,6,7,8,9};

int index = findElementIteratve(input,0, input.length-1, 6);
System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

}
}
```

Complexity of above recursive and iterative algorithm to find an element in a rotated sorted array is `O(log n)`. Recursive implementation has implicit space complexity of `O(log n)`

What did we learn today? We learned that it’s always better to come up with non-optimized solution first and then try to improve it. Also helps to correlate problem with similar and simpler problem like we understood first what is best way to find an element in sorted array and then extrapolated the solution with additional conditions for our problem.

I hope that this post helped you with this problem and many more similar problems you will see in interviews.

# Binary Indexed Trees (Fenwick Tree)

Why Binary Indexed Tree?Consider an array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}, you have to find the sum of a range say (1,5). One way of doing this can be by keeping the sum of elements from index 0 to index i, where 0 <= i<= n. So the array with all the cumulative sum is "sum" :{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136} and to calculate sum from 1 to 5 we can simply do sum – sum. This will take O(n) precomputing time and O(q) with q queries with O(1) complexity per query

Let us modify the question now, Suppose we have another query that modifies value at some index i,  this will make us calculate the sum from index ‘i’ to ‘n’ again. Now the complexity will be O(q*n) if there are ‘q’ queries. Segment trees can be used to solve this in O(q*log(n)). (Refer to this post for segment trees).
Coding for segment trees can be a very lengthy and Hectic process, Segment Trees require a very large memory space, Debugging a code of segment tree is very difficult. Another approach to solve the above problem is to use Binary Indexed Tree data structure, which also has O(q*log(n))
complexity but BIT (Binary Indexed Trees) are much easier to code and require very less memory space than segment trees. Binary Indexed trees are also called Fenwick Trees.

### Representation of Binary Indexed Tree

Consider an input array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}. Binary Indexed Tree or Fenwick tree is represented using an array of size n, where n is the length of the input array. Let’s call the binary indexed tree of this array “tree[n]”. tree[idx] (where idx is some index of BIT) will store the sum of values of the given input array from index (idx – 2^r +1)  to index idx.
Here, r is the position of the last set bit (from left to right) in binary representation of the index idx.
So, for example idx = 6, binary representation of 6 is 0110, Therefore the last set bit from left to right is the 1st bit (considering 0 based index) which makes r = 1. Therefore tree stores the sum from index 5 to index 6.

The diagram below shows value of r for every index from 1 to 16. The color of rth index is changed for better understanding.

Therefore, tree = A + A + A + A. To calculate “tree[idx]”, we can store the cumulative sum from index “0” to index “idx”  where (0 <= idx < n) in an array and then subtract "sum[idx – 2^r + 1]" from "sum[idx]". This will find value of tree[idx] in O(1).
So, tree[idx] = sum[idx] – sum[idx – 2^r + 1].

### How to Find the value of the last set bit?

Let num be an integer whose last set bit we want to isolate. Note that num can be represented in the form a1b, where a represents the series of bits before last set bit and b represents all the zeros after the last set bit.
Integer (-num) can be found out using 2’s complement of num, which is done by adding 1 to the inverse of num. the expression for finding twos complement is as follows,
(a1b)¯ + 1 = a¯0b¯ + 1

Since b consists of all zeroes, so b¯  consists all ones.Therefore, finally we have -num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b.
Now, we can easily isolate the last digit, using bitwise operator AND with num and -num a 1 b &   a¯1 b       ——————–     = (0…0)1(0…0)
So, to calculate the value of (idx – 2^r + 1) we just have to do the following operation

idx = idx – (idx & -idx);

### Construction of Binary Indexed Tree

For every index “idx”, tree[idx] is calculated in O(1) complexity using the expression tree[idx] = sum[idx] – sum[idx – 2^r + 1], where “sum[idx]” stores the cumulative sum from index “0” to index “idx”.

The code is shown below.

```int* construct_bit(int sum[], int length)
{
int *tree = new int[length];
tree = 0;

for(int idx = 1; idx < length; idx++)
{
int left, right;

left = idx - (idx & (-idx));
right = idx;

tree[idx] = sum[right] - sum[left];
}

return tree;
}
```

Sum Between Two Indices :
To calculate sum between two given indices l and r. we will have to calculate sum from index ‘0’ to index ‘r’, then the same thing from index ‘0’ to index ‘l’ and then calculate the difference between of the results obtained.
Let us consider an example of index 13, to calculate sum from index 0 to index 13, array tree will play a major role here, we know that tree will store sum of 13th index only, tree stores sum from 9th index to 12th index and tree stores sum from  index 0 to index 8. So, adding tree + tree + tree will give us cumulative sum from index 0 to index 13.
tree = tree + tree + tree
tree = tree + tree + tree
(Binary representation)

Note that, complexity of our algorithm to calculate sum from index 0 to index idx will be O(log(idx)). The diagram below illustrate this.

The Code to find sum from index 0 to index idx is shown below

```int read_sum(int tree[], int index)
{
int sum = 0;
while(index > 0)
{
sum += tree[index];
index -= (index & -index);
}
return sum;
}
```

Update Value at some position and update BIT :
If a value at some index idx is added by some value say val, then we will have to update the tree at all those places which are affected by this index. For example, if value at 9 is changed, then tree, tree, tree …so on, will be changed because
tree = tree + tree; tree = tree + tree + tree + tree; while we were reading the sum, we were removing last set bit from index until it became zero. Now, while updating the tree we should add one set bit to the index idx until it becomes greater than or equal to length.
Below is the code to do that.

```void update_tree(int idx, int val, int tree[])
{
int length = sizeof(tree)/sizeof(int);
idx++;
while(idx <= length)
{
tree[idx] += val;
idx += idx & (-idx);
}
}
```

Binary Indexed Trees easy to code, the code length is very short and should be used wherever possible.
The Links of some practice problems are given below :
http://www.spoj.com/problems/UPDATEIT/

http://www.spoj.com/problems/CTRICK/

# Find Kth smallest element in two sorted arrays

We have already solved a problem to find kth smallest element in an array using quicksort modification and min heap. Today, our problem is to find Kth smallest element in two sorted arrays. In other words, given two sorted arrays, find Kth smallest element of the union of these two arrays.

For example if A = [10, 20, 40, 60] and B =[15, 35, 50, 70, 100] and K = 4 then solution should be 35 because union of above arrays will be C = [10,15,20,35,40,50,60,70,100] and fourth smallest element is 35.

## Kth smallest element in two sorted arrays

As I always insist on doing : what will be the most brute force solution for this problem. Simple, merge two sorted arrays into one and return Kth smallest element merged array. There are different ways to merge two sorted arrays , merge part of merge sort will be most efficient when two parts are already sorted. Time complexity of merge is O(n+m) and additional space complexity of O(m+n) where m and n are sizes of two sorted arrays.

If you are preparing for an interview, you can signup for a free session to find a coach to help you with your preparation.

Now that we already know brute force solution, can we do better than this?
the kth smallest element can be present in any one of the two arrays. How many elements can we include from first array A, with size m, it can be max(k-1, m).
Let’s suppose we took i elements from the first array, how many maximum numbers of elements we can take from array B? Since, we have zero-based indexing of array,

```i+j = k-1
``` Now, we need to find combination of `i` and `j` such that all elements from 0 to i are less than B[j] and all elements from 0 to j should be smaller than A[i], and min(A[i], B[j]) will be the kth smallest element. For A[i], all elements from index 0 to i-1 are smaller, all we need to check is that all elements in array B from index 0 to index j-1 are smaller too. Therefor A[i] >= B[j-1]

Similarly for B[j], it must satisfy the condition B[j] >= A[i-1]. In order to be kth smallest element, index i and j have to satisfy two conditions, (A[i] >= B[j-1] && B[j] >= A[i-1]) and also i+j  =  k-1 or j = k-1-i

What if A[i] < B[j-1]  as we saw in the first picture?  That means i is too small, we need to increase i and when we increase i and A[i], j and B[j] is decreased automatically, which makes it possible to satisfy A[i] >= B[j-1]. In the same vain when B[j] < A[i-1],  i is too big and it’s a good choice to decrease it.

This is where binary search comes into picture. We can start i as mid of array A, j = k-i and see if this i satisfies the condition. There can be three possible outcomes for condition.
1. `A[i-1]` >= `B[j]` and `B[j-1]` <=`A[i]` is true, we return the index min(A[i], B[j])
2. If`B[j-1]` > `A[i]`, in this case, A[i] is too small. How can we increase it? by moving towards right. If i is increased, value A[i] is bound to increase, and also it will decrease j. In this case, B[j-1] will decrease and A[i] will increase which will make B[j-1] >=A[i] is true. So, limit search space for i to  mid+1 to min(k, m)
3. `A[i-1]` > `B[j]`, means A[i-1] is too big. And we must decrease i to get A[i-1] >=B[j]. Limit search space for i from 0 to i-1.

Since, i is bound by 0 to min(k-1,m), j will never go below 0. When i or j is o, return min(A[i], B[j]).

There is lot to process I know, let’s take an example and see how it works. Below are the two sorted arrays and K  = 7. First thing to notice is that k is greater than m, size of array A. Hence range of i will be 0 to m i.e. 5. Find mid, i = 2 and j = k – 2-1 = 4 Now, A[i] < B[j-1], it is evident that we chose i too small. Search space is now from i+1 to m.

Again we find mid which is index 4 of array A. Index j = 2. At this point condition A[i-1] <= B[j] is false. This means, we chose i too big and hence we decrease range till i-1 which now 3. New i and j are shown below. Condition A[i-1] <= B[j] and B[j-1] <= A[j] is true. Return min(A[i], B[j]) as kth smallest element which is 6. ## Code to find Kth smallest element in two sorted arrays

```package com.company;

/**
* Created by sangar on 19.4.18.
*/
public class KthSmallestElement {

public static double findKthSmallestElement(int[] A, int[] B, int k){

int[] temp;

int lenA = A.length;
int lenB = B.length;

if(lenA + lenB < k) return -1;

int iMin = 0;
int iMax = Integer.min(A.length, k-1);

int i = 0;
int j = 0;

while (iMin <= iMax) {
i = (iMin + iMax) / 2;
j = k - 1 - i; // because of zero based index
if (B[j - 1] > A[i]) {
// i is too small, must increase it
iMin = i + 1;
} else if (i > 0 && A[i - 1] > B[j]) {
// i is too big, must decrease it
iMax = i - 1;
} else {
// i is perfect
return Integer.min(A[i], B[j]);
}
}
return -1;
}

public static void main(String[] args){
int[] a = {1,3,5,6,7,8,9,11};
int[] b = {1,4,6,8,12,14,15,17};

double smallest = findKthSmallestElement(a,b, 9);
System.out.println("Kth smallest element is : " + smallest);
}
}

```

Complexity of algorithm to find Kth smallest element in union of two arrays is O(log(N+M)).

Please share if there is something wrong or missing. we would be glad to hear from you. If you are preparing for an interview and want to understand how to approach it, please book a free coaching session.

## Subarray with sum zero

Given an array of positive and negative integers, find a subarray with sum zero in that array. For example, in the array given below, there are two subarrays whose elements sum to zero.

Brute force method to find subarray with sum zero will be to find all sub-arrays of the array and then add them individually to see if any subarray adds up to zero. There can be `n * (n-1)` subarrays for a given array of size n, so the complexity of brute force solution is `O(n2)`.

```package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
* Created by sangar on 3.12.18.
*/
public class SubarrayWithZeroSum {
public int [] findSubarrayWithZeroSumBrute(int[] a){
int len = a.length;

for(int i=0; i<len; i++){
int  sum  = 0;
for(int j=i; j<len; j++){
sum += a[j];
if(sum == 0){
return Arrays.copyOfRange(a,i,j+1);
}
}
}
return new int;
}
}
```

#### Test cases

```package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class SubarrayWithSumZeroTest {

SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

@Test
public void subarrayWithZeroSumBruteTest() {

int[] a = {2, -3, -1, 4};
int [] output = {-3, -1, 4};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
}

@Test
public void subarrayWithZeroSumBruteNoSubArrayTest() {

int[] a = {2, -3, -2, 4};
int [] output = {};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
}

@Test
public void subarrayWithZeroSumBruteOneElementTest() {

int[] a = {2, 0, -1, 4};
int [] output = {0};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
}
}
```

### Find subarray with sum zero: thoughts

A subarray is a contiguous part of an array. Let’s say we find the sum of subarray starting at 0 and ending at any index i. So, T[i] represents the sum of subarray A[0..i].

What if we have two indices i and j; such that `i< j` and `T[i] = T[j]`. In this case, all the elements which are between index i and index j add up to zero and that is our subarray with sum zero.
Length of subarray with sum zero will be j-i+1.

#### Implementation

```package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
* Created by sangar on 3.12.18.
*/
public class SubarrayWithZeroSum {
public int [] findSubarrayWithZeroSum(int[] a){

int len = a.length;

int [] T = new int[len];

T = a;
for(int i=1; i<len; i++){
T[i] = T[i-1] + a[i];
}

//Complexity of below code is O(n^2)

for(int i=0; i<len; i++){
for(int j=i+1; j<len; j++){
if(T[i]== T[j]){
return Arrays.copyOfRange(a, i+1, j+1);
}
}
}
return new int;
}
}
```

#### Test cases

```package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class SubarrayWithSumZeroTest {

SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

@Test
public void subarrayWithZeroSumTest() {

int[] a = {2, -3, -1, 4};
int [] output = {-3, -1, 4};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSum(a)));
}

@Test
public void subarrayWithZeroSumNoSubArrayTest() {

int[] a = {2, -3, -2, 4};
int [] output = {};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSum(a)));
}

@Test
public void subarrayWithZeroSumOneElementTest() {

int[] a = {2, 0, -1, 4};
int [] output = {0};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSum(a)));
}
```

The complexity of the algorithm to find a subarray with zero sum in a given array of integers is `O(n2)` with an additional space complexity of `O(n)` to store sum till index i.

We can optimize it further by creating a hash of all the sums which we see while adding. When we add the index i to already calculated sum till index i-1, we check if the new sum is zero? If yes, then subarray from 0 to index i add up to zero. If there is already a sum present which is equal to the current sum then there is subarray with sum zero between index when we saw the sum last and current index.

```package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
* Created by sangar on 3.12.18.
*/
public class SubarrayWithZeroSum {

public int [] findSubarrayWithZeroSumOptimized(int[] a){

int len = a.length;

HashMap<Integer, Integer> T = new HashMap<Integer, Integer>();

int sum  = 0 ;
for(int i=0; i<len; i++){
sum  += a[i];
if(T.get(sum) != null){
return Arrays.copyOfRange(a,T.get(sum)+1, i+1);
}
T.put(sum, i);
}

return new int;
}
}
```

#### Test cases

```package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class SubarrayWithSumZeroTest {

SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

@Test
public void subarrayWithZeroSumOptimizedTest() {

int[] a = {2, -3, -1, 4};
int [] output = {-3, -1, 4};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
}

@Test
public void subarrayWithZeroSumOptimizedNoSubArrayTest() {

int[] a = {2, -3, -2, 4};
int [] output = {};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
}

@Test
public void subarrayWithZeroSumOptimizedOneElementTest() {

int[] a = {2, 0, -1, 4};
int [] output = {0};
assertEquals(Arrays.toString(output),
Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
}

}
```

The complexity of this method is `O(n)` with additional space of `O(n)` in worst case.

# Minimum jumps to reach end of array

Given an array of integers, find minimum jumps to reach end of the array. Condition is that you can maximum jump a[i] indices from index i.

For example, in following array, minimum jumps required are 2.

At index 1, we can either jump 0, 1 or 2 indices ahead. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4. So total number of jumps would be 3.

However if we jump only 1 index ahead, next A[i] will allow us to jump 3 indices ahead, doing so we will reach at the end of the array. So minimum number of jumps to reach at the end of array is 2.

## Minimum number of jumps : thought process

What would be the brute force method to solve this? At each index, you try all possible jumps and get the combination which gives you the minimum jumps. This method will have exponential complexity which we do not want.

What is the original problem? It’s `minJumps(start, end)` Of all the jumps possible from start, let’s say we go to index k, then what how does problem reduces? Well, now we have to find minimum number of jumps from k to end. How to decide on k now? We try all k values from start+1 to start + a[i].

```minJumps(start, end) = Min ( minJumps(k, end) )
for all k reachable from start
```

Now, we have clear recursion relationship, what should be the base case? When `k + A[k]` > end, or `k == end`, we should return 1 as there would be only one jump required from k to end now.

```package com.company;

/**
* Created by sangar on 10.10.18.
*/
public class MinimumJumps {

public int minimumNumberOfJump(int[] a, int start, int end){
//If start == end, we reached the end, return 0.
if(start == end) return 0;

//if current element is 0, you cannot jump to end at all
if(a[start] == 0) return Integer.MAX_VALUE;

int minimumJumps = Integer.MAX_VALUE;

for(int k=start+1; k<=start+a[start] && k<=end; k++){
/*
For each K from start+1 to end, find the minimum jumps.
*/
int jumps = minimumNumberOfJump(a,k,end);
if(jumps != Integer.MAX_VALUE && jumps + 1 <; minimumJumps){
minimumJumps  = jumps + 1;
}
}
return minimumJumps;
}
}
```

Test cases for above function

```package test;

import com.company.MinimumJumps;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class MinimumJumpTest {

MinimumJumps tester = new MinimumJumps();

@Test
public void baseTest() {

int[] a = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
assertEquals(3,
tester.minimumNumberOfJump(a,0, a.length-1));
}

@Test
public void arrayContainsZeroTest() {

int[] a = {1, 3, 0, 0, 0, 2, 6, 7, 6, 8, 9};
assertEquals(Integer.MAX_VALUE,
tester.minimumNumberOfJump(a,0, a.length-1));
}

@Test
public void nullArrayTest() {

assertEquals(0, tester.minimumNumberOfJump(null,0, 0));
}

@Test
public void arrayWithTwoElementsTest() {

int[] a = {1, 0};
assertEquals(1,
tester.minimumNumberOfJump(a,0, a.length-1));
}
}
```

Let’s see execution trace of above function for an input.

From the above execution tree, we notice that some subproblems are calculated again and again. This is typically known as overlapping subproblems.
Also, optimal solution to subproblem actually lead us to optimal solution for original problem which is optimal subproblem structure. These two property are must to apply dynamic programming to a problem.

What if we store minimum number of jumps required to reach a particular index. To reach first index, jumps required is 0. `Jump[i]` represents the number of reach index i. Solution to reach at the end of the array would be Jump[n-1]. How do we feel this array? For each i,  from  j = 0 to i-1 and check if j+a[j] <= i, if yes, update `jump[i] = min (jump[i], jump[j]+1)`.

### Minimum number of jumps: dynamic programming approach

```package com.company;

/**
* Created by sangar on 10.10.18.
*/
public class MinimumJumps {

public int minimumNumberOfJumpDP(int[] a){

if(a == null || a.length == 0) return 0;

if(a == 0) return Integer.MAX_VALUE;

int[] jump = new int[a.length];

//no jumps required for first element
jump = 0;

for(int i=1; i<a.length;i++){
jump[i] = Integer.MAX_VALUE;

for(int j=0; j<i; j++){
if(j+a[j]>=i && jump[j] != Integer.MAX_VALUE ){
jump[i] = Integer.min(jump[i], 1 + jump[j]);
}
}
}
return jump[a.length-1];
}
}
```

Complexity of dynamic programming approach to find minimum number of jumps to reach end of an array is `O(n2)` with space complexity of `O(n)`

If you are interested to solve this problem in `O(n)` time, please visit stack overflow discussion

Please share if there is something wrong or missing. If you are interested in taking coaching from one of our experienced teachers, please reach out to us at communications@algorithmsandme.com

# Peak in array

Given an unsorted array, find a peak in array. A peak is defined as an element which is not smaller than its immediate neighbors. In an unsorted array, there can be many such peaks, referred to as local Maxima. Mathematically, ith element is called as peak following property holds true:

```A[i-1] <= A[i] >=A[i+1]
```

For first element and last elements of array, left and right neighbors respectively, are considered as negative infinity.

```A = A[n] = -infinity
```

For example, peak in following array would be 6 or 7 Can you identify the peak in this array? What would be peak in sorted array? It will be the last element of array and similarly, for reverse sorted array, first element will be peak.

## Peak  in array : Thought process

I recommend two things: First, get your pen and paper to practice this problem yourself. Second, try to come up with brute force solution as soon as possible. Why? Because it adds to your confidence, when you have some solution already in hand.

Brute force approach to find peak in an array of integers will be to scan through it and for each element, check if greater than it’s greater than previous and next element.  If it is, return index of that element. In worst case we would end up scanning whole array (in a sorted array), so worst case complexity of brute force solution is O(N)

Obviously, this would not have been an interview question, if expectation was to solve it in O(N) complexity, anyone with basic programming knowledge can solve it. There is no way to differentiate a good candidate from an average based on this question then. However, interviewer expects you to solve it in better than O(N) complexity and that’s where problem becomes interesting.

What if we do not go linear and randomly check index m for local maxima? If it is local maxima, we are good, return the index of that element. If it is not peak and given that array is unsorted, three situations possible at that index :
1. Array is rising toward right, that means, next element is greater than current and it’s previous element. 2.  Array is falling towards right, that means, next element is less than current and it’s previous element. 3.  It’s a valley, where current element is less than both previous and next element. In first situation, maximum should be on the right side of current index, why? In second situation, peak will be in left side of current index.

If A[m] < A[m+1], A[m] cannot be peak. However, if A[m+2] is less than A[m+1] is less than A[m+1], then A[m+1] can be a peak or some subsequent element can be. In worst case it would be the last element of array if whole A[m..end] is sorted.
If A[m] < A[m-1], in that case, either A[m-1] is peak or some element preceding it can surely be. In worst case, first element will be the peak.

### Algorithm to find peak in array

Now question is how to select m? We want to minimize the worst case number of elements to check after splitting, which is possible by splitting the array in middle. Take mid as the starting point, this is classic case of divide and conquer  approach as we will discard half of the array based on certain condition.

1. Find mid = low + (high-low)/2
2. If A[mid-1] <= A[mid] =>A[mid+1], then return mid
3. If A[mid-1] > A[mid], high = mid-1
4. If A[mid+1] > A[mid], low = mid+1
5. Repeat step 1 to 4 till there are more than one element in array. Else return that last element.

Let’s take an example and see if this algorithm works. We have given array a as below

## Find mid and see if mid is peak we are looking for, in this case it is not as A[mid] is less than A[mid+1].We will discard left subarray and look for peak in right subarray starting from mid+1. New low and high are shown, we find new mid. Is new mid, local maxima? No, as it is less than previous and next element, it is valley. We will discard right subarray and look for peak in left subarray. Now, there is only one element, hence it should be peak in array. ## Peak in array : Implementation

```package com.company;

/**
* Created by sangar on 25.3.18.
*/
public class BinarySearcchAlgorithm {

public  static int findPeak(int[] a){
int low = 0;
int high = a.length-1;

while (low<high){
int mid = low + (high-low)/2;
if(mid == low ) return a[low] > a[high] ? low:high;

//If mid is local maxima, return it.
if(a[mid-1] <= a[mid]
&& a[mid] >= a[mid+1]) return mid;
else if(a[mid-1] > a[mid]) high = mid-1;
else low = mid+1;
}
return low;
}

public static void main(String[] args) {
int[] input = {1,2,6,5,3,7,4};

int index = findPeak(input);
System.out.print("Peak found at : " + index);
}
}
```

Always remember to check for array with two elements, that will catch almost all bugs regarding boundary overflow. Also, notice that since we are accessing mid+1 and mid-1 indices of array, make sure that these indices are within bounds of array. These two things are very important for a solution to be correct and acceptable in interview. Also, to understand more about binary search algorithm and how it works, please refer to Binary search algorithm

Complexity of divide and conquer algorithm to find peak in unsorted array is O(log n). Recurrence relation for this would be T(n) = T(n/2) + c

Please share if there is something wrong or missing. If you want to contribute to website and help others to learn, please reach out to us on communications@algorithmsandme.com

# Move all zeros at the end of the array

Given an array, which contains random numbers, including zero. We have to move all zeros at the end of the array. For example input array is 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 a difference between the last element of the array and size of the given input array. That will be the number of zeros in the input array. Fill all those spots with zero.

```#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]);
}
}

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

Simple it is O(N). There is another problem which can be solved with the same approach. Problem is to delete consecutive duplicate elements except the first in an array. For example, input array is { 0,1,1,3,3,5,0,0,6,6}  {0,1,3,5,0,6}