early pruning

This is very nice:

 // delete any that are over our budget

Doing it before sorting can slightly speed the sorting operation.
I say slightly because "items over budget" is determined by the input,
and it will be some fraction f of an input item category,
so the savings is O(f * n * log n).

early discard

This is a bigger deal.

 // sort the list & delete anything over budget

For k keyboards and d drives, the sort does O(k * d * log k * d) work.
Discarding within this loop would be an even bigger win.

consistent idiom

It was a little odd that you used

 combinedTotals.RemoveAll(n => n > budget);

and

 array.Where(n => n < budget).ToArray();

to accomplish the same thing.
There's no speed difference but consider phrasing the same thing in the same way.

reversing

If you pass into Sort something that implements the IComparer interface,
you can change the comparison order and thus skip the Reverse step entirely.

arithmetic

Arbitrarily choose one of the categories as the driving category, perhaps keyboard.
Sort the drive prices, while leaving the keyboards in arbitrary order.
Note the min drive price, and use that along with budget for immediately pruning infeasible keyboards.

Loop over all surviving keyboards.
Target price is budget - kb_price.
Do binary search over drives for the target,
finding largest feasible drive,
and use that to update "best combo so far".
No need to sort them, you need only retain the "best" one.

General Guidelines

• You have coded everything in a single class Program. Take advantage of the fact C# is an object oriented language. Create at least one custom class that defines this problem.


• Your current implementation is very strict and specific to 2 types of items. What if Monica needs to buy from n item types? It is up to you to decide the scope of your implementation, so what you have done is not wrong, but it is something to consider when building reusable code blocks. We can argue reusability of this exercise though.


• When providing a method for consumers to use, make sure to include a handful of unit tests. This is an excellent way to get to know the outcome given any input. In this case, you are providing us GetMoneySpent, but we have to write our own unit tests to verify correctness of this method.

Review

• You are using Array for a problem where IEnumerable could have also been used. Prefer the latter because you don't want to depend on fixed sized collections. You are converting ToArray(), this overhead should not be required when working with IEnumerable.

The good thing first:

You divide and conquer the problem by creating some reasonable (and well named) methods. You could have gone all in by making methods for combining and final selection as well:

 ...
 var combinedTotals = Combine(affordableKeyboards, affordableDrives);
 return SelectMaxBuy(combinedTotals, budget);
}

But as shown below, dividing the code into such small methods can sometimes obscure more useful approaches.

It must be a mind slip that you find the affordable keyboards and drives, but you forget about them and iterate over the full arrays of keyboards and drives:

 // delete any that are over our budget
 var affordableKeyboards = GetAffordableItems(keyboards, budget);
 var affordableDrives = GetAffordableItems(drives, budget);

 // make a list to contain the combined totals
 var combinedTotals = new List<int>();

 foreach (var keyboard in keyboards)
 
 foreach (var drive in drives)
 
 combinedTotals.Add(keyboard + drive);
 
 

I suppose that the loops should be:

 foreach (var keyboard in affordableKeyboards)
 
 foreach (var drive in affordableDrives)
 
 combinedTotals.Add(keyboard + drive);
 
 

Some optimizations:

 return array.Where(n => n < budget).ToArray();

Where has to iterate through the entire array, even if it is sorted.
A better approach would have been to sort ascending first, then take untill n > budget, and then reverse:

array.OrderBy(n => n).TakeWhile(n => n <= budget).Reverse();

Making the almost same considerations with the combined totals:

 int result = combinedTotals.OrderByDescending(n => n).FirstOrDefault(n => n <= budget);

Your entire method could be refined to this:

static int GetMoneySpent(int[] keyboards, int[] drives, int budget)
 budget <= 0)
 return -1;

 keyboards = keyboards.OrderBy(n => n).TakeWhile(n => n <= budget).Reverse().ToArray();
 drives = drives.OrderBy(n => n).TakeWhile(n => n <= budget).Reverse().ToArray();

 // make a list to contain the combined totals
 var combinedTotals = new List<int>();

 foreach (var keyboard in keyboards)
 
 foreach (var drive in drives)
 
 combinedTotals.Add(keyboard + drive);
 
 

 int result = combinedTotals.OrderByDescending(n => n).FirstOrDefault(n => n <= budget);
 return result == 0 ? -1 : result;

Just for the sport I made the below solution, that sorts the data sets in ascending order and iterate backwards to avoid reversing the data:

int GetMoneySpent(int[] keyboards, int[] drives, int budget)
 budget <= 0)
 return -1;

 int result = -1; 

 Array.Sort(keyboards);
 Array.Sort(drives);

 int istart = keyboards.Length - 1;
 while (istart >= 0 && keyboards[istart] > budget) istart--;
 int jstart = drives.Length - 1;
 while (jstart >= 0 && drives[jstart] > budget) jstart--;

 for (int i = istart; i >= 0; i--)
 
 int keyboard = keyboards[i];

 for (int j = jstart; j >= 0; j--)
 
 int drive = drives[j];

 int price = keyboard + drive;
 if (price < result)
 break;

 if (price > result && price <= budget)
 
 result = price;
 
 
 

 return result;

3 good answers already, but there's more!

I don't like that you modify the array you are given. This sort of thing would need to be documented, and generally creates confusion for all. You don't need arrays as inputs, so you could take IEnumerables instead without any added cost, which makes the code easier to reuse and communicates to the consumer that you aren't modifying anything. I'd consider making the parameter names a little more explicit:

public static int GetMoneySpent(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)

Your SortArrayDescending modifies the array given, and then proceeds to return it: this is how to really annoying people, because they will assume that because the method returns something that it won't be modifying the input.

You've clearly thought about edge cases, which is good. You might consider some parameter validation (e.g. checking the budget makes sense, the arrays should not be null):

if (budget < 0)
 throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
if (keyboardPrices == null)
 throw new ArgumentNullException(nameof(keyboardPrices));
if (drivePrices == null)
 throw new ArgumentNullException(nameof(drivePrices));

At the moment the program would print -1, which is sort of makes sense, but could easily be the first clue that something has gone wrong higher-up.

As implied by J_H, you should discard before the sort. The following also clones the arrays immediately so we don't modify them:

// filter to within-budget items, sort the two arrays (ascending)
keyboards = keyboards.Where(k => k < budget).ToArray();
Array.Sort(keyboards);

drives = drives.Where(d => d < budget).ToArray();
Array.Sort(drives);

J_H has already described how you can get the optimal time complexity, but you can perform the loops at the end very simply, without needing nesting or binary search or any of that.

You also don't need to record a list of all the candidates, just keep track of the current best, as Henrik Hansen has already demonstrated:

// maximum within budget price
int max = -1;

If we start by looking at the most expensive keyboard and cheapest drive and simultaneously iterate through both, we can do this bit in linear time.

int ki = keyboards.Length - 1; // drive index
int di = 0; // drive index

while (ki >= 0 && di < drives.Length)

 int candidate = keyboards[ki] + drives[di];
 if (candidate <= budget)
 
 max = Math.Max(candidate, max);
 di++;
 
 else
 
 ki--;
 

Suppose we are looking at keyboard ki and drive di: candidate is the sum of their costs. If this candidate cost is no more than the budget, then it is a candidate for the max. We also know that we can check for a more pairing by looking at the next most expensive drive, di + 1. If instead the candidate was out of the budget, we know we can find a cheaper candidate by looking at the next cheapest keyboard ki - 1.

Basically, we look at each keyboard in turn, and cycle through the drives until we find the most expensive one we can get away with. When we find the first drive that is too expensive, we move onto the next keyboard. We know that we don't want any drive cheaper than the last one we looked at, because that could only produce a cheaper pair, so we can continue our search starting from the same drive.

At the end, we just return max: if we didn't find any candidates below budget, it will still be -1:

return max;

Concerning dfhwze's comment about buying more than 2 items: this process is essentially searching the Pareto front, which is done trivially and efficiently for 2 items, but becomes nightmarish for any more, so I would certainly forgive you for sticking to 2 lists ;)

The above code all in one, with added inline documentation to make the purpose explicit (useful for the consumer, so that they know exactly what it is meant to do, and useful for the maintainer, so that they also know what it is meant to do):

/// <summary>
/// Returns the maximum price of any pair of a keyboard and drive that is no more than the given budget.
/// Returns -1 if no pair is within budget.
/// </summary>
/// <param name="keyboardPrices">A list of prices of keyboards.</param>
/// <param name="drivepricess">A list of prices of drives.</param>
/// <param name="budget">The maximum budget. Must be non-negative</param>
public static int GetMoneySpent2(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)

 if (budget < 0)
 throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
 if (keyboardPrices == null)
 throw new ArgumentNullException(nameof(keyboardPrices));
 if (drivePrices == null)
 throw new ArgumentNullException(nameof(drivePrices));

 if (budget == 0)
 return -1;

 // filter to within-budget items, sort the two arrays (ascending)
 var keyboards = keyboardPrices.Where(k => k < budget).ToArray();
 Array.Sort(keyboards);

 var drives = drivePrices.Where(d => d < budget).ToArray();
 Array.Sort(drives);

 // maximum within budget price
 int max = -1;

 int ki = keyboards.Length - 1; // keyboard index
 int di = 0; // drive index

 while (ki >= 0 && di < drives.Length)
 
 int candidate = keyboards[ki] + drives[di];
 if (candidate <= budget)
 
 max = Math.Max(candidate, max);
 di++;
 
 else
 
 ki--;
 
 

 return max;

J_H's solution (using a BinarySearch) could well be better in practise, because you only need to sort (and binary search) the shortest input: you can scan the other however you like. Implementation of that, since I too enjoy the sport:

/// <summary>
/// Returns the maximum price of any pair of a keyboard and drive that is no more than the given budget.
/// Returns -1 if no pair is within budget.
/// </summary>
/// <param name="keyboardPrices">A list of prices of keyboards.</param>
/// <param name="drivepricess">A list of prices of drives.</param>
/// <param name="budget">The maximum budget. Must be non-negative</param>
public static int GetMoneySpent3(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)

 if (budget < 0)
 throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
 if (keyboardPrices == null)
 throw new ArgumentNullException(nameof(keyboardPrices));
 if (drivePrices == null)
 throw new ArgumentNullException(nameof(drivePrices));

 if (budget == 0)
 return -1;

 // filter to within-budget items
 var keyboards = keyboardPrices.Where(k => k < budget).ToArray();
 var drives = drivePrices.Where(d => d < budget).ToArray();

 // determine which list is shorter
 IReadOnlyList<int> longList;
 int[] shortList;

 if (keyboards.Length < drives.Length)
 
 shortList = keyboards;
 longList = drives;
 
 else
 
 shortList = drives;
 longList = keyboards;
 

 // special case of empty short-list
 if (shortList.Length == 0)
 return -1;

 // sort shortList, to facilitate binary search
 Array.Sort(shortList);

 // maximum within budget price
 int max = -1;

 foreach (var k in longList)
 
 // filter faster
 if (k + shortList[0] > budget)
 continue;

 // find most expensive drive no more than budget - k
 int i = Array.BinarySearch(shortList, budget - k);
 i = i >= 0
 ? i // found
 : ~i - 1; // not found, consider next smallest

 // if such a drive exists, consider it a candidate
 if (i >= 0)
 
 int candidate = k + shortList[i];
 max = Math.Max(max, candidate);
 
 

 return max;

As others have pointed out, the code should be object oriented. It’s OK to start with procedural code as you have, but if you do, you should get in the habit of writing a quick test in your main entry point. Once you’ve written the first test, it can help you start seeing objects more clearly (and drive you to further unit tests.)

For example: an ElectronicsShop would only have a catalog of items, but it has nothing to do with your spending habits. In your case, it would serve only as a data store for items.

I’d really expect to see a Shopper class. The shopper would have both Money and a BuyingStrategy. The money could be a simple amount, but the strategy would be what you’re really working on. Finally, the strategy would expose a method Shop(Store, Items[], Budget).

Inside Shop(), you’d retrieve the items from the store that meet your criteria: they’d be only keyboards and drives, and they’d be within budget. The shopper would add only eligible items to their comparison lists. Then comes time to evaluate them , so you’d add an Evaluate(Budget, ItemLists[]) method that would be called from within Shop(). Inside Evaluate() you can order results by price. But what happens when you get multiple answers that meet the same amount? A budget of 10 would be met by any of 9,1, 1,9, 6,4, or even 5,5! Which is more important, expensive drives or expensive keyboards? (In the real world, you’d go back to your product owner at this point and ask them about their priorities: “do you prefer the most expensive drive, the most expensive keyboard, or should it try to split the difference somehow?”) This might lead you to conclude that Evaluating is really the strategy, not Buying.

I could go on, but I think I’ve made my point. Notice how once I’ve defined just a few relevant objects that the process I’m describing begins to mirror the real world act of shopping? And once you start down this path of viewing coding problems as models of real objects interacting in the real world, you’ll see the ease of defining objects and writing tests for them, and using them to recognize shortcomings in the specs and completing your specifications. (Pro tip: specifications are always incomplete.)

Performance isn’t always the best starting point. Object oriented programming is less about finding the most mathematically efficient solution; it’s about building understandable components and proving that they meet your clients’ needs. Getting to the right answer is much more important than quickly getting to some answer that you can’t prove is correct. If performance is an issue after you’ve solved the problem, then start optimizing; but don’t start there.