when work with grid or graph that could potentially grow to massive size, is common use an array to store it, but there is an elegant solution to run this in linear time and space.
there is a simple trick of how to do that. let assume some requirements first:
-
imagine you have a potentially infinite structure that should store all nodes, edges and neighbors in the world.
-
you should traverse it with with linear time, big O(n). It means you process each element at least once.
-
considering the potentially infinite X-axis grid, you should avoid create a dynamic array all time you need have to access the N position.
example: you have a 3x3 grid, but you want to store a new information at the (1000, 1000) position. What you wanna do? Will you increase the size of array?
DO NOT CREATE AN ARRAY FOR THAT, USE HASHSET.
just store the position X, Y as key and when you need it, just consume it in constant time. YAY!
sorry for scream, but this very useful trick, to avoid increase the space of algorithm.