Minimum number of steps to move from one city to another Question:
A country X consists of N cities numbered 0 to N-1 . The map of this country can be represented as a cycle — for each valid i, city i has exactly two neighboring cities (i+1)%N and (i-1+N)%N.

The cities in the country are broadly categorized into different types. For each valid i, the type of city i is denoted by A[i].

A person called Suarez wants to travel between some pairs of the cities. You are given Q queries. In each query, Suarez wants to travel from city number Y to a city of type Z. Also, he wants to travel only in a given direction along the cycle.

The direction is represented by a letter — L or R. If it's L, Suarez may only move from city i to city (i-1+N)%N for each valid i. If it's R, he may only move from city i to city (i+1)%N.

You need to find the minimum number of steps Suarez needs to take to reach a city of type Z if he starts moving from city Y in the given direction (he can take zero steps). In one step, Suarez can move from his current city to a neighboring city.

If Suarez can never reach a city of type Z for a given query, print -1 instead.

Input format

The first line of the input contains two space-separated integers N and Q. The next line contains N space-separated integers, where the i-th of these integers represents A[i].

Each of the following Q lines describes a query in the format Y Z D, where Y is an integer denoting the number of the starting city, Z is an integer denoting the type of a target city and D is a letter ('L' or 'R') denoting the direction along the cycle.

Output format

For each query, print a single line containing one integer — the answer to the query.

    Input                                Output
    3 4                                  0
    1 2 3                                2
    0 1 L                                1
    1 3 L                                -1
    2 1 R
    1 5 L


My solution is as follows. It gives TLE. Can you suggest me a better and optimized way of doing it.

    class TestClass {
public static void main(String args[] ) throws Exception {
    Scanner kb=new Scanner(System.in);
    int size=kb.nextInt();
    int queries=kb.nextInt();
    int[] city=new int[size];
    for(int i=0;i&lt;size;i++){
        city[i]=kb.nextInt();
    }
    while(queries--&gt;0){
        int current_city_number=kb.nextInt();
        int destination_city_type=kb.nextInt();
        char direction=kb.next().charAt(0);
        int number_of_steps=0;
        if(city[current_city_number]==destination_city_type){
            System.out.println("0");
        }
        else{
            boolean flag=false;
            for(int i=0;i&lt;size;i++){
                if(destination_city_type==city[i]){  //Checking valid/invalid city type
                    flag=true;
                    break;
                }
            }
            if(flag){                                           //Valid city type
                    for(int i=current_city_number;i&lt;size;){  
                        if(direction=='R')
                        {i=(i+1)%size; number_of_steps++;}
                        else
                        {i=(i-1+size)%size; number_of_steps++;}
                        if(city[i]==destination_city_type){
                            System.out.println(number_of_steps);
                            break;
                        }
                    }
            }
            else{
                System.out.println("-1");                        //Invalid city type
            }
        }
    }
    }
    }
Okay, found problem online and solved it. The trick to the problem (as with most problems) lies in the constraints:



There are a lot of queries, but a small amount of cities. It would seem more important to optimize answering a query time, which is usually done with some precalculation or caching.

In this case, we can think that as there are at most 3000 cities, there is at most 3000 distinct city types. So all queries that don´t ask for an invalid city type (no city has that city type) will have one of those 3000 types. 

We can precalculate for all cities, the query of going to right or left for each of these types, ending with a O(cities * distinct types * 2) complexity, which would be 3000 * 3000 * 2 at most, much better than the original 500000 * 3000.

Then for each query, if the type of city is a valid type (at least one of the cities has it), we have already preprocessed the answer and can answer in O(1). If it isn´t, we just answer with -1.

Another hint is the topic of the problem, which is for practicing multi dimentional arrays. We use this to store the calculation of all valid queries to then answer in O(1).

I advice you to try coding the problem again with these hints.

If you get stuck:


   Even though city types can go up to 200000, we can map them to values between 1 and 3000, because we only have 3000 cities.


And if you still can´t solve it, here is my solution:


  
        Scanner kb=new Scanner(System.in);
        int cities = kb.nextInt();
        int queries = kb.nextInt();

        int types[] = new int[cities];
        HashSet uniqueTypes = new HashSet();

        for (int i = 0; i &lt; cities; i++) {
            types[i] = kb.nextInt();
            uniqueTypes.add(types[i]);
        }

        HashMap mapping = new HashMap();

        Integer idx = 0;
        for (Integer type: uniqueTypes) {
            mapping.put(type, idx++);
        }

        for (int i = 0; i &lt; cities; i++) {
            types[i] = mapping.get(types[i]);
        }

        int closestRight[][] = new int[cities][cities];
        int closestLeft[][] = new int[cities][cities];

        for(int i = 0; i &lt; cities; i++) {
            for (int j = 0; j &lt; cities; j ++) {
                closestRight[i][j] = closestLeft[i][j] = cities + 1; 
            }
        }

        for(int i = 0; i &lt; cities; i++) {
            for (int j = 0; j &lt; cities; j ++) {
                int leftIndex = ((i - j) + cities) % cities;
                int rightIndex = (i + j) % cities;
                int rightCityType = types[rightIndex];
                int leftCityType = types[leftIndex];

                closestRight[i][rightCityType] = Math.min(closestRight[i][rightCityType], j);
                closestLeft[i][leftCityType] = Math.min(closestLeft[i][leftCityType], j);

            }
        }

        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new
        FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);

        for (int i = 0; i &lt; queries; i++) {
            int city = kb.nextInt();

            int destinationType = kb.nextInt();

            if (mapping.get(destinationType) == null) {
                out.write("-1" + "\n");
                continue;
            }

            destinationType = mapping.get(destinationType);

            if (kb.next().charAt(0) == 'L') {
                out.write(closestLeft[city][destinationType] + "\n"); 
            } else {
                out.write(closestRight[city][destinationType] + "\n"); 
            }


        }

        out.flush();