Predict the best day to buy and sell the shares

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.


Constraints


1 5


1 i, Di 8


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

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 work

• Make it right

• 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 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>>();
for (var endDay = n - 1; endDay >= 0; endDay--)
{
for (var startDay = 0; startDay > {transaction});
}
}
}

var targetProfit = 3;
if (transactions.ContainsKey(targetProfit))

StackExchange Code Review Q#138342, answer score: 6