0

I came across this question and everywhere except a couple of places, i found solution using hashmap. But a hashmap solution runs out of space when range goes higher. I found below solution which says how to use "Priority queue" to reduce space complexity to O(n).

The basic idea, is to initialize a priority queue with pairs (a, a+1) for a in the range [1, N), and then repeatedly increment the second value of the smallest (by sum of cubes) tuple until it reaches N. If at any time the smallest two elements in the queue are equal, you have a solution.

I didn't get the solution. If we are increasing the second value till specified range, then space complexity will again be O(n^2), same as hashmap. Can anyone provide the code to solve this problem using priority queue that uses O(n) space?

Prune
  • 76,765
  • 14
  • 60
  • 81
Apurva
  • 19
  • 5
  • You have a queue with N pairs. Increasing the second value means modifying one of the pairs, so you always have N pairs. No O(n^2) memory used – juvian Mar 19 '19 at 19:07
  • There are implementations [here](https://stackoverflow.com/questions/12243571/how-to-find-all-taxicab-numbers-less-than-n) – juvian Mar 19 '19 at 19:16

0 Answers0