Minimum Waiting Time with Time and Space Complexity — Competitive Programming

Question — 10 (Level — Easy)

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve another easy problem, Sorted Squared Array.

We will find the Time and Space complexity of our solution and will also guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Code Wrestling

Question

You’re given a non-empty array of positive integers representing the amount of time that specific queries take to execute. Only one query can be executed at a time, but the queries can be executed in any order.

A query’s waiting time is defined as the amount of time that it must wait before its execution starts. In other words, if a query is executed second, then its waiting time is the duration of the first query; if a query is executed third, then its waiting time is the sum of the duration of the first two queries.

Write a function that returns the minimum amount of total waiting time for all of the queries. For example, if you’re given the queries of durations [1, 4, 5], then the total waiting time if the queries were executed in the order of [5, 1, 4] would be (0) +(5) + (5 + 1) = 11. The first query of duration 5 would be executed immediately, so its waiting time would be 0, the second query of duration 1 would have to wait 5 seconds (the duration of the first query) to be executed, and the last query would have to wait for the duration of the first two queries before being executed.

Note: you’re allowed to mutate the input array.

Sample Input:

queries = [3, 2, 1, 2, 6]

Sample Output:

17

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

Here, we need to find minimum waiting time, so we need to find an approach such that all the tasks should wait at their minimum time.

So if we have a long task, then it must be executed at the end, otherwise, all other small tasks need to wait. Thus this gives an idea to sort the array first and then just add to find the minimum waiting time.

See the below code snippet for the solution:

private int MinWaitingTime(int[] queries)
{
            // Time Complexity - O(n logn)
            // Space Complexity - O(1)
            Array.Sort(queries);
            int sum = 0;
            int waitingTime = 0;
            // Waiting time of first query is always 0
            for (int i = 0; i < queries.Length - 1; i++)
            {
                waitingTime += queries[i];
                sum += waitingTime;
            }
            return sum;
}

Here the time complexity is O(n logn) because the sorting has a time complexity of O(n logn) and the for loop has a complexity of O(n), now add both so O(n + n logn) => O(n logn) and space complexity is O(1).

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.

Code Wrestling