HackerRank woman codesprint: minimum cost

Lauren has a chart of projected prices for a house over the next n
years, where the price of the house in the i-th year is P_i. She
wants to purchase and resell the house at a minimal loss according to
the following rules:

• The house cannot be sold at a price greater than or equal to the price it was purchased at (i.e., it must be resold at a loss).

• The house cannot be resold within the same year it was purchased.

Find and print the minimum amount of money Lauren must lose if she
buys the house and resells it within the next n years.


https://www.hackerrank.com/contests/womens-codesprint-2/challenges/minimum-loss

The minimum cost algorithm is implemented in C++ set, Java TreeSet, no timeout. But, C# code using SortedSet has a timeout issue. C# SortedSet uses extension methods, using LINQ to simulate TreeSet floor method. I need help with avoiding LINQ performance issues as well as algorithm design, code style, etc.

Java code using TreeSet:

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

public class Solution {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int numYears = sc.nextInt();
    long[] data = new long[numYears];
    for (int i = 0; i  values = new TreeSet<>();
    long best = Long.MAX_VALUE;
    for (int i = numYears-1; i >= 0; i--) {
        Long smaller = values.floor(data[i]);
        if (smaller != null) {
            long diff = (data[i] - smaller);
            if (diff >= 0) {
                best = Math.min(best, diff);
            }
        }
        values.add(data[i]);
    }
    System.out.println(best);
}
}

C# implementation - failed test cases 11 - 15 due to timeout:

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace minimumLoss
{
class Program
{
static void Main(string[] args)
{

I don't quite follow your solution.

• Why do you sort a sorted collection? Either use OrderBy with a regular collection, or SortedSet without OrderBy.

-
Is there any difference between .OrderByDescending(p => p).Take(1).Last() and .Max()?

var smaller = data.Where(p => p < prices[i]);
if (smaller.Any())
{
    Int64 newDiff = prices[i] - smaller.Max();

Or even .Last() instead of .Max(), if collection is already sorted?

-
Is there any difference between n and prices.Length?

All in all, LINQ is a great tool, but not when you have to write a solution to an unrealistic problem that has to meet an unrealistic performance requirement. Use loops instead. The Java code you posted can be easily translated to C# without any major modifications.

If for some reason you need a LINQ solution, this should probably work:

private static Int64 MinimumLossCal(Int64[] prices)
{
    return prices
                 //calculate all the differences
                 .SelectMany((currentPrice, i) => prices.Take(i).Select(p => p - currentPrice))
                 //pick only those, that are positive (loss)
                 .Where(difference => difference > 0)
                 //pick minimum
                 .Min();
}

But, again, it will never work as fast as a regular loop.

StackExchange Code Review Q#148523, answer score: 2