Topic: Arrays
Questions Successfully Completed: 1
1) Help Classmates | Medium |
Question
Input: N = 5, arr[] = {3, 8, 5, 2, 25} Output: 2 5 2 -1 -1 Explanation: 1. Roll number 1 has 3 marks. The first person who has less marks than him is roll number 4, who has 2 marks. 2. Roll number 2 has 8 marks, he helps student with 5 marks. 3. Roll number 3 has 5 marks, he helps student with 2 marks. 4. Roll number 4 and 5 can not pick anyone as no student with higher roll number has lesser marks than them. This is denoted by -1. Output shows the marks of the weaker student that each roll number helps in order. ie- 2,5,2,-1,-1
Time Complexity : O(n2) --> Could be improved to O(N)
Space Complexity : O(N)
class Solution {
public static int[] help_classmate(int arr[], int n)
{
// Brute Force
int k=0;
boolean flag=false;
int[] arr2 = new int[n];
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
flag=false;
if(arr[j]<arr[i]){
arr2[k++]=arr[j];
flag = true;
break;
}
}
if(flag==false){
arr2[k++] = -1;
}
}
arr2[k] = -1;
return arr2;
}
}
Thank you for reading:)