coding-interview-questionsfacebook-interview-questionsmicrosoft-interview-questionsamazon-interview-questions

**Difficulty:** Medium, **Asked-In:** Facebook, Amazon, Microsoft, Adobe, Morgan Stanley

**Key takeaway:** An excellent problem to learn problem-solving using binary search.

A **sorted** and **rotated** array of size n is given, write a program to find the minimum element in the array.

- Rotation by k times means that the first k sorted elements of the array will move to the last k positions and the last n - k sorted elements move to the first n - k positions (in an anti-clockwise fashion). For example, rotating an array X[0], X[1], X[2], ..., X[n-1] 3 time results in the array X[3], X[4], X[5], ..., X[n-2], X[n-1], X[0], X[1], X[2].
- In the given problem, we don’t know how many times the array is rotated.
- Assume that all elements in the array are unique.

**Examples**

Input: X[] = [5, 6, 7, 8, 9, **1**, 2, 3, 4], Output: 1, Explanation: Array is rotated by 4, so minimum element is present at index 5, which is 1.

Input: X[] = [8, 9, **3**, 4, 5, 6, 7], Output: 3, Explanation: Array is rotated by 5, so minimum element is present at index 2, which is 3.

Input: X[] = [**5**, 6, 7, 8, 9], Output: 5, Explanation: Array is not rotated at all, so minimum element is present at index 0, which is 5.

Input: X[] = [8, **7**], Output: 7, Explanation: Array is not rotated by 1, so minimum element is present at index 1, which is 7.

- A brute force approach using linear search
- An efficient approach using binary search

One basic idea would be to traverse the array from start to end and find the minimum element. For this, we initialize a variable minRotated to track the minimum. Whenever we find a value X[i] less than minRotated, we update the minRotated with the X[i]. So by the end of the loop, the minimum value gets stored in minRotated.

```
int minRotatedArray(int X[], int n)
{
int minRoated = X[0]
for (int i = 1; i < n; i = i + 1)
{
if(minRotated > X[i])
minRotated = X[i]
}
return minRotated
}
```

We are traversing the array once doing constant operations at each iteration, so time complexity = O(n). We are using constant extra space, so space Complexity = O(1).

Now the critical question is: can we think to improve the time complexity using the property of a sorted and rotated array. Is there some insight that can help us to reduce the comparison operations? One idea looks obvious: The input array is almost similar to a sorted array and we need to search for something. Can we think to apply a binary search approach? Let’s explore!

If we look closely then we can recognize three cases:

**Case 1:**When the leftmost value is less than the rightmost value, then the minimum element will be present at the leftmost index. In other words, the array is not rotated and we can return the leftmost value.**Case 2:**When the value at the mid-index is greater than the rightmost value, then the minimum value will be present on the right half.**Case 3:**When the value at the mid-index is less than the rightmost value, then the minimum value will be present on the left half.

So we can think to apply a modified version of binary search where case 2 and case 3 decides the search direction.

- We initialize two variables
**l**and**r**with 0 and n -1. - Now we run a loop till l < r
**If (X[l] < X[r])**, then return X[l].- Now we calculate the mid index i.e.
**mid = l + (r - l)/2** **If (X[mid] > X[r]),**we search the minimum in the right half of the array. For this, we update**l = mid + 1.**- Otherwise, we search in the left part of the array. For this, we update
**r = mid.**

```
int minRotatedArray(int X[], int n)
{
int l = 0
int r = n - 1
while (l < r)
{
if (X[l] < X[r])
return X[l]
int mid = l + (r - l)/2
if (X[mid] > X[r])
l = mid + 1
else
r = mid
}
return X[l]
}
```

We define a function minRotated(int X[], int l, int r), where function parameters **l** and **r** are initialized with 0 and n - 1.

**If (X[l] < X[r])**, we return X[l].- We calculate the mid index i.e.
**mid = l + (r - l)/2** **If (X[mid] > X[r]),**then we search the minimum in the right half of the array. For this, we call the same function with updated left parameter l equal to mid + 1 i.e. return**minRotatedArray(X, mid + 1, r)**.- Otherwise, we search in the left part of the array. For this, we update
**r = mid.**For this, we call the same function with updated right parameter r equal to mid i.e. return**minRotatedArray(X, l, mid).**

```
int minRotatedArray(int X[], int l, int r)
{
if(l < r)
{
if (X[l] < X[r])
return X[l]
int mid = l + (r - l)/2
if (X[mid] > X[r])
return minRotatedArray(X, mid + 1, r)
else
return minRotatedArray(X, l, mid)
}
return X[l]
}
```

At each step of iteration or recursion, we are decreasing the input size by half. In other words, the time complexity of the above approach is equal to the binary search. Time complexity = O(log n).

- The space complexity of iterative solution = O(1)
- The space complexity of recursive solution = O(logn) for the call stack.

- Why are we returning X[l] after the end? Is it necessary?
- Can the above approach work if we have duplicates in the array?
- Can we think of some different approaches to solve this problem?
- Is this operation necessary inside the loop: if(X[l] < X[r]), return X[l]? Can the above approach works if we put this condition before the loop?
- Can we keep loop condition l ≤ r instead of l < r?

- Search in Rotated Sorted Array
- Find the first or last occurrence of a given number in a sorted array
- Find the maximum in an array which is first increasing and then decreasing
- Find the row with the maximum number of 1s

**Enjoy learning, Enjoy algorithms!**

Search in a row-wise sorted 2D matrix

You are given a row-wise sorted 2D matrix and a given integer k, write a program to find whether the integer ‘k’ is present in the matrix or not. The matrix has the following properties: Integers in each row are sorted from left to right and the first integer of each row is greater than the last integer of the previous row.

Find Majority Element in an Array

You are given an array X[] consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.