Game of largest element

Easy
0/40
6 upvotes
Asked in companies
AmazonGoogle inc

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
2 3 1
4
1 2 3 4
Sample Output 1:
3
4
Explanation of Sample Input 1:
For the first test case:
The largest element in the given ‘ARR’ is 3 which is at index 1 (0 based indexing). 

For the second test case:
The largest element in the given ‘ARR’ is 4 which is at index 3.
Sample Input 2:
2
3
3 1 2
1
10
Sample Output 2:
3
10
Explanation of Sample Input 2:
For the first test case:
3 is the largest element in ‘ARR’ which is at index 0.

For the second test case:
10 is the largest element in ‘ARR’ which is at index 0.
Hint

Brute Force

Approaches (2)
Brute Force

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’.
Time Complexity

O(N) where ‘N’ is the number of elements in the given array/list ‘ARR’.

 

We are iterating each element exactly once. So, the time complexity is O(N).

Space Complexity

O(1)

 

Because we are not using any extra space.

Code Solution
(100% EXP penalty)
Game of largest element
Full screen
Console