Challenge from Hacker Rank -

Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for the items, given her budget.

Given the price lists for the store's keyboards and USB drives, and Monica's budget, find and print the amount of money Monica will spend. If she doesn't have enough money to both a keyboard and a USB drive, print -1 instead. She will buy only the two required items.

For example - with a budget of 10, two keyboards costing 3,1 & finally three drives available costing 5,2,8, the answer should be 9 as she is only able to purchase the keyboard for 3 and a drive for 5.

I've attempted to solve this logically and with good performance in mind. I'm not sure if I should be happy with my solution. I would appreciate any feedback.

My solution (which works) or my GitHub repo -

using System;
using System.Collections.Generic;
using System.Linq;

namespace ElectronicsShop

 class Program
 
 static void Main(string[] args)
 

 Console.WriteLine(GetMoneySpent(new int[] 3, 1 , new int[] 5, 2, 8 , 10));
 Console.WriteLine(GetMoneySpent(new int[] 5, new int[] 4 , 5));
 Console.ReadLine();
 

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

 // sort the two arrays so the highest values are at the front
 keyboards = SortArrayDescending(keyboards);
 drives = SortArrayDescending(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);
 
 

 // sort the list & delete anything over budget
 combinedTotals.Sort();
 combinedTotals.Reverse();
 combinedTotals.RemoveAll(n => n > budget);

 return combinedTotals.Count == 0 ? -1 : combinedTotals[0];
 

 static int[] SortArrayDescending(int[] array)
 
 Array.Sort(array);
 Array.Reverse(array);

 return array;
 

 static int[] GetAffordableItems(int[] array, int budget)
 
 return array.Where(n => n < budget).ToArray();
 
 

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;

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.

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)

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)

 if (keyboards == null