I was trying out my hand at solving problems and came across this HackerRank problem. I have written a solution which passes for a few test cases but times out for most others (time limit - 3 seconds). I'd like to know the best way possible to achieve the same.Any pointers as to how the code may be optimized, any approaches/algorithms I should look at, anything that would help me improve the code and optimize the performance would be much appreciated.Reproducing the problem statement below in case the link stops working.Jesse has started stock trading and loves it. He knows the prices of a  share of a particular company over the next N days. He wants to  analyze this data to build a model which can predict the best day to  buy and sell the shares. Given an amount, he wants to know if the  given desirable amount of profit can be made. If yes, he wants to know  the minimum number of days in which it can be made. If there are  multiple ways of buying and selling to achieve that profit, he wants  to know the way which happens the earliest. Note: Jesse can buy only 1  share and not more. He always has to buy before he can sell the share.Input Format The first line contains two integers N and D, where N is  the number of days for which he knows the share values and D is the  number of amounts for which he needs the answer. The next line  contains N space separated integers, where Ni is the value  of the share on the i+1th day. The next D lines contain a  single integer Di, where Di is the profit that  needs to be made.Constraints1 <= N <= 2x1051 <= D <= 101 <= Ni, Di <= 108Output FormatFor each amount of profit given as a query, print in a  new line containing two space separated integers  the day on which  the share was bought and the day on which the share was sold if an  answer exists. If it is not possible to achieve the amount of profit,  print -1. Sample Input 6 2 3 1 2 1 4 5 3 2 Sample Output 4 5 3 5Explanation To achieve a profit of 3, he can either buy on day 2 or day 4  and sell on day 5 or he can buy on day 3 and sell on day 6. The one that  takes the minimum number of days is the one where he buys on day 4 and  sells on day 5. So the answer is 4 5.My Codestruct Transaction{    public int startDay;    public int endDay;    public int difference;}class Solution{    static void Main(string[] args)    {        //get initial inputs        string inputs = Console.ReadLine();        string[] parsedInput = inputs.Split(' ');        int numberOfDays = Convert.ToInt32(parsedInput[0]);        int expectedProfitCases = Convert.ToInt32(parsedInput[1]);        //get share prices        string prices = Console.ReadLine();        string[] parsedPrices = prices.Split(' ');        IList<int> sharePrices = new List<int>();        foreach (string parsedPrice in parsedPrices)        {            sharePrices.Add(Convert.ToInt32(parsedPrice));        }        if (numberOfDays != sharePrices.Count)        {            throw new Exception(INVALID INPUT!);        }        //get expected profits        IList<int> expectedProfits = new List<int>();        for (int i = 0; i < expectedProfitCases; i++)        {            expectedProfits.Add(Convert.ToInt32(Console.ReadLine()));        }        IList<Transaction> transactions;        Transaction minimumDaysTransaction = new Transaction();        //loop through each expected profit, printing result at the end        foreach (int expectedProfit in expectedProfits)        {            //find all transactions which would yield the desired profit            transactions = new List<Transaction>();            for (int i = numberOfDays - 1; i >= 0; i--)            {                for (int j = 0; j < i; j++)                {                    if ((sharePrices[i] - sharePrices[j]) == expectedProfit)                    {                        transactions.Add(new Transaction { startDay = j + 1, endDay = i + 1, difference = i - j });                    }                }            }            //print -1 if no transactions yield desired profit            if (transactions.Count == 0)            {                Console.WriteLine(-1);                continue;            }            //find the transaction which takes least amount of days            if (transactions.Count > 1)            {                minimumDaysTransaction = transactions.OrderBy(x => x.difference).First();            }            else if(transactions.Count == 1)            {                minimumDaysTransaction = transactions[0];            }            Console.WriteLine(minimumDaysTransaction.startDay +   + minimumDaysTransaction.endDay);        }        Console.ReadLine();    }}
Predict the best day to buy and sell the shares
c#;algorithm;programming challenge;time limit exceeded
struct Transaction{    public int startDay;    public int endDay;    public int difference;}This Transaction struct is mutable, and mutable structs are a problem.Making it immutable isn't very complicated:public struct Transaction{    public Transaction(int startDay, int endDay)    {        _startDay = startDay;        _endDay = endDay;        _difference = endDay - startDay;    }    private readonly int _startDay;    public int StartDay { get { return _startDay; } }    private readonly int _endDay;    public int EndDay { get { return _endDay; } }    private readonly int _difference;    public int Difference { get { return _difference; } }}Note the PascalCase naming of public members, and also note that if you're using C# 6, you can use readonly auto-properties to simplify the implementation:public struct Transaction{    public Transaction(int startDay, int endDay)    {        StartDay = startDay;        EndDay = endDay;        Difference = endDay - startDay;    }    public int StartDay { get; }    public int EndDay { get; }     public int Difference { get; }}This will change instantiation from this:transactions.Add(new Transaction { startDay = j + 1, endDay = i + 1, difference = i - j });To that:transactions.Add(new Transaction(j + 1, i + 1));Renaming i and j variables to more meaningful names restores the line's readability:transactions.Add(new Transaction(endDay + 1, startDay + 1));Don't throw System.Exception:if (numberOfDays != sharePrices.Count){    throw new Exception(INVALID INPUT!);}Instead, throw the most meaningful/appropriate existing exception, or make your own. Here it seems an InvalidOperationException would be perfectly acceptable:The exception that is thrown when a method call is invalid for the object's current state. (MSDN)The code is hard to follow, because there is a lot happening in that Main method. If you thought stuffing everything in one method was going to save you the overhead of method calls and therefore perform better, you have fallen prey to premature optimization - the algorithm you've implemented has problems much more significant than whatever overhead comes with method calls.Here's how software should be written:Make it workMake it rightMake it fastThere should be at least 3 methods, for minimal abstraction:Collect inputProcess inputProduce outputI suppose the online tool factors out time spent processing Console.ReadLine calls.//print -1 if no transactions yield desired profitif (transactions.Count == 0){    Console.WriteLine(-1);    continue;}//find the transaction which takes least amount of daysif (transactions.Count > 1){    minimumDaysTransaction = transactions.OrderBy(x => x.difference).First();}else if(transactions.Count == 1){    minimumDaysTransaction = transactions[0];}You never use the empty minimumDaysTransaction value declared outside the loop; that minimumDaysTransaction should be local to each iteration, declared inside the scope of the foreach loop.The bottleneck is obviously the nested loops - I'd extract the entire body of that foreach loop into its own method, and profile to confirm.Already by making the struct immutable, you've turned this:Call the Transaction constructor to create an instance of the value typeCompute the startDay valueCompute the endDay valueCompute the difference valueMutate the startDay public field valueMutate the endDay public field valueMutate the difference public field valueInto that:Compute the startDay valueCompute the endDay valueCall the Transaction constructor to create an instance of the value type (difference value being computed in the constructor, ensuring consistency)That should be faster already, but not by an order of magnitude at all, since you're still facing a nested loop logic.The problem constraints on N are such that there are many possible combinations, and building a lookup table seems impractical.However, you're computing the profits \$D\$ times; each iteration of that foreach loop will re-calculate the same figures over and over again: you'd want to compute them once, and be done with it.Here's a quick implementation that's not exactly per specs (it does produce the expected buy on day 4, sell on day 5 output though) and uses a Tuple<int,int> instead of a Transaction type (IMO the Transaction type is better), but still should give you an idea of what I mean:static void Main(string[] args){    const int n = 6;    int[] sharePrices = {3, 1, 2, 1, 4, 5};    var transactions = new Dictionary<int, List<Tuple<int,int>>>();    for (var endDay = n - 1; endDay >= 0; endDay--)    {        for (var startDay = 0; startDay < endDay; startDay++)        {            var profit = sharePrices[endDay] - sharePrices[startDay];            var transaction = Tuple.Create(startDay + 1, endDay + 1);            if (transactions.ContainsKey(profit))            {                transactions[profit].Add(transaction);            }            else            {                transactions.Add(profit, new List<Tuple<int, int>> {transaction});            }        }    }    var targetProfit = 3;    if (transactions.ContainsKey(targetProfit))    {        var result = transactions[targetProfit].OrderBy(trx => trx.Item2 - trx.Item1).First();        Console.WriteLine(Buy: day {0}\nSell: day {1}, result.Item1, result.Item2);    }    else    {        Console.WriteLine(No result :();    }    Console.ReadLine();}In your case that would be a Dictionary<int, List<Transaction>> - the idea is to pre-compute the profit, and group all transactions by profit achieved. Then you can retrieve all the transactions you need with a single \$O(1)\$ dictionary lookup, so each expectedProfit iteration is exactly instant - all that's left to do is sort the list of transactions so that the one with smallest number of days comes up first, and output that transaction as your result.And meanwhile you've only iterated and computed the possible transactions once, instead of once per target profit value.