[Solved] Closest Friends Contest Problem

There are N persons standing in a line from left to right. This line is represented with an array of size N and the elements of the array are the height of the persons. For each person the closest friend is the closest person to his left whose height is strictly smaller than him. If for any person there is no person to his left whose height is smaller than him print -1 else print the index of smaller friend (0-based indexing).

Input: 
First line contains an integer T which denotes number of test cases. Next line contains an integer N which which is the size of the array. Next line of each test case contain N space seperated integers denoting the array  .

Output: 
For each print -1 or index of the closet friend, if found.

Constraints:
1 <= T <= 10000
1 <= N <= 10⁵
0 <= A[i] <= 10⁵

Example :
Input :
1
6
1 3 4 1 3 8
Output :
-1 0 1 -1 3 4

Solution

import java.io.*;
import java.util.*;
import java.lang.*;

class GFG {
    public static void getClosestFriends(int[] arr, int n){
        Stack<Integer> st = new Stack<Integer>();
        for(int i=0; i<n; i++){
            while(!st.empty() && arr[st.peek()]>=arr[i]){
                st.pop();
            }
            if(!st.empty()){
                System.out.print(st.peek()+" ");
            } else {
                System.out.print("-1 ");
            }
            st.push(i);
        }
        System.out.println();
    }
    
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine().trim());
		while(t-->0){
		    int n = Integer.parseInt(br.readLine().trim());
		    int[] arr = new int[n];
		    String[] inputline = br.readLine().trim().split(" ");
		    for(int i=0; i<n; i++)arr[i]=Integer.parseInt(inputline[i]);
		    getClosestFriends(arr, n);
		}
	}
}

#include<bits/stdc++.h>
using namespace std;

int main(){

    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        stack<int> s;
        for(int i=0;i<n;i++){
            while(!s.empty()&&a[s.top()]>=a[i]){
                s.pop();
            }
            if(!s.empty()){
                cout<<s.top()<<" ";
            }
            else{
                cout<<-1<<" ";
            }
            s.push(i);
        }
        cout<<endl;
    }
    return 0;
}

Happy Learning – If you require any further information, feel free to contact me.