Can someone please help me with a solution to this problem?

Question

I am a novice in solving DSA problems. I am stuck to start an approach to this problem. Can someone please provide me help or reference to this problem?

Question

N people are standing in a queue based on descending order of their age, find the last person's name with the given age K. If not found, return "Not found".

Input Format

First line contains two integers N, K - Number of people, the given age.
Second line contains N integers - The ages of people.
Third line contains N strings - The names of people.

Output Format

Print the name of the last person with the given age or "Not found" if not present.

Sample Input

6 30
80 30 30 7 3 3
Sam Will Roy Lane Pam Jim

Sample Output

Roy

Explanation

The people with age 30 in order are Will, Roy. The last person from them is "Roy".

Constraints

1 <= N <= 10^5
1 <= K, Age[i] <= 10^5
1 <= |Person's name| <= 10

Here is my code:

import java.util.*;

class FindLastPersonOfAgeK{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        List<Integer> ages = new ArrayList<Integer>();
        List<String> people = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            ages.add(sc.nextInt());
        }
        for (int i = 0; i < n; i++) {
            people.add(sc.next());
        }
        String ans = findLastPersonOfAgeK(ages, people, k);
        System.out.println(ans);
        sc.close();
    }

    static String findLastPersonOfAgeK(List<Integer> ages, List<String> people, int k){
         
    }
}

I am not able to think of which data structure would help me solve the problem — shrimaan0205, Dec 06 '22 at 05:54
@shrimaan0205 Please specify your question and input format clearly — Faheem azaz Bhanej, Dec 06 '22 at 06:06
@FaeemazazBhanej I have edited the question, now I hope its clear. — shrimaan0205, Dec 06 '22 at 06:09
Your lists are suitable for this task (as well as arrays, arraylists etc). You can also use list/array of pairs(age,name). — MBo, Dec 06 '22 at 06:10

score 1 · Answer 1 · answered Dec 06 '22 at 06:18

1

Here are a couple of pointers to help you out:

Array/list is a suitable data structure for this problem.
To improve the complexity of searching, you can use binary search to find the index of the last element with age = K.
Using the found index, you can find the name of the person.

answered Dec 06 '22 at 06:18

Abhinav Mathur

7,791
3
10
24

Hey, thanks for providing an approach. – shrimaan0205 Dec 06 '22 at 08:46
@shrimaan0205 if it solves your intended purpose, consider marking it as the accepted answer – Abhinav Mathur Dec 06 '22 at 19:07

Abra · Accepted Answer · 2022-12-06T08:29:06.353

You don't need to use List since you know the number of elements – it is the first number on the first line of input entered by the user. In the code in your question, it is the variable n. Hence you can use arrays rather than Lists.

Assuming the input is always valid, i.e. all the integers are not negative and the ages are entered in descending order, all you need do is iterate the ages array in reverse order. Once you find an element of ages that equals k, you have found the last element. Get its index and return the element in people at that index.

As an optimization, once an element in ages is greater than k, there is no need to continue iterating through ages.

import java.util.Scanner;

public class FindLastPersonOfAgeK {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] ages = new int[n];
        String[] people = new String[n];
        for (int i = 0; i < n; i++) {
            ages[i] = sc.nextInt();
        }
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            people[i] = sc.next();
        }
        String ans = findLastPersonOfAgeK(ages, people, k);
        System.out.println(ans);
        sc.close();
    }

    static String findLastPersonOfAgeK(int[] ages, String[] people, int k) {
        for (int i = ages.length; --i >= 0;) {
            if (ages[i] == k) {
                return people[i];
            }
            else if (ages[i] > k) {
                break;
            }
        }
        return "Not found";
    }
}

Note that after calling method nextInt (of class java.util.Scanner) and before calling method next (also of class java.util.Scanner) you need to call method nextLine. Refer to Scanner is skipping nextLine() after using next() or nextFoo()

When I run the above code, using the sample input from your question, I get the following:

6 30
80 30 30 7 3 3
Sam Will Roy Lane Pam Jim
Roy

The first three lines above are the inputs and the last line is the value returned by method findLastPersonOfAgeK.

Hey thanks for making it simple to understand, it is much more simple if we do not use list. — shrimaan0205, Dec 06 '22 at 08:40

Can someone please help me with a solution to this problem?

2 Answers2