In the world of algorithm design and implementation, efficiency is key. While time complexity often takes center stage, space complexity is equally crucial, especially in resource-constrained environments. This comprehensive guide will explore 40 powerful techniques for space optimization in algorithms, helping you write more efficient and scalable code.<\/p>\n
1. In-place Algorithms<\/h2>\n
In-place algorithms modify the input data structure directly without using additional space. This technique is particularly useful for sorting and array manipulation problems.<\/p>\n
Example: In-place Reverse Array<\/h3>\ndef reverse_array(arr):\n left, right = 0, len(arr) - 1\n while left < right:\n arr[left], arr[right] = arr[right], arr[left]\n left += 1\n right -= 1\n return arr\n\n# Usage\narr = [1, 2, 3, 4, 5]\nreversed_arr = reverse_array(arr)\nprint(reversed_arr) # Output: [5, 4, 3, 2, 1]<\/code><\/pre>\n2. Bit Manipulation<\/h2>\n
Using bit manipulation techniques can significantly reduce space usage, especially when dealing with boolean flags or small integer values.<\/p>\n
Example: Checking if a number is even using bitwise AND<\/h3>\ndef is_even(num):\n return (num & 1) == 0\n\n# Usage\nprint(is_even(4)) # Output: True\nprint(is_even(7)) # Output: False<\/code><\/pre>\n3. String Interning<\/h2>\n
String interning is a technique where only one copy of each distinct string is stored in memory. This can save space when dealing with many duplicate strings.<\/p>\n
Example: String interning in Python<\/h3>\na = 'hello'\nb = 'hello'\nprint(a is b) # Output: True (both variables reference the same string object)<\/code><\/pre>\n4. Use of Generators<\/h2>\n
Generators allow you to iterate over a sequence of values without storing the entire sequence in memory.<\/p>\n
Example: Using a generator for Fibonacci sequence<\/h3>\ndef fibonacci():\n a, b = 0, 1\n while True:\n yield a\n a, b = b, a + b\n\n# Usage\nfib = fibonacci()\nfor _ in range(10):\n print(next(fib), end=' ')\n# Output: 0 1 1 2 3 5 8 13 21 34<\/code><\/pre>\n5. Memoization<\/h2>\n
Memoization involves caching the results of expensive function calls to avoid redundant computations. While it trades space for time, it can be more space-efficient than naive recursive solutions.<\/p>\n
Example: Memoized Fibonacci<\/h3>\ndef memoized_fib(n, memo={}):\n if n in memo:\n return memo[n]\n if n <= 1:\n return n\n memo[n] = memoized_fib(n-1, memo) + memoized_fib(n-2, memo)\n return memo[n]\n\n# Usage\nprint(memoized_fib(100)) # Calculates 100th Fibonacci number efficiently<\/code><\/pre>\n6. Use of Constant Space<\/h2>\n
Some algorithms can be optimized to use only a constant amount of extra space, regardless of input size.<\/p>\n
Example: Finding the majority element in an array<\/h3>\ndef majority_element(nums):\n candidate = None\n count = 0\n for num in nums:\n if count == 0:\n candidate = num\n count += (1 if num == candidate else -1)\n return candidate\n\n# Usage\narr = [2, 2, 1, 1, 1, 2, 2]\nprint(majority_element(arr)) # Output: 2<\/code><\/pre>\n7. Space-Efficient Data Structures<\/h2>\n
Choosing the right data structure can significantly impact space usage. For example, using a Trie for storing strings with common prefixes can be more space-efficient than storing each string separately.<\/p>\n
Example: Implementing a Trie<\/h3>\nclass TrieNode:\n def __init__(self):\n self.children = {}\n self.is_end = False\n\nclass Trie:\n def __init__(self):\n self.root = TrieNode()\n\n def insert(self, word):\n node = self.root\n for char in word:\n if char not in node.children:\n node.children[char] = TrieNode()\n node = node.children[char]\n node.is_end = True\n\n def search(self, word):\n node = self.root\n for char in word:\n if char not in node.children:\n return False\n node = node.children[char]\n return node.is_end\n\n# Usage\ntrie = Trie()\ntrie.insert(\"apple\")\nprint(trie.search(\"apple\")) # Output: True\nprint(trie.search(\"app\")) # Output: False<\/code><\/pre>\n8. Sliding Window Technique<\/h2>\n
The sliding window technique can be used to process subarrays or substrings efficiently without using extra space.<\/p>\n
Example: Finding the maximum sum subarray of size k<\/h3>\ndef max_sum_subarray(arr, k):\n n = len(arr)\n if n < k:\n return None\n \n window_sum = sum(arr[:k])\n max_sum = window_sum\n \n for i in range(n - k):\n window_sum = window_sum - arr[i] + arr[i + k]\n max_sum = max(max_sum, window_sum)\n \n return max_sum\n\n# Usage\narr = [1, 4, 2, 10, 23, 3, 1, 0, 20]\nk = 4\nprint(max_sum_subarray(arr, k)) # Output: 39<\/code><\/pre>\n9. Two Pointer Technique<\/h2>\n
The two pointer technique can be used to solve various problems with minimal space usage, especially for array and linked list problems.<\/p>\n
Example: Removing duplicates from a sorted array in-place<\/h3>\ndef remove_duplicates(nums):\n if not nums:\n return 0\n \n i = 0\n for j in range(1, len(nums)):\n if nums[j] != nums[i]:\n i += 1\n nums[i] = nums[j]\n \n return i + 1\n\n# Usage\nnums = [1, 1, 2, 2, 3, 4, 4, 5]\nnew_length = remove_duplicates(nums)\nprint(nums[:new_length]) # Output: [1, 2, 3, 4, 5]<\/code><\/pre>\n10. Recursive Space Optimization<\/h2>\n
Tail recursion optimization can help reduce the space complexity of recursive algorithms by reusing stack frames.<\/p>\n
Example: Tail-recursive factorial function<\/h3>\ndef factorial(n, acc=1):\n if n == 0:\n return acc\n return factorial(n - 1, n * acc)\n\n# Usage\nprint(factorial(5)) # Output: 120<\/code><\/pre>\n11. Use of Static Variables<\/h2>\n
In some languages, using static variables can help reduce memory usage by sharing a single copy of the variable across all instances of a class.<\/p>\n
Example: Using static variables in Java<\/h3>\npublic class Counter {\n private static int count = 0;\n\n public void increment() {\n count++;\n }\n\n public int getCount() {\n return count;\n }\n}\n\n\/\/ Usage\nCounter c1 = new Counter();\nCounter c2 = new Counter();\nc1.increment();\nc2.increment();\nSystem.out.println(c1.getCount()); \/\/ Output: 2\nSystem.out.println(c2.getCount()); \/\/ Output: 2<\/code><\/pre>\n12. Space-Time Tradeoffs<\/h2>\n
Sometimes, trading a little space for significant time improvements can be beneficial. For example, using a hash table for O(1) lookup time at the cost of O(n) space.<\/p>\n
Example: Two Sum problem using a hash table<\/h3>\ndef two_sum(nums, target):\n num_dict = {}\n for i, num in enumerate(nums):\n complement = target - num\n if complement in num_dict:\n return [num_dict[complement], i]\n num_dict[num] = i\n return []\n\n# Usage\nnums = [2, 7, 11, 15]\ntarget = 9\nprint(two_sum(nums, target)) # Output: [0, 1]<\/code><\/pre>\n13. Bitsets<\/h2>\n
Bitsets can be used to represent sets of small non-negative integers very space-efficiently.<\/p>\n
Example: Implementing a simple bitset in Python<\/h3>\nclass Bitset:\n def __init__(self, size):\n self.bits = 0\n self.size = size\n\n def set(self, pos):\n self.bits |= (1 << pos)\n\n def clear(self, pos):\n self.bits &= ~(1 << pos)\n\n def test(self, pos):\n return bool(self.bits & (1 << pos))\n\n# Usage\nbs = Bitset(8)\nbs.set(1)\nbs.set(4)\nprint(bs.test(1)) # Output: True\nprint(bs.test(2)) # Output: False<\/code><\/pre>\n14. Sparse Matrix Representation<\/h2>\n
For matrices with many zero elements, using a sparse matrix representation can save significant space.<\/p>\n
Example: Implementing a simple sparse matrix<\/h3>\nclass SparseMatrix:\n def __init__(self, rows, cols):\n self.rows = rows\n self.cols = cols\n self.elements = {}\n\n def set(self, row, col, value):\n if value != 0:\n self.elements[(row, col)] = value\n elif (row, col) in self.elements:\n del self.elements[(row, col)]\n\n def get(self, row, col):\n return self.elements.get((row, col), 0)\n\n# Usage\nsm = SparseMatrix(1000, 1000)\nsm.set(5, 10, 3.14)\nprint(sm.get(5, 10)) # Output: 3.14\nprint(sm.get(0, 0)) # Output: 0<\/code><\/pre>\n15. Compression Techniques<\/h2>\n
Data compression can be used to reduce the space required to store or transmit data.<\/p>\n
Example: Simple run-length encoding<\/h3>\ndef run_length_encode(s):\n if not s:\n return \"\"\n result = []\n count = 1\n for i in range(1, len(s)):\n if s[i] == s[i-1]:\n count += 1\n else:\n result.append(f\"{count}{s[i-1]}\")\n count = 1\n result.append(f\"{count}{s[-1]}\")\n return ''.join(result)\n\n# Usage\nprint(run_length_encode(\"AABBBCCCC\")) # Output: 2A3B4C<\/code><\/pre>\n16. Memory Pooling<\/h2>\n
Memory pooling involves pre-allocating a large chunk of memory and managing it manually to avoid frequent allocations and deallocations.<\/p>\n
Example: Simple object pool in Python<\/h3>\nclass ObjectPool:\n def __init__(self, create_func, max_size):\n self.create_func = create_func\n self.max_size = max_size\n self.pool = []\n\n def acquire(self):\n if self.pool:\n return self.pool.pop()\n return self.create_func()\n\n def release(self, obj):\n if len(self.pool) < self.max_size:\n self.pool.append(obj)\n\n# Usage\ndef create_expensive_object():\n return [0] * 1000000 # Large list\n\npool = ObjectPool(create_expensive_object, 5)\nobj1 = pool.acquire()\nobj2 = pool.acquire()\npool.release(obj1)\nobj3 = pool.acquire() # This will reuse obj1<\/code><\/pre>\n17. Lazy Evaluation<\/h2>\n
Lazy evaluation defers the computation of values until they are actually needed, potentially saving space.<\/p>\n
Example: Lazy evaluation using Python’s property decorator<\/h3>\nclass LazyComputation:\n def __init__(self):\n self._expensive_result = None\n\n @property\n def expensive_result(self):\n if self._expensive_result is None:\n print(\"Computing expensive result...\")\n self._expensive_result = sum(range(1000000))\n return self._expensive_result\n\n# Usage\nlc = LazyComputation()\nprint(lc.expensive_result) # Computes and prints result\nprint(lc.expensive_result) # Uses cached result<\/code><\/pre>\n18. Space-Efficient Sorting Algorithms<\/h2>\n
Some sorting algorithms, like Heapsort, can sort in-place with O(1) extra space.<\/p>\n
Example: In-place Heapsort<\/h3>\ndef heapify(arr, n, i):\n largest = i\n left = 2 * i + 1\n right = 2 * i + 2\n\n if left < n and arr[largest] < arr[left]:\n largest = left\n\n if right < n and arr[largest] < arr[right]:\n largest = right\n\n if largest != i:\n arr[i], arr[largest] = arr[largest], arr[i]\n heapify(arr, n, largest)\n\ndef heapsort(arr):\n n = len(arr)\n\n for i in range(n \/\/ 2 - 1, -1, -1):\n heapify(arr, n, i)\n\n for i in range(n - 1, 0, -1):\n arr[0], arr[i] = arr[i], arr[0]\n heapify(arr, i, 0)\n\n# Usage\narr = [12, 11, 13, 5, 6, 7]\nheapsort(arr)\nprint(arr) # Output: [5, 6, 7, 11, 12, 13]<\/code><\/pre>\n19. Circular Buffers<\/h2>\n
Circular buffers can be used to implement queues with fixed memory usage.<\/p>\n
Example: Implementing a circular buffer<\/h3>\nclass CircularBuffer:\n def __init__(self, size):\n self.buffer = [None] * size\n self.head = 0\n self.tail = 0\n self.size = size\n self.count = 0\n\n def enqueue(self, item):\n if self.count == self.size:\n raise Exception(\"Buffer is full\")\n self.buffer[self.tail] = item\n self.tail = (self.tail + 1) % self.size\n self.count += 1\n\n def dequeue(self):\n if self.count == 0:\n raise Exception(\"Buffer is empty\")\n item = self.buffer[self.head]\n self.head = (self.head + 1) % self.size\n self.count -= 1\n return item\n\n# Usage\ncb = CircularBuffer(3)\ncb.enqueue(1)\ncb.enqueue(2)\ncb.enqueue(3)\nprint(cb.dequeue()) # Output: 1\ncb.enqueue(4)\nprint(cb.dequeue()) # Output: 2<\/code><\/pre>\n20. Bloom Filters<\/h2>\n
Bloom filters provide a space-efficient probabilistic data structure for set membership queries.<\/p>\n
Example: Simple Bloom filter implementation<\/h3>\nimport mmh3\n\nclass BloomFilter:\n def __init__(self, size, hash_count):\n self.size = size\n self.hash_count = hash_count\n self.bit_array = [0] * size\n\n def add(self, item):\n for seed in range(self.hash_count):\n result = mmh3.hash(item, seed) % self.size\n self.bit_array[result] = 1\n\n def check(self, item):\n for seed in range(self.hash_count):\n result = mmh3.hash(item, seed) % self.size\n if self.bit_array[result] == 0:\n return False\n return True\n\n# Usage\nbf = BloomFilter(20, 3)\nbf.add(\"apple\")\nbf.add(\"banana\")\nprint(bf.check(\"apple\")) # Output: True\nprint(bf.check(\"orange\")) # Output: False (probably)<\/code><\/pre>\n21. Prefix Sum Array<\/h2>\n
Prefix sum arrays can be used to efficiently compute range sums with O(1) space complexity after preprocessing.<\/p>\n
Example: Range sum queries using prefix sum<\/h3>\ndef build_prefix_sum(arr):\n prefix_sum = [0] * (len(arr) + 1)\n for i in range(1, len(prefix_sum)):\n prefix_sum[i] = prefix_sum[i-1] + arr[i-1]\n return prefix_sum\n\ndef range_sum(prefix_sum, left, right):\n return prefix_sum[right + 1] - prefix_sum[left]\n\n# Usage\narr = [1, 2, 3, 4, 5]\nprefix_sum = build_prefix_sum(arr)\nprint(range_sum(prefix_sum, 1, 3)) # Sum of arr[1:4], Output: 9<\/code><\/pre>\n22. Segment Trees<\/h2>\n
Segment trees provide efficient range queries and updates with O(n) space complexity.<\/p>\n
Example: Segment tree for range minimum queries<\/h3>\nclass SegmentTree:\n def __init__(self, arr):\n self.n = len(arr)\n self.tree = [0] * (4 * self.n)\n self.build(arr, 0, 0, self.n - 1)\n\n def build(self, arr, node, start, end):\n if start == end:\n self.tree[node] = arr[start]\n else:\n mid = (start + end) \/\/ 2\n self.build(arr, 2*node+1, start, mid)\n self.build(arr, 2*node+2, mid+1, end)\n self.tree[node] = min(self.tree[2*node+1], self.tree[2*node+2])\n\n def query(self, node, start, end, l, r):\n if r < start or end < l:\n return float('inf')\n if l <= start and end <= r:\n return self.tree[node]\n mid = (start + end) \/\/ 2\n left = self.query(2*node+1, start, mid, l, r)\n right = self.query(2*node+2, mid+1, end, l, r)\n return min(left, right)\n\n def range_minimum(self, l, r):\n return self.query(0, 0, self.n-1, l, r)\n\n# Usage\narr = [1, 3, 2, 7, 9, 11]\nst = SegmentTree(arr)\nprint(st.range_minimum(1, 4)) # Output: 2<\/code><\/pre>\n23. Fenwick Trees (Binary Indexed Trees)<\/h2>\n
Fenwick trees provide efficient range sum queries and updates with O(n) space complexity.<\/p>\n
Example: Fenwick tree for range sum queries<\/h3>\nclass FenwickTree:\n def __init__(self, n):\n self.size = n\n self.tree = [0] * (n + 1)\n\n def update(self, i, delta):\n while i <= self.size:\n self.tree[i] += delta\n i += i & (-i)\n\n def sum(self, i):\n s = 0\n while i > 0:\n s += self.tree[i]\n i -= i & (-i)\n return s\n\n def range_sum(self, left, right):\n return self.sum(right) - self.sum(left - 1)\n\n# Usage\nft = FenwickTree(5)\narr = [1, 2, 3, 4, 5]\nfor i, val in enumerate(arr, 1):\n ft.update(i, val)\nprint(ft.range_sum(2, 4)) # Output: 9<\/code><\/pre>\n24. Suffix Arrays<\/h2>\n
Suffix arrays provide a space-efficient alternative to suffix trees for string processing tasks.<\/p>\n
Example: Building a suffix array<\/h3>\ndef build_suffix_array(s):\n suffixes = [(s[i:], i) for i in range(len(s))]\n suffixes.sort()\n return [i for _, i in suffixes]\n\n# Usage\ns = \"banana\"\nsa = build_suffix_array(s)\nprint(sa) # Output: [5, 3, 1, 0, 4, 2]<\/code><\/pre>\n25. Sparse Table<\/h2>\n
Sparse tables provide efficient range minimum\/maximum queries with O(n log n) preprocessing and O(1) query time.<\/p>\n
Example: Sparse table for range minimum queries<\/h3>\nimport math\n\ndef build_sparse_table(arr):\n n = len(arr)\n k = int(math.log2(n)) + 1\n st = [[0] * k for _ in range(n)]\n \n for i in range(n):\n st[i][0] = arr[i]\n \n for j in range(1, k):\n for i in range(n - (1 << j) + 1):\n st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])\n \n return st\n\ndef query(st, L, R):\n j = int(math.log2(R - L + 1))\n return min(st[L][j], st[R - (1 << j) + 1][j])\n\n# Usage\narr = [1, 3, 4, 8, 6, 1, 4, 2]\nsparse_table = build_sparse_table(arr)\nprint(query(sparse_table, 2, 7)) # Output: 1<\/code><\/pre>\n26. Union-Find (Disjoint Set)<\/h2>\n
Union-Find data structure provides efficient operations for maintaining disjoint sets with near-constant time complexity.<\/p>\n
Example: Union-Find implementation<\/h3>\nclass UnionFind:\n def __init__(self, n):\n self.parent = list(range(n))\n self.rank = [0] * n\n\n def find(self, x):\n if self.parent[x] != x:\n self.parent[x] = self.find(self.parent[x])\n return self.parent[x]\n\n def union(self, x, y):\n px, py = self.find(x), self.find(y)\n if px == py:\n return\n if self.rank[px] < self.rank[py]:\n self.parent[px] = py\n elif self.rank[px] > self.rank[py]:\n self.parent[py] = px\n else:\n self.parent[py] = px\n self.rank[px] += 1\n\n# Usage\nuf = UnionFind(5)\nuf.union(0, 1)\nuf.union(2, 3)\nuf.union(1, 2)\nprint(uf.find(0) == uf.find(3)) # Output: True<\/code><\/pre>\n27. Space-Efficient Graph Representations<\/h2>\n
Choosing the right graph representation can significantly impact space usage.<\/p>\n
Example: Adjacency list representation for sparse graphs<\/h3>\nclass Graph:\n def __init__(self, vertices):\n self.V = vertices\n self.graph = [[] for _ in range(vertices)]\n\n def add_edge(self, u, v):\n self.graph[u].append(v)\n self.graph[v].append(u) # For undirected graph\n\n# Usage\ng = Graph(4)\ng.add_edge(0, 1)\ng.add_edge(0, 2)\ng.add_edge(1, 2)\ng.add_edge(2, 3)<\/code><\/pre>\n28. Succinct Data Structures<\/h2>\n
Succinct data structures aim to represent data using space close to the information-theoretic lower bound.<\/p>\n
Example: Succinct representation of a binary tree<\/h3>\nclass SuccinctBinaryTree:\n def __init__(self, tree_string):\n self.tree = tree_string\n\n def is_leaf(self, node):\n return self.tree[node] == '1'\n\n def left_child(self, node):\n return 2 * node + 1\n\n def right_child(self, node):\n return 2 * node + 2\n\n def parent(self, node):\n return (node - 1) \/\/ 2\n\n# Usage\ntree = SuccinctBinaryTree(\"10110100\")\nprint(tree.is_leaf(3)) # Output: True<\/code><\/pre>\n29. Memory-Mapped Files<\/h2>\n
Memory-mapped files allow you to treat file content as if it were in memory, potentially saving RAM for large datasets.<\/p>\n
Example: Using memory-mapped files in Python<\/h3>\nimport mmap\nimport os\n\ndef sum_integers_from_file(filename):\n with open(filename, \"r+b\") as f:\n mmapped_file = mmap.mmap(f.fileno(), 0)\n total = sum(int(line) for line in mmapped_file)\n mmapped_file.close()\n return total\n\n# Usage\n# Assume \"numbers.txt\" contains one integer per line\nprint(sum_integers_from_file(\"numbers.txt\"))<\/code><\/pre>\n30. Streaming Algorithms<\/h2>\n
Streaming algorithms process data in a single pass, using sublinear space relative to the input size.<\/p>\n
Example: Reservoir sampling for random sampling from a stream<\/h3>\nimport random\n\ndef reservoir_sampling(stream, k):\n reservoir = []\n for i, item in enumerate(stream):\n if len(reservoir) < k:\n reservoir.append(item)\n else:\n j = random.randint(0, i)\n if j < k:\n reservoir[j] = item\n return reservoir\n\n# Usage\nstream = range(1000000)\nsample = reservoir_sampling(stream, 10)\nprint(sample)<\/code><\/pre>\n31. Lossy Counting<\/h2>\n
Lossy counting is a technique for approximating frequency counts in data streams with limited space.<\/p>\n
Example: Lossy counting for frequent items<\/h3>\nclass LossyCounter:\n def __init__(self, epsilon):\n self.epsilon = epsilon\n self.N = 0\n self.counts = {}\n self.bucket_id = 1\n\n def add(self, item):\n self.N += 1\n if item in self.counts:\n self.counts[item][0] += 1\n elif len(self.counts) < 1 \/ self.epsilon:\n self.counts[item] = [1, self.bucket_id - 1]\n \n if self.N % int(1 \/ self.epsilon) == 0:\n self.counts = {k: v for k, v in self.counts.items() if v[0] + v[1] > self.bucket_id}\n self.bucket_id += 1\n\n def get_frequent_items(self, support):\n return {k: v[0] for k, v in self.counts.items() if v[0] > (support - self.epsilon) * self.N}\n\n# Usage\nlc = LossyCounter(0.1)\nfor item in [1, 2, 3, 1, 1, 2, 1, 1]:\n lc.add(item)\nprint(lc.get_frequent_items(0.3)) # Output: {1: 5}<\/code><\/pre>\n32. Probabilistic Data Structures<\/h2>\n
Probabilistic data structures trade perfect accuracy for space efficiency.<\/p>\n
Example: HyperLogLog for cardinality estimation<\/h3>\nimport mmh3\nimport math\n\nclass HyperLogLog:\n def __init__(self, p):\n self.p = p\n self.m = 1 << p\n self.registers = [0] * self.m\n self.alpha = self._get_alpha()\n\n def _get_alpha(self):\n if self.p == 4:\n return 0.673\n elif self.p == 5:\n return 0.697\n elif self.p == 6:\n return 0.709\n return 0.7213 \/ (1 + 1.079 \/ self.m)\n\n def add(self, item):\n x = mmh3.hash(item)\n j = x & (self.m - 1)\n w = x >> self.p\n self.registers[j] = max(self.registers[j], self._get_rho(w))\n\n def _get_rho(self, w):\n return len(bin(w)) - 3\n\n def count(self):\n z = sum(math.pow<\/code><\/pre>\n<\/article>\n<\/body><\/html><\/p>\n","protected":false},"excerpt":{"rendered":"
In the world of algorithm design and implementation, efficiency is key. While time complexity often takes center stage, space complexity…<\/p>\n","protected":false},"author":1,"featured_media":6708,"comment_status":"","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-6709","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6709"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=6709"}],"version-history":[{"count":0,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6709\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/6708"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=6709"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=6709"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=6709"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
def reverse_array(arr):\n left, right = 0, len(arr) - 1\n while left < right:\n arr[left], arr[right] = arr[right], arr[left]\n left += 1\n right -= 1\n return arr\n\n# Usage\narr = [1, 2, 3, 4, 5]\nreversed_arr = reverse_array(arr)\nprint(reversed_arr) # Output: [5, 4, 3, 2, 1]<\/code><\/pre>\n2. Bit Manipulation<\/h2>\n
Using bit manipulation techniques can significantly reduce space usage, especially when dealing with boolean flags or small integer values.<\/p>\n
Example: Checking if a number is even using bitwise AND<\/h3>\ndef is_even(num):\n return (num & 1) == 0\n\n# Usage\nprint(is_even(4)) # Output: True\nprint(is_even(7)) # Output: False<\/code><\/pre>\n3. String Interning<\/h2>\n
String interning is a technique where only one copy of each distinct string is stored in memory. This can save space when dealing with many duplicate strings.<\/p>\n
Example: String interning in Python<\/h3>\na = 'hello'\nb = 'hello'\nprint(a is b) # Output: True (both variables reference the same string object)<\/code><\/pre>\n4. Use of Generators<\/h2>\n
Generators allow you to iterate over a sequence of values without storing the entire sequence in memory.<\/p>\n
Example: Using a generator for Fibonacci sequence<\/h3>\ndef fibonacci():\n a, b = 0, 1\n while True:\n yield a\n a, b = b, a + b\n\n# Usage\nfib = fibonacci()\nfor _ in range(10):\n print(next(fib), end=' ')\n# Output: 0 1 1 2 3 5 8 13 21 34<\/code><\/pre>\n5. Memoization<\/h2>\n
Memoization involves caching the results of expensive function calls to avoid redundant computations. While it trades space for time, it can be more space-efficient than naive recursive solutions.<\/p>\n
Example: Memoized Fibonacci<\/h3>\ndef memoized_fib(n, memo={}):\n if n in memo:\n return memo[n]\n if n <= 1:\n return n\n memo[n] = memoized_fib(n-1, memo) + memoized_fib(n-2, memo)\n return memo[n]\n\n# Usage\nprint(memoized_fib(100)) # Calculates 100th Fibonacci number efficiently<\/code><\/pre>\n6. Use of Constant Space<\/h2>\n
Some algorithms can be optimized to use only a constant amount of extra space, regardless of input size.<\/p>\n
Example: Finding the majority element in an array<\/h3>\ndef majority_element(nums):\n candidate = None\n count = 0\n for num in nums:\n if count == 0:\n candidate = num\n count += (1 if num == candidate else -1)\n return candidate\n\n# Usage\narr = [2, 2, 1, 1, 1, 2, 2]\nprint(majority_element(arr)) # Output: 2<\/code><\/pre>\n7. Space-Efficient Data Structures<\/h2>\n
Choosing the right data structure can significantly impact space usage. For example, using a Trie for storing strings with common prefixes can be more space-efficient than storing each string separately.<\/p>\n
Example: Implementing a Trie<\/h3>\nclass TrieNode:\n def __init__(self):\n self.children = {}\n self.is_end = False\n\nclass Trie:\n def __init__(self):\n self.root = TrieNode()\n\n def insert(self, word):\n node = self.root\n for char in word:\n if char not in node.children:\n node.children[char] = TrieNode()\n node = node.children[char]\n node.is_end = True\n\n def search(self, word):\n node = self.root\n for char in word:\n if char not in node.children:\n return False\n node = node.children[char]\n return node.is_end\n\n# Usage\ntrie = Trie()\ntrie.insert(\"apple\")\nprint(trie.search(\"apple\")) # Output: True\nprint(trie.search(\"app\")) # Output: False<\/code><\/pre>\n8. Sliding Window Technique<\/h2>\n
The sliding window technique can be used to process subarrays or substrings efficiently without using extra space.<\/p>\n
Example: Finding the maximum sum subarray of size k<\/h3>\ndef max_sum_subarray(arr, k):\n n = len(arr)\n if n < k:\n return None\n \n window_sum = sum(arr[:k])\n max_sum = window_sum\n \n for i in range(n - k):\n window_sum = window_sum - arr[i] + arr[i + k]\n max_sum = max(max_sum, window_sum)\n \n return max_sum\n\n# Usage\narr = [1, 4, 2, 10, 23, 3, 1, 0, 20]\nk = 4\nprint(max_sum_subarray(arr, k)) # Output: 39<\/code><\/pre>\n9. Two Pointer Technique<\/h2>\n
The two pointer technique can be used to solve various problems with minimal space usage, especially for array and linked list problems.<\/p>\n
Example: Removing duplicates from a sorted array in-place<\/h3>\ndef remove_duplicates(nums):\n if not nums:\n return 0\n \n i = 0\n for j in range(1, len(nums)):\n if nums[j] != nums[i]:\n i += 1\n nums[i] = nums[j]\n \n return i + 1\n\n# Usage\nnums = [1, 1, 2, 2, 3, 4, 4, 5]\nnew_length = remove_duplicates(nums)\nprint(nums[:new_length]) # Output: [1, 2, 3, 4, 5]<\/code><\/pre>\n10. Recursive Space Optimization<\/h2>\n
Tail recursion optimization can help reduce the space complexity of recursive algorithms by reusing stack frames.<\/p>\n
Example: Tail-recursive factorial function<\/h3>\ndef factorial(n, acc=1):\n if n == 0:\n return acc\n return factorial(n - 1, n * acc)\n\n# Usage\nprint(factorial(5)) # Output: 120<\/code><\/pre>\n11. Use of Static Variables<\/h2>\n
In some languages, using static variables can help reduce memory usage by sharing a single copy of the variable across all instances of a class.<\/p>\n
Example: Using static variables in Java<\/h3>\npublic class Counter {\n private static int count = 0;\n\n public void increment() {\n count++;\n }\n\n public int getCount() {\n return count;\n }\n}\n\n\/\/ Usage\nCounter c1 = new Counter();\nCounter c2 = new Counter();\nc1.increment();\nc2.increment();\nSystem.out.println(c1.getCount()); \/\/ Output: 2\nSystem.out.println(c2.getCount()); \/\/ Output: 2<\/code><\/pre>\n12. Space-Time Tradeoffs<\/h2>\n
Sometimes, trading a little space for significant time improvements can be beneficial. For example, using a hash table for O(1) lookup time at the cost of O(n) space.<\/p>\n
Example: Two Sum problem using a hash table<\/h3>\ndef two_sum(nums, target):\n num_dict = {}\n for i, num in enumerate(nums):\n complement = target - num\n if complement in num_dict:\n return [num_dict[complement], i]\n num_dict[num] = i\n return []\n\n# Usage\nnums = [2, 7, 11, 15]\ntarget = 9\nprint(two_sum(nums, target)) # Output: [0, 1]<\/code><\/pre>\n13. Bitsets<\/h2>\n
Bitsets can be used to represent sets of small non-negative integers very space-efficiently.<\/p>\n
Example: Implementing a simple bitset in Python<\/h3>\nclass Bitset:\n def __init__(self, size):\n self.bits = 0\n self.size = size\n\n def set(self, pos):\n self.bits |= (1 << pos)\n\n def clear(self, pos):\n self.bits &= ~(1 << pos)\n\n def test(self, pos):\n return bool(self.bits & (1 << pos))\n\n# Usage\nbs = Bitset(8)\nbs.set(1)\nbs.set(4)\nprint(bs.test(1)) # Output: True\nprint(bs.test(2)) # Output: False<\/code><\/pre>\n14. Sparse Matrix Representation<\/h2>\n
For matrices with many zero elements, using a sparse matrix representation can save significant space.<\/p>\n
Example: Implementing a simple sparse matrix<\/h3>\nclass SparseMatrix:\n def __init__(self, rows, cols):\n self.rows = rows\n self.cols = cols\n self.elements = {}\n\n def set(self, row, col, value):\n if value != 0:\n self.elements[(row, col)] = value\n elif (row, col) in self.elements:\n del self.elements[(row, col)]\n\n def get(self, row, col):\n return self.elements.get((row, col), 0)\n\n# Usage\nsm = SparseMatrix(1000, 1000)\nsm.set(5, 10, 3.14)\nprint(sm.get(5, 10)) # Output: 3.14\nprint(sm.get(0, 0)) # Output: 0<\/code><\/pre>\n15. Compression Techniques<\/h2>\n
Data compression can be used to reduce the space required to store or transmit data.<\/p>\n
Example: Simple run-length encoding<\/h3>\ndef run_length_encode(s):\n if not s:\n return \"\"\n result = []\n count = 1\n for i in range(1, len(s)):\n if s[i] == s[i-1]:\n count += 1\n else:\n result.append(f\"{count}{s[i-1]}\")\n count = 1\n result.append(f\"{count}{s[-1]}\")\n return ''.join(result)\n\n# Usage\nprint(run_length_encode(\"AABBBCCCC\")) # Output: 2A3B4C<\/code><\/pre>\n16. Memory Pooling<\/h2>\n
Memory pooling involves pre-allocating a large chunk of memory and managing it manually to avoid frequent allocations and deallocations.<\/p>\n
Example: Simple object pool in Python<\/h3>\nclass ObjectPool:\n def __init__(self, create_func, max_size):\n self.create_func = create_func\n self.max_size = max_size\n self.pool = []\n\n def acquire(self):\n if self.pool:\n return self.pool.pop()\n return self.create_func()\n\n def release(self, obj):\n if len(self.pool) < self.max_size:\n self.pool.append(obj)\n\n# Usage\ndef create_expensive_object():\n return [0] * 1000000 # Large list\n\npool = ObjectPool(create_expensive_object, 5)\nobj1 = pool.acquire()\nobj2 = pool.acquire()\npool.release(obj1)\nobj3 = pool.acquire() # This will reuse obj1<\/code><\/pre>\n17. Lazy Evaluation<\/h2>\n
Lazy evaluation defers the computation of values until they are actually needed, potentially saving space.<\/p>\n
Example: Lazy evaluation using Python’s property decorator<\/h3>\nclass LazyComputation:\n def __init__(self):\n self._expensive_result = None\n\n @property\n def expensive_result(self):\n if self._expensive_result is None:\n print(\"Computing expensive result...\")\n self._expensive_result = sum(range(1000000))\n return self._expensive_result\n\n# Usage\nlc = LazyComputation()\nprint(lc.expensive_result) # Computes and prints result\nprint(lc.expensive_result) # Uses cached result<\/code><\/pre>\n18. Space-Efficient Sorting Algorithms<\/h2>\n
Some sorting algorithms, like Heapsort, can sort in-place with O(1) extra space.<\/p>\n
Example: In-place Heapsort<\/h3>\ndef heapify(arr, n, i):\n largest = i\n left = 2 * i + 1\n right = 2 * i + 2\n\n if left < n and arr[largest] < arr[left]:\n largest = left\n\n if right < n and arr[largest] < arr[right]:\n largest = right\n\n if largest != i:\n arr[i], arr[largest] = arr[largest], arr[i]\n heapify(arr, n, largest)\n\ndef heapsort(arr):\n n = len(arr)\n\n for i in range(n \/\/ 2 - 1, -1, -1):\n heapify(arr, n, i)\n\n for i in range(n - 1, 0, -1):\n arr[0], arr[i] = arr[i], arr[0]\n heapify(arr, i, 0)\n\n# Usage\narr = [12, 11, 13, 5, 6, 7]\nheapsort(arr)\nprint(arr) # Output: [5, 6, 7, 11, 12, 13]<\/code><\/pre>\n19. Circular Buffers<\/h2>\n
Circular buffers can be used to implement queues with fixed memory usage.<\/p>\n
Example: Implementing a circular buffer<\/h3>\nclass CircularBuffer:\n def __init__(self, size):\n self.buffer = [None] * size\n self.head = 0\n self.tail = 0\n self.size = size\n self.count = 0\n\n def enqueue(self, item):\n if self.count == self.size:\n raise Exception(\"Buffer is full\")\n self.buffer[self.tail] = item\n self.tail = (self.tail + 1) % self.size\n self.count += 1\n\n def dequeue(self):\n if self.count == 0:\n raise Exception(\"Buffer is empty\")\n item = self.buffer[self.head]\n self.head = (self.head + 1) % self.size\n self.count -= 1\n return item\n\n# Usage\ncb = CircularBuffer(3)\ncb.enqueue(1)\ncb.enqueue(2)\ncb.enqueue(3)\nprint(cb.dequeue()) # Output: 1\ncb.enqueue(4)\nprint(cb.dequeue()) # Output: 2<\/code><\/pre>\n20. Bloom Filters<\/h2>\n
Bloom filters provide a space-efficient probabilistic data structure for set membership queries.<\/p>\n
Example: Simple Bloom filter implementation<\/h3>\nimport mmh3\n\nclass BloomFilter:\n def __init__(self, size, hash_count):\n self.size = size\n self.hash_count = hash_count\n self.bit_array = [0] * size\n\n def add(self, item):\n for seed in range(self.hash_count):\n result = mmh3.hash(item, seed) % self.size\n self.bit_array[result] = 1\n\n def check(self, item):\n for seed in range(self.hash_count):\n result = mmh3.hash(item, seed) % self.size\n if self.bit_array[result] == 0:\n return False\n return True\n\n# Usage\nbf = BloomFilter(20, 3)\nbf.add(\"apple\")\nbf.add(\"banana\")\nprint(bf.check(\"apple\")) # Output: True\nprint(bf.check(\"orange\")) # Output: False (probably)<\/code><\/pre>\n21. Prefix Sum Array<\/h2>\n
Prefix sum arrays can be used to efficiently compute range sums with O(1) space complexity after preprocessing.<\/p>\n
Example: Range sum queries using prefix sum<\/h3>\ndef build_prefix_sum(arr):\n prefix_sum = [0] * (len(arr) + 1)\n for i in range(1, len(prefix_sum)):\n prefix_sum[i] = prefix_sum[i-1] + arr[i-1]\n return prefix_sum\n\ndef range_sum(prefix_sum, left, right):\n return prefix_sum[right + 1] - prefix_sum[left]\n\n# Usage\narr = [1, 2, 3, 4, 5]\nprefix_sum = build_prefix_sum(arr)\nprint(range_sum(prefix_sum, 1, 3)) # Sum of arr[1:4], Output: 9<\/code><\/pre>\n22. Segment Trees<\/h2>\n
Segment trees provide efficient range queries and updates with O(n) space complexity.<\/p>\n
Example: Segment tree for range minimum queries<\/h3>\nclass SegmentTree:\n def __init__(self, arr):\n self.n = len(arr)\n self.tree = [0] * (4 * self.n)\n self.build(arr, 0, 0, self.n - 1)\n\n def build(self, arr, node, start, end):\n if start == end:\n self.tree[node] = arr[start]\n else:\n mid = (start + end) \/\/ 2\n self.build(arr, 2*node+1, start, mid)\n self.build(arr, 2*node+2, mid+1, end)\n self.tree[node] = min(self.tree[2*node+1], self.tree[2*node+2])\n\n def query(self, node, start, end, l, r):\n if r < start or end < l:\n return float('inf')\n if l <= start and end <= r:\n return self.tree[node]\n mid = (start + end) \/\/ 2\n left = self.query(2*node+1, start, mid, l, r)\n right = self.query(2*node+2, mid+1, end, l, r)\n return min(left, right)\n\n def range_minimum(self, l, r):\n return self.query(0, 0, self.n-1, l, r)\n\n# Usage\narr = [1, 3, 2, 7, 9, 11]\nst = SegmentTree(arr)\nprint(st.range_minimum(1, 4)) # Output: 2<\/code><\/pre>\n23. Fenwick Trees (Binary Indexed Trees)<\/h2>\n
Fenwick trees provide efficient range sum queries and updates with O(n) space complexity.<\/p>\n
Example: Fenwick tree for range sum queries<\/h3>\nclass FenwickTree:\n def __init__(self, n):\n self.size = n\n self.tree = [0] * (n + 1)\n\n def update(self, i, delta):\n while i <= self.size:\n self.tree[i] += delta\n i += i & (-i)\n\n def sum(self, i):\n s = 0\n while i > 0:\n s += self.tree[i]\n i -= i & (-i)\n return s\n\n def range_sum(self, left, right):\n return self.sum(right) - self.sum(left - 1)\n\n# Usage\nft = FenwickTree(5)\narr = [1, 2, 3, 4, 5]\nfor i, val in enumerate(arr, 1):\n ft.update(i, val)\nprint(ft.range_sum(2, 4)) # Output: 9<\/code><\/pre>\n24. Suffix Arrays<\/h2>\n
Suffix arrays provide a space-efficient alternative to suffix trees for string processing tasks.<\/p>\n
Example: Building a suffix array<\/h3>\ndef build_suffix_array(s):\n suffixes = [(s[i:], i) for i in range(len(s))]\n suffixes.sort()\n return [i for _, i in suffixes]\n\n# Usage\ns = \"banana\"\nsa = build_suffix_array(s)\nprint(sa) # Output: [5, 3, 1, 0, 4, 2]<\/code><\/pre>\n25. Sparse Table<\/h2>\n
Sparse tables provide efficient range minimum\/maximum queries with O(n log n) preprocessing and O(1) query time.<\/p>\n
Example: Sparse table for range minimum queries<\/h3>\nimport math\n\ndef build_sparse_table(arr):\n n = len(arr)\n k = int(math.log2(n)) + 1\n st = [[0] * k for _ in range(n)]\n \n for i in range(n):\n st[i][0] = arr[i]\n \n for j in range(1, k):\n for i in range(n - (1 << j) + 1):\n st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])\n \n return st\n\ndef query(st, L, R):\n j = int(math.log2(R - L + 1))\n return min(st[L][j], st[R - (1 << j) + 1][j])\n\n# Usage\narr = [1, 3, 4, 8, 6, 1, 4, 2]\nsparse_table = build_sparse_table(arr)\nprint(query(sparse_table, 2, 7)) # Output: 1<\/code><\/pre>\n26. Union-Find (Disjoint Set)<\/h2>\n
Union-Find data structure provides efficient operations for maintaining disjoint sets with near-constant time complexity.<\/p>\n
Example: Union-Find implementation<\/h3>\nclass UnionFind:\n def __init__(self, n):\n self.parent = list(range(n))\n self.rank = [0] * n\n\n def find(self, x):\n if self.parent[x] != x:\n self.parent[x] = self.find(self.parent[x])\n return self.parent[x]\n\n def union(self, x, y):\n px, py = self.find(x), self.find(y)\n if px == py:\n return\n if self.rank[px] < self.rank[py]:\n self.parent[px] = py\n elif self.rank[px] > self.rank[py]:\n self.parent[py] = px\n else:\n self.parent[py] = px\n self.rank[px] += 1\n\n# Usage\nuf = UnionFind(5)\nuf.union(0, 1)\nuf.union(2, 3)\nuf.union(1, 2)\nprint(uf.find(0) == uf.find(3)) # Output: True<\/code><\/pre>\n27. Space-Efficient Graph Representations<\/h2>\n
Choosing the right graph representation can significantly impact space usage.<\/p>\n
Example: Adjacency list representation for sparse graphs<\/h3>\nclass Graph:\n def __init__(self, vertices):\n self.V = vertices\n self.graph = [[] for _ in range(vertices)]\n\n def add_edge(self, u, v):\n self.graph[u].append(v)\n self.graph[v].append(u) # For undirected graph\n\n# Usage\ng = Graph(4)\ng.add_edge(0, 1)\ng.add_edge(0, 2)\ng.add_edge(1, 2)\ng.add_edge(2, 3)<\/code><\/pre>\n28. Succinct Data Structures<\/h2>\n
Succinct data structures aim to represent data using space close to the information-theoretic lower bound.<\/p>\n
Example: Succinct representation of a binary tree<\/h3>\nclass SuccinctBinaryTree:\n def __init__(self, tree_string):\n self.tree = tree_string\n\n def is_leaf(self, node):\n return self.tree[node] == '1'\n\n def left_child(self, node):\n return 2 * node + 1\n\n def right_child(self, node):\n return 2 * node + 2\n\n def parent(self, node):\n return (node - 1) \/\/ 2\n\n# Usage\ntree = SuccinctBinaryTree(\"10110100\")\nprint(tree.is_leaf(3)) # Output: True<\/code><\/pre>\n29. Memory-Mapped Files<\/h2>\n
Memory-mapped files allow you to treat file content as if it were in memory, potentially saving RAM for large datasets.<\/p>\n
Example: Using memory-mapped files in Python<\/h3>\nimport mmap\nimport os\n\ndef sum_integers_from_file(filename):\n with open(filename, \"r+b\") as f:\n mmapped_file = mmap.mmap(f.fileno(), 0)\n total = sum(int(line) for line in mmapped_file)\n mmapped_file.close()\n return total\n\n# Usage\n# Assume \"numbers.txt\" contains one integer per line\nprint(sum_integers_from_file(\"numbers.txt\"))<\/code><\/pre>\n30. Streaming Algorithms<\/h2>\n
Streaming algorithms process data in a single pass, using sublinear space relative to the input size.<\/p>\n
Example: Reservoir sampling for random sampling from a stream<\/h3>\nimport random\n\ndef reservoir_sampling(stream, k):\n reservoir = []\n for i, item in enumerate(stream):\n if len(reservoir) < k:\n reservoir.append(item)\n else:\n j = random.randint(0, i)\n if j < k:\n reservoir[j] = item\n return reservoir\n\n# Usage\nstream = range(1000000)\nsample = reservoir_sampling(stream, 10)\nprint(sample)<\/code><\/pre>\n31. Lossy Counting<\/h2>\n
Lossy counting is a technique for approximating frequency counts in data streams with limited space.<\/p>\n
Example: Lossy counting for frequent items<\/h3>\nclass LossyCounter:\n def __init__(self, epsilon):\n self.epsilon = epsilon\n self.N = 0\n self.counts = {}\n self.bucket_id = 1\n\n def add(self, item):\n self.N += 1\n if item in self.counts:\n self.counts[item][0] += 1\n elif len(self.counts) < 1 \/ self.epsilon:\n self.counts[item] = [1, self.bucket_id - 1]\n \n if self.N % int(1 \/ self.epsilon) == 0:\n self.counts = {k: v for k, v in self.counts.items() if v[0] + v[1] > self.bucket_id}\n self.bucket_id += 1\n\n def get_frequent_items(self, support):\n return {k: v[0] for k, v in self.counts.items() if v[0] > (support - self.epsilon) * self.N}\n\n# Usage\nlc = LossyCounter(0.1)\nfor item in [1, 2, 3, 1, 1, 2, 1, 1]:\n lc.add(item)\nprint(lc.get_frequent_items(0.3)) # Output: {1: 5}<\/code><\/pre>\n32. Probabilistic Data Structures<\/h2>\n
Probabilistic data structures trade perfect accuracy for space efficiency.<\/p>\n
Example: HyperLogLog for cardinality estimation<\/h3>\nimport mmh3\nimport math\n\nclass HyperLogLog:\n def __init__(self, p):\n self.p = p\n self.m = 1 << p\n self.registers = [0] * self.m\n self.alpha = self._get_alpha()\n\n def _get_alpha(self):\n if self.p == 4:\n return 0.673\n elif self.p == 5:\n return 0.697\n elif self.p == 6:\n return 0.709\n return 0.7213 \/ (1 + 1.079 \/ self.m)\n\n def add(self, item):\n x = mmh3.hash(item)\n j = x & (self.m - 1)\n w = x >> self.p\n self.registers[j] = max(self.registers[j], self._get_rho(w))\n\n def _get_rho(self, w):\n return len(bin(w)) - 3\n\n def count(self):\n z = sum(math.pow<\/code><\/pre>\n<\/article>\n<\/body><\/html><\/p>\n","protected":false},"excerpt":{"rendered":"
In the world of algorithm design and implementation, efficiency is key. While time complexity often takes center stage, space complexity…<\/p>\n","protected":false},"author":1,"featured_media":6708,"comment_status":"","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-6709","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6709"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=6709"}],"version-history":[{"count":0,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6709\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/6708"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=6709"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=6709"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=6709"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}