Predict the best day to buy and sell the shares

Question

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 N_i is the value of the share on the i+1^th day. The next D lines contain a single integer D_i, where D_i is the profit that needs to be made.

Constraints

1 <= N <= 2x10⁵

1 <= D <= 10

1 <= N_i, D_i <= 10⁸

Output Format

For 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 5

Explanation

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 Code

struct 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();
    }
}

Answer 1

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:

1. Make it work
2. Make it right
3. Make it fast

There should be at least 3 methods, for minimal abstraction:

• Collect input
• Process input
• Produce output

I suppose the online tool factors out time spent processing Console.ReadLine calls.

---

//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];
}

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 type
• Compute the startDay value
• Compute the endDay value
• Compute the difference value
• Mutate the startDay public field value
• Mutate the endDay public field value
• Mutate the difference public field value

Into that:

• Compute the startDay value
• Compute the endDay value
• Call 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.

Answer 2

1. There's no use of IList when you have only lists you can't create an array anyway because you are using Add().

2. When you know your input will be only string you should use int.Parse() instead of Convert.ToInt32

3. Those lines can be replaced by a ternary operator

           if (transactions.Count > 1)
           {
               minimumDaysTransaction = transactions.OrderBy(x => x.difference).First();
           }
           else if (transactions.Count == 1)
           {
               minimumDaysTransaction = transactions[0];
           }
   

Can become

minimumDaysTransaction = transactions.Count > 1 
? minimumDaysTransaction = transactions.OrderBy(x => x.difference).First() 
: minimumDaysTransaction = transactions[0];

4. You can replace one of your for loops with an LINQ expression

   IList<int> sharePrices = new List<int>();
   foreach (string parsedPrice in parsedPrices)
   {
       sharePrices.Add(Convert.ToInt32(parsedPrice));
   }
   

   Like this

   List<int> sharePrices = parsedPrices.Select(int.Parse).ToList();
   

   performance-wise LINQ falls behind a normal for/foreach loop but it brings more readability to your code and also shortens it.

5. Both IList<Transaction> transactions and Transaction minimumDaysTransaction can be moved inside your for loop.

6. Talking about performance here : transactions.OrderBy(x => x.difference).First() you are using OrderBy and First() the second one can be replaced by [0] because direct indexing works faster the method call. OrderBy is not really fast you should replace it with custom ICombarable(T) + a List Sort, however you are using struct not a class implementing interface's in struct can cause some problems, so if You want to implement IComparable(T) you should switch to class.