CODEWITHSUNDEEP
c#algorithmlistmatching
Furkan Karacan
Furkan Karacan

Reputation: 192

C# - Best Way to Match 2 items from a List Without Nested Loops

My objective is : For any given flightDuration, i want to match 2 film from my filmDurations that their sums exactly finishes 30 minutes from flight.

For example :

I can do it with nested loops. But it is not effective and it is time consuming.

I want to do it more effectively. I thinked using Linq but still it is O(n^2).

What is the best effective way?

Edit: I want to clear one thing.

I want to find filmDurations[i] + filmDurations[j] in;

filmDurations[i] + filmDurations[j] == fligtDuration - 30

And say i have very big amont of film durations.

Upvotes: 0

Views: 200

Answers (2)

MrSmith42
MrSmith42

Reputation: 10181

You could sort all durations (remove duplicates) (O(n log n)) and than iterate through them (until the length flight-duration -30). Search for the corresponding length of the second film (O(log n)).

This way you get all duration-pairs in O(n log n).

You can also use a HashMap (duration -> Films) to find matching pairs.

This way you can avoid sorting and binary search. Iterate through all durations and look up in the map if there are entries with duration = (flight-duration -30).

Filling the map needs O(n) lookup O(1) and you need to iterate all durations.

-> Over all complexity O(n) but you loose the possibility to find 'nearly matching pairs which would be easy to implement using the sorted list approach described above)

Upvotes: 2

Aleks Andreev
Aleks Andreev

Reputation: 7054

As Leisen Chang said you can put all items into dictionary. After doing that rewrite your equation

filmDurations[i] + filmDurations[j] == fligtDuration - 30

as

filmDurations[i] == (fligtDuration - 30 - filmDurations[j])

Now for each item in filmDurations search for (fligtDuration - 30 - filmDurations[j]) in dictionary. And if such item found you have a solution.

Next code implement this concept

public class IndicesSearch
{
    private readonly List<int> filmDurations;
    private readonly Dictionary<int, int> valuesAndIndices;

    public IndicesSearch(List<int> filmDurations)
    {
        this.filmDurations = filmDurations;

        // preprocessing O(n)
        valuesAndIndices = filmDurations
            .Select((v, i) => new {value = v, index = i})
            .ToDictionary(k => k.value, v => v.index);
    }

    public (int, int) FindIndices(
        int flightDuration,
        int diff = 30)
    {
        // search, also O(n)
        for (var i = 0; i < filmDurations.Count; ++i)
        {
            var filmDuration = filmDurations[i];
            var toFind = flightDuration - filmDuration  - diff;
            if (valuesAndIndices.TryGetValue(toFind, out var j))
                return (i, j);
        }

        // no solution found
        return (-1, -1); // or throw exception
    }
}

Upvotes: 1

Related Questions