Which products should be purchased with the given amount of money: Hackerrank? I am writing code for the challenge given here . Below the text:


  Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they
  pool their money to buy ice cream. On any given day, the parlor offers
  a line of flavors. Each flavor has a cost associated with it. Given the value of and the of each flavor for trips to the Ice Cream
  Parlor, help Sunny and Johnny choose two distinct flavors such that
  they spend their entire pool of money during each visit. ID numbers
  are the 1- based index number associated with a cost. For each trip to the parlor, print the ID numbers for the two types
  of ice cream that Sunny and Johnny purchase as two space-separated
  integers on a new line. You must print the smaller ID first and the
  larger ID second.
  
  For example, there are flavors having cost = [2, 1, 3, 5, 6]. Together they have money = 5 to spend.
  They would purchase flavor ID's 1 and 3  for a cost of 2 + 3 = 5  . Use 1 based indexing
  for your response.


I have written code for the problem. However, it is running for most of the test cases except three. The error message that they show is that "Your code did not execute within the time limits". Apparently the code needs to be optimized. Can anyone please tell how may I do that?

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the whatFlavors function below.
    static void whatFlavors(int[] cost, int money) {

         int baseItem=0, comparedItem = 0,totalAmount=0, chosenFlavour1=0,
                chosenFlavour2=0,flag=0;
        for(int i = 0 ; i&lt;(cost.length-1); i++)
        {
            baseItem = cost[i];
            for(int j = (i+1); j&lt; (cost.length);j++)
            {
                comparedItem= cost[j];
                totalAmount = baseItem + comparedItem;

                if(totalAmount == money)
                {
                    chosenFlavour1 = i;
                    chosenFlavour2 = j;
                    flag = 1;
                    break;
                }

            }

            if(flag == 1)
            {
               break; 
            }
        }

        chosenFlavour1++;
        chosenFlavour2++;
        System.out.println(chosenFlavour1+" "+chosenFlavour2);


    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr &lt; t; tItr++) {
            int money = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] cost = new int[n];

            String[] costItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i &lt; n; i++) {
                int costItem = Integer.parseInt(costItems[i]);
                cost[i] = costItem;
            }

            whatFlavors(cost, money);
        }

        scanner.close();
    }
}
Your algorithm is slow in some cases because of the time complexity O(n^2). (starting the second loop from i+1 makes it twice faster than starting from 0, but it doesn't change the time complexity which has much greater impact on performance)

To improve your time complexity you need to reduce the amount of times you look at items in the array. One way of doing it is by first sorting it (more precisely, sorting index-value pairs to keep record of the original indexing) and then iterating over the sorted array once (O(n)) while taking advantage of the fact that it is sorted. I'll leave you the task of learning about integer sorting algorithms (of time complexity O(n log n)), and only explain how to use the sorted array to find the final answer.

You can look at both edges of the array (smallest and biggest number), if their sum is too small you can increase it by advancing the lower-edge index to look at a bigger number, and if the sum is too big you can decrease it by advancing the higher-edge index to look at a smaller number. Repeat it until you reach the needed sum, then get the original indices and increment them to get the IDs you need for the output.

As @vnp hinted, there is a better solution than mine (with time complexity O(n)) using a hash table.