Time and Space complexity of the max disk space

user_13545435 0
Viewed 21323
from collections import deque
def findMax(hardDiskSpace, k):
    n = len(hardDiskSpace)
    if n * k == 0:
        return []
    if k > n:
        return []

    deq = deque()
    res = []
    i = 0
    while i < n:
        if deq and deq[0] == i - k:
            deq.popleft()
        while deq and hardDiskSpace[deq[-1]] > hardDiskSpace[i]:
            deq.pop()
        deq.append(i)

        if i >= k - 1:
            res.append(hardDiskSpace[deq[0]])
        i += 1
    print(res)
    print(max(res))


if __name__ == '__main__':
    hdd = [62, 64, 77, 75, 71, 60, 79, 75]
    k = 4
    findMax(hdd, k)

A Company performing an analysis on the computers at one of its offices. The computers are spaced along a single row. The analysis is performed in the following way: Choose a contiguous segment of a certain number of computers, starting from the beginning of the row. Analyze the available hard disk space on each of the computers. Determine the minimum available disk space within this segment. After performing these steps for the first segment, it is then repeated for the next segment, continuing this procedure until the end of the row (i.e. if the segment size is 4, computers 1 to 4 would be analyzed, then 2 to 5, etc.) Given this analysis procedure, write an algorithm to find the maximum available disk space among all the minima that are found during the analysis.
Input
The input consists of three arguments:
numComputer: an integer representing the number of computers
hardDiskSpace: a list of integers representing the hard disk space of the computers
segmentLength: an integer representing the length of the contiguous segment of computers to be considered in each iteration

Output
Return an integer representing the maximum available disk space among all the minima that are found during the analysis.
Examples
Input:
numComputer = 3
hardDiskSpace = [62, 64, 77, 75, 71, 60, 79, 75]
segmentLength = 4
Output: 64

Could anyone please explain me the time and space complexity of the above problem.

space-complexity time-complexity optimization python
2 Answers

The listed solution is linear in both time and space (O(N)). It also can't be better than that since you need to at least read the input.

I'll start with the space complexity since it's easier.

  • You are given the List input of size N.
  • The only additional memory you will be using is the deque that holds the current minimum and its possible successors. if deq and deq[0] == i - k: deq.popleft() part guarantees that this queue will never be larger than the segmentLength.
  • There is no additional space used apart from few one-off variables.

Hence the space complexity is O(N).

The time complexity is also O(N). Let us look at why:

  • The outlying while i < n: iterates once over the whole computer list. The index i is increased in each step so we are in no risk of lingering longer. What about the insides of the outer cycle though?
  • Nothing wrong there either: Every element(hd space) that we go over gets appended into the queue.
  • Every element we go over is removed from the queue at some point(Apart from those that are closer to the end of the array than the segment size. This doesn't change the result in any way). So for every one of the elements we perform one push and either one pop or one popleft. Both pop, push and popleft are done in constant time - courtesy of the deque collection, so we are still linear.
  • The only potentionally suspicious part is the inner while deq and hardDiskSpace[deq[-1]] > hardDiskSpace[i]:. However since it only performs pop when the queue is nonempty and we never insert any of the elements more than once it is fine.

The part we should've probably started with is the corectness. However since you didn't ask about it, I'm leaving it last:

The key to the corectness is the deque structure we use to find the minima. The final max(result) is just a finishing touch since maximum can be find in a linear time simply by going over the result array.

During every iteration we:

  • Check if the leftmost index in the deque isn't obsolete. (not a part of the current segment anymore)
  • Check if the rightmost-indexed element is smaller then the currently-indexed element. If yes, we remove it. Repeat until it either isn't true anymore or the deque is empty. This guarantees that the leftmost element stays minimal - if it wasn't we would've removed it in this step.
  • We insert the new addition into the queue. (So the queue holds a non-ascending sequence of the minimum-candidates)
  • If we already loaded at least one whole segment, we add the leftmost-indexed element into the result set.

Not sure if this could qualify as a proof, however it is enough reasoning for me to be certain that it works. Fun fact - I had to rewrite this part since I assumed a slightly different approach and got rather confused when that wasn't the case in the middle of going through the explanation.

user_64446310 
vector<int> minSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        int res=0;
        for (int i = 0; i < nums.size(); i++) {
            while (!dq.empty() and dq.front() <= i - k) dq.pop_front();
            while (!dq.empty() and nums[dq.back()] >=nums[i]) dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1) {
                 int x = nums[dq.front()];
                ans.push_back(x);
                res = max(res,x);
            }
        }
        return res;
    }
user_189679790
Related