Last Updated: 14 Feb, 2021
Game of largest element
Easy
Asked in companies
Ninja and his friend are playing a game of finding the largest element in an array/list ‘ARR’ consisting of ‘N’ unique elements. To make it difficult for Ninja to win, his friend rotates 'ARR' K(possibly zero) times to the left about the largest element. Now, it is Ninja’s turn to find and tell the largest element to his friend.
For Example: 'ARR' = [1, 2, 3, 4, 5] after rotating 2 times to the left about its largest element (here, 5) becomes [3, 4, 5, 1, 2].
Your task is to help Ninja determine the largest element in the sorted and rotated ‘ARR’.
For Example: For the rotated 'ARR’ = [4, 5, 1, 2, 3], the largest element is ‘5’ which is at index 1(0 based indexing).
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains a single integer 'N’ denoting the number of elements in the ‘ARR’.
The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the ‘ARR’.
Output Format:
For each test case, print the largest element in the given array/list.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 10^5
1 <= ARR[i] <= 10^5
Where ‘T’ is the number of test cases, ‘ARR’ is the given array and ‘N’ denotes the number of elements in the ‘ARR’.
Time Limit: 1 sec
Approaches
We have a simple brute force solution to this problem. We will iterate through each element in ‘ARR’ and find the largest element. Finally, we return that element as our answer.
Here is the complete algorithm :
- Initialize a variable ‘largestElement’ to the minimum possible value.
- Iterate the array ‘ARR’ and do the following for each index ‘i’:
- If ‘ARR[i]’ > ‘largestElement’ then update ‘largestElement’ as ‘largestElement’ = ‘ARR[i]’.
- Finally, return ‘largestElement’.
For a sorted and rotated array/list, the largest element might be somewhere in between the array/list. We can solve this in O(log N) time using a binary search approach. We will have the lower limit ‘low’ and the upper limit ‘high,’ from which we will calculate the ‘mid’ as ‘(high + low) / 2’. Initial values of ‘low’ and ‘high’ are 0 and ‘N’ - 1 where ‘N’ is the number of elements in ‘ARR’.
Now, the following four cases arise:
- ‘ARR[mid]’ > ‘ARR[high]’: If the mid element is greater than the last element, then the greatest element should be in the second half of the ‘ARR’. So, ‘low’ becomes ‘mid’ + 1. This is because ‘ARR’ is a sorted and rotated array.
- ‘ARR[mid]’ < ‘ARR[high]’: If the mid element is less than the last element, then the largest element should be in the first half. So, ‘high’ becomes ‘mid’ - 1.
- If the mid element is the largest: If the mid element satisfies the property of the largest element (not lesser than its neighbors) i.e. ‘ARR[mid + 1]’ < ‘ARR[mid]’ then, it is our answer.
- If the ‘ARR[mid - 1]’ element is the largest: If the ‘mid’ - 1 element satisfies the property of the largest element (not lesser than its neighbors) i.e. ‘ARR[mid]’ < ‘ARR[mid - 1]’ then ARR[mid - 1]’ is our answer.