Ninja In Interview

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in company
Morgan Stanley

Problem statement

Ninja is preparing for DSA interviews and in an interview, he was given an array of size ‘N’ and was asked to check if the array is sorted in ascending order or not.

Return 1 if the array is sorted, else return 0.

EXAMPLE: 
Input: 'N' = 2, ‘ARR’ = [1, 2, 5, 6]

Output: 1

As we can see that ‘ARR’ is sorted in ascending order so the answer will be 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

For each test case, the first line will contain ‘N’ the number of elements in array ‘ARR’ and the next line will contain all the elements of ‘ARR’.
Output format : 
For each test case, print 1 of the array is sorted else print 0.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
1 <= 'N' <= 10^3
1 <= ‘ARR[i]’ <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
3
1 2 3
4
10 15 12 20
Sample Output 1 :
1
0
Explanation Of Sample Input 1 :
For the first case:
All the elements of the array are greater than or equal to the previous element of it except for the first element of the array as there is no element before it. Hence the answer will be 1.

For the second case:
At 2nd index (0-based indexing) we can see that 12 is not greater than 15 so the array is not sorted so the answer is 0.
Sample Input 2 :
2
1
1
5
1 2 2 2 5
Sample Output 2 :
1
1
Hint

Can you try the above method recursively?

Approaches (2)
Recursive

For each element except for the first, check if it is greater than or equal to the previous element. If it is then the array is sorted else not.
 

Algorithm :  
 

Bool isSortedRec( int ARR[], int I, int LAST, int N)`

//where ‘LAST’ is the last element, ‘ARR[]’ is the array and ‘I’ is a current index, and ‘N’ is array size:

  • If ‘I’ is greater than or equal to ‘N’ return true.
  • Check if current element of the array ‘ARR[i]’ is >= ‘LAST’:-
    • Return isSorted(ARR[I], ARR, I+1, N).
  • Else return false.
     

Bool isSorted(int ARR[], int N)

// where ‘ARR’ is the initial array and ‘N’ is the size of the array.

  • Returns isSortedRec(ARR, 0, -1, N).
Time Complexity

O(N), Where ‘N’ is the size of an input array ‘ARR’.

 

As we are traversing the whole array of size ‘N’, The time complexity will be O(N)

Space Complexity

O(N), Where ‘N’ is the size of an input array ‘ARR’.

 

As we are using recursion and there will be maximum ‘N’ calls hence space due the recursion stack will add up the O(N) space complexity.

Code Solution
(100% EXP penalty)
Ninja In Interview
Full screen
Console