Best Algorithm to avoid nested loops without Brute Force approach

I want to make this method run as fast as possible.

int[] p = new int[] {1,4,4,5,1,3,6};
int[] q = new int[] {2,1,3,1,6,4,3};
int k =4.
void nestLoop(){
 for(int i = 0; i < q.length; i++){
     for(int j = 0; j < p.length; j++){
       //code continues 
       // inside here...
       //This approach 
        // takes a longer 
         //time to finish 
         // executing. I need a better algorithm

      }


  }
}

To be clearer; at q[0], p = 1, since 1 is less than q[0], choose 1, and p[4] is also lower, choose 1; hence the answer when it is q[0] are 1 and 1 : but because 1 and 1 are two ints, they are not equal to k = 4, then return 0. If the answer had been 1, 1,1,1 then the number is 4 which is equal to k. [1,1,1,1] will be returned. The same for other q and so on

If I understand correctly you are returning either k or 0, correct?

Then this is the way to do it:

int[] p = new int[] {1,4,4,5,1,3,6};
int[] q = new int[] {2,1,3,1,6,4,3};
int k =4.

void notNested()
{
    TreeSet<Integer> ts = new TreeSet<Integer>();
    // Find the kth smallest number in the array.
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
    for (int p1 : p)
    {
        if (pq.size() < k)
        {
            pq.add(p1);
        } else if (pq.peek() > p1)
        {
            pq.poll();
            pq.add(p1);
        }
    }

    int ksm = pq.poll();
    // For each q, compare against kth smallest only.
    for (int q1 : q)
    {
        if (q1 >= ksm)
        {
            results.add(k);
        }
        else
        {
            results.add(0);
        }
    }
}

If the number of different elements in p is relatively small compared to the total number of elements, the following might work. If, however, there are many different elements, or even all elements are different, then it will be much slower.

• create a Map mapping elements to their indices, e.g. [1,4,4,5,1,3,6] would become {1: [0,4], 4: [1,2], 5: [3], 3: [5], 6: [6]}
• from that map, get the lists of indices for all elements smaller than the current element from q
• put those into a Heap, or Priority Queue, sorted by the next unused index for that element
• pop lists from the heap, get the first index, and put them back onto the heap for the next index until you get k indices

If there are many repeated elements (and only then), this may somewhat reduce the complexity. For P elements in p, d of which being distinct, Q elements in q, and k, this should have complexity of O(P + Q*(d+k*log(d))) (P for creating the map, and d for selecting the lists and k heap operation with log(d) for all the Q queries).

This is a solution using Java Streams:

package javaapplication3;
import java.util.Arrays;
import java.util.stream.*;

public class JavaApplication3 {
    public static void main(String[] args) {

        int[] p = new int[] {1,4,4,5,1,3,6};
        int[] q = new int[] {2,1,3,1,6,4,3};
        int[][] results = new int[q.length][]; // Array of arrays to store results
        int k =4;
        
        // For each element q[i], execute in parallel
        IntStream.range(0, q.length).parallel().forEach(i -> {
            final int qi = q[i];
            // Get first k elements of p <= q[i]
            results[i] = Arrays.stream(p).filter(v -> v <= qi).limit(k).toArray();            
        });
        
        for(int i=0; i<q.length; i++) {
            int[] result = results[i];
            System.out.print("Values less or equal than " + q[i] + ": {");
            for (int v : result)
                System.out.print(" " + v);
            System.out.println(" }");
        }

    }    
}

Output:

Values less or equal than 2: { 1 1 }
Values less or equal than 1: { 1 1 }
Values less or equal than 3: { 1 1 3 }
Values less or equal than 1: { 1 1 }
Values less or equal than 6: { 1 4 4 5 }
Values less or equal than 4: { 1 4 4 1 }
Values less or equal than 3: { 1 1 3 }

Note: You can optionally sort p which will improve performance if p is large and k is small.