1

I am trying to create a mapping, where we are given an integer n, and also a bunch of intervals that map to random numbers.

e.g. n = 55, and say we have intervals: [1:3]->-2,[4:10]->-3,[11:25]->-4,[26:44]->-5,[45:66]->-6, etc.

Is it possible/how can I create a mapping that is constant time, so that for any given n, I can find the corresponding interval, then the correct mapping to the negative number?

My thoughts are to create a dictionary, with keys as the intervals, and the values as the negative number- however would this be constant time lookup for any given n?

Patrick_Chong
  • 302
  • 1
  • 8
  • what do you know about n? what do you know about the intervals? – Eyal D Nov 14 '21 at 10:35
  • What do you mean by "the correct mapping to the negative number"? You want to take an integer and then lookup the value where the integer is in a range? – Iain Shelvington Nov 14 '21 at 10:35
  • Sorry if I wasn't the clearest, n is an integer that falls inside exactly one of the intervals – Patrick_Chong Nov 14 '21 at 10:37
  • So following the example, if n=27, I want the function to return -5. Is n=2 then I want the function to return -2 – Patrick_Chong Nov 14 '21 at 10:37
  • If `n` is restricted to a finite number of values and it's convenient to store them in memory, then a dict with each value would be constant time lookup. Or if up at 66 you have the mapping above and for n > 66 you have, say, -7. That would also work with a dict by using a default value for any missing keys. A list can achieve all that where you first check that `n < len(list_of_values)` and then fetch by index. If it's not practical to store the whole mapping, then you can use bisect thresholds, but with O(logn) complexity. – Reti43 Nov 14 '21 at 10:39
  • I know the intervals above don't quite work in coding terms either, like [1:3] is meaningless, but I think it is clear what I meant! In my code I would do [I for I in range(1,4)] – Patrick_Chong Nov 14 '21 at 10:39
  • What do you know about the NUMBER of intervals? – Eyal D Nov 14 '21 at 10:41
  • @Reti43 n can be huge 10^5, so storing each number won't be practical- sorry should have mentioned this too! – Patrick_Chong Nov 14 '21 at 10:42
  • @Eyal, the number of intervals will be say around 100 – Patrick_Chong Nov 14 '21 at 10:43
  • @user15877202 you will probably have to loop over the intervals and run a comparison to see if n contained in the interval – Iain Shelvington Nov 14 '21 at 10:44
  • Thanks Lain, that's what I thought. But if the intervals were sorted, is there a faster was to look up then? – Patrick_Chong Nov 14 '21 at 10:45
  • I don't think 10**5 is really that big of a deal. Do you have any memory restrictions? If your intervals are sorted, you can use bisect like I mentioned above. Check [here](https://stackoverflow.com/questions/66762595/efficient-way-to-sort-by-number-thresholds-in-python). – Reti43 Nov 14 '21 at 10:47
  • Even if you define your map with something like `d = {i: -i for i in range(10000)}` so that all numbers are different and you need that many objects in memory, they still don't take up more than [1 MB](https://stackoverflow.com/a/30316760/2243104). – Reti43 Nov 14 '21 at 10:50
  • And a numpy array would be even more memory efficient, assuming the list/array approach is practical. – Reti43 Nov 14 '21 at 10:52
  • Thanks Reti- this does seem to work. I am coding on CodeChef, a competitive website, so conscious about time and space! But this does work so thank you :) – Patrick_Chong Nov 14 '21 at 11:29

1 Answers1

0

A naive solution would be to create an array of size n, and for each index, initialize it with the target value. This is wasteful (for example if n is really big, and you have just one interval). Constructing the array is done in O(n) time, but accessing an array by index is O(1).

EDIT: If the number of given intervals is a constant and not a function of n, then iterating the intervals to find the right one can be done in O(1) time. In this case you don't need any dict or array.

Eyal D
  • 159
  • 1
  • 15