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[0] is leader and move forward. Remove `A[0]` if `A[1] > A[0]` as A[0] is not leader anymore. Now, if `A[2] > A[1]`, then A[1] cannot be leader.
What if `A[3] < A[2]`, then A[2] may still be leader and A[3] may also be.
What if `A[4] > A[3]`, then A[3] cannot be leader. Can A[2] be leader? Depends if A[4] is less or more than A[2]. 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[0]);

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 [email protected]

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.