I will iterate over a list of integers, nums, multiple times, and each time, when an integer has been 'used' for something (doesn't matter what), I want to mark the index as used. So that in future iterations, I do not use this integer again.
Two questions:
My idea is to simply create a separate list marker = [1]*len(nums) ; and each time I use a number in nums, I will subtract 1 from the corresponding index in marker as a way to keep track of the numbers in nums I have used.
My first question is, is there a well known efficient way to do this? As I believe this would make the SPACE COMPLEXITY O(n)
My other idea is to replace each entry in nums, like this. nums = [1,2,3,4] -> nums = [(1,1),(2,1),(3,1),(4,1)]. And each time I use an integer in nums, I would subtract 1 from the second index in each pair as a way of marking that it has been used. My question is, am I right in understanding that this would optimise the SPACE COMPLEXITY relative to solution 1. above? And the SPACE COMPLEXITY here would be O(1)?
For reference, I am solving the following question: https://leetcode.com/contest/weekly-contest-256/problems/minimum-number-of-work-sessions-to-finish-the-tasks/
Where each entry in tasks needs to be used once.
I don't think there is a way to do it in O(1) space. Although, I believe that using a boolean value instead of an integer value or using the concept of sets would be a better solution.
No, the space complexity is still O(n). Think about it like this. Let us assume n is the size of the list. In the first method that you mentioned, we are storing n 'stuff' separately. So, the space complexity is O(n). In the second method also, we are storing n 'stuff' separately. It's just that those n 'stuff' are being stored as part of the same array. So, the space complexity still remains the same which is O(n).