Optimizing Space Complexity
1. Implementing Space-Time Tradeoffs
| Pattern | Description | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|---|
| Hash Maps / Sets | Use hash tables to store and retrieve data in O(1) average time. | O(n) | O(n) | When frequent lookups are needed, and memory is not a constraint. |
| Caching / Memoization | Store results of expensive function calls to avoid recomputation. | O(1) for lookup, O(n) for computation | O(n) | Dynamic programming problems with overlapping subproblems. |
| Preprocessing | Transform input data into a more efficient structure (e.g., sorted array). | O(n log n) | O(n) | When multiple queries on the same data are expected. |
| In-Place Operations | Modify input data directly without using extra space (e.g., sorting in-place). | O(n log n) | O(1) | When memory is constrained and input can be modified. |
Example: Using Hash Maps for Lookup Optimization
const nums = [2, 7, 11, 15];
const target = 9;
// O(n) space, O(n) time
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
console.log([map.get(complement), i]);
break;
}
map.set(nums[i], i);
}Example: Memoization for Fibonacci
// O(n) space, O(n) time
const memo = {};
function fib(n) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
Note: Tradeoffs between space and time depend on the problem constraints and expected query patterns.
2. Using In-Place Algorithms
| Algorithm | Description | Space Complexity | Notes |
|---|---|---|---|
| Two Pointers | Use two pointers to traverse array/list from both ends towards center | O(1) |
Commonly used for reversing, merging sorted arrays |
| Floyd's Cycle Detection | Detect cycles in linked lists using slow and fast pointers | O(1) |
Also known as the "tortoise and hare" algorithm |
| Partitioning (Lomuto/Hoare) | Reorganize array elements around a pivot without extra space | O(1) |
Used in quicksort; Hoare is more efficient |
Example: Two Pointers for Reversing Array
function reverseArray(arr) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
return arr;
}
// Example usage:
const nums = [1, 2, 3, 4, 5];
reverseArray(nums);
// Result: [5, 4, 3, 2, 1]Example: Floyd's Cycle Detection
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function hasCycle(head) {
if (!head || !head.next) return false;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}3. Implementing Constant Space DP
| Pattern | Description | Key Techniques | Examples |
|---|---|---|---|
| Space-Optimized DP | Using only necessary variables to store intermediate results | Reusing previous state values, avoiding full DP tables | |
| Two-Pointer Technique | Using two pointers to traverse data with minimal space | Single pass, in-place updates | |
| Sliding Window | Maintaining a window of elements with minimal storage | Fixed-size or variable-size windows | |
Example: Space-Optimized Fibonacci
function fib(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
let curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
Note: This approach reduces space from O(n) to O(1) by only storing the last two computed values.
4. Using Bit Manipulation
| Operation | Description | Example |
|---|---|---|
| AND (&) | Performs bitwise AND operation | |
| OR (|) | Performs bitwise OR operation | |
| XOR (^) | Performs bitwise XOR operation | |
| NOT (~) | Performs bitwise NOT operation | |
| Left Shift (<<) | Shifts bits to the left | |
| Right Shift (>>) | Shifts bits to the right | |
Common Bit Manipulation Techniques
- Check if a number is even or odd: Use
n & 1where0means even,1means odd. - Toggle a bit: Use XOR with
1at the desired position. - Set a bit: Use OR with
1at the desired position. - Clear a bit: Use AND with
0at the desired position. - Get a bit: Use AND with
1shifted to the position of interest.
Example: Find Unique Number in Array
Given an array where every element appears twice except one, find the unique number using XOR.
function findUnique(arr) {
let result = 0;
for (let num of arr) {
result ^= num;
}
return result;
}
// Example usage:
let nums = [2, 3, 2, 4, 4];
console.log(findUnique(nums)); // Output: 35. Implementing Two-Variable DP
| Pattern | Description | Use Case | Space Complexity |
|---|---|---|---|
| Two-Variable DP | Uses only two variables to store previous and current states | Optimizing space in dynamic programming problems with linear recurrence | O(1) |
Example: Fibonacci with Two Variables
function fibonacci(n) {
if (n <= 1) return n;
let prev2 = 0;
let prev1 = 1;
let current;
for (let i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// Example usage:
console.log(fibonacci(5)); // Output: 5
Note: This approach reduces space complexity from O(n) to O(1) by maintaining only the last two computed values.
6. Using Hash Set vs Array
| Feature | Hash Set | Array |
|---|---|---|
| Time Complexity (Lookup) | O(1) average |
O(n) |
| Space Complexity | O(n) |
O(n) |
| Duplicate Handling | Automatically handles duplicates | Manual handling required |
| Ordering | No order guarantee | Ordered by insertion |
| Memory Overhead | Higher due to hash table structure | Lower, more compact |
Example: Finding Duplicates in Array
const nums = [1, 2, 3, 2, 4, 5];
const seen = new Set();
let hasDuplicates = false;
for (let num of nums) {
if (seen.has(num)) {
hasDuplicates = true;
break;
}
seen.add(num);
}
console.log(hasDuplicates); // true
Example: Using Array for Ordered Unique Elements
const nums = [1, 2, 3, 2, 4, 5];
const unique = [];
for (let num of nums) {
if (!unique.includes(num)) {
unique.push(num);
}
}
console.log(unique); // [1, 2, 3, 4, 5]
When to Use Which
- Hash Set is preferred for fast lookups and automatic duplicate handling.
- Array is preferred when order matters or memory usage is a strict constraint.
7. Implementing Sliding Window
| Property | Description | Usage |
|---|---|---|
| windowStart | Start index of the sliding window | Initialize to 0 |
| windowEnd | End index of the sliding window | Incremented in loop |
| windowSize | Current size of the window | Calculated as (windowEnd - windowStart + 1) |
Example: Maximum Sum Subarray of Size K
function maxSumSubarray(arr, k) {
let windowStart = 0;
let windowSum = 0;
let maxSum = -Infinity;
for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
windowSum += arr[windowEnd];
if (windowEnd >= k - 1) {
maxSum = Math.max(maxSum, windowSum);
windowSum -= arr[windowStart];
windowStart++;
}
}
return maxSum;
}
// Example usage:
const arr = [2, 1, 5, 1, 3, 2];
const k = 3;
console.log(maxSumSubarray(arr, k)); // Output: 9
Example: Longest Substring with K Distinct Characters
function longestSubstringWithKDistinct(str, k) {
let windowStart = 0;
let maxLength = 0;
const charFrequency = new Map();
for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
const rightChar = str[windowEnd];
charFrequency.set(rightChar, (charFrequency.get(rightChar) || 0) + 1);
while (charFrequency.size > k) {
const leftChar = str[windowStart];
charFrequency.set(leftChar, charFrequency.get(leftChar) - 1);
if (charFrequency.get(leftChar) === 0) {
charFrequency.delete(leftChar);
}
windowStart++;
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}
// Example usage:
const str = "araaci";
const k = 2;
console.log(longestSubstringWithKDistinct(str, k)); // Output: 4
8. Using Deque vs Array
| Feature | Deque | Array |
|---|---|---|
| Insertion at Front | O(1) |
O(n) |
| Insertion at Back | O(1) |
O(1) |
| Deletion at Front | O(1) |
O(n) |
| Deletion at Back | O(1) |
O(1) |
| Random Access | O(1) |
O(1) |
| Memory Layout | Dynamic, non-contiguous | Contiguous |
Example: Deque Operations
const deque = [];
// Insert at front - O(1)
deque.unshift(10);
// Insert at back - O(1)
deque.push(20);
// Delete from front - O(1)
deque.shift();
// Delete from back - O(1)
deque.pop();
Example: Array Operations
const arr = [];
// Insert at back - O(1)
arr.push(20);
// Insert at front - O(n) - inefficient
arr.unshift(10);
// Delete from back - O(1)
arr.pop();
// Delete from front - O(n) - inefficient
arr.shift();
When to Use Which
- Use Deque when frequent insertions/deletions at both ends are required.
- Use Array when random access is more important than front operations.
9. Implementing Generator Functions
Generator functions are a powerful feature in JavaScript that allow you to write functions that can be paused and resumed, enabling efficient memory usage and lazy evaluation.
| Feature | Description | Example |
|---|---|---|
| Generator Function Declaration | Defined using the function* syntax. |
|
| Generator Function Expression | Defined using the function* keyword as an expression. |
|
| Generator Object | Returned when calling a generator function. It implements the Iterator protocol. | |
| yield Keyword | Pauses the generator and yields a value to the caller. | |
| yield* Expression | Delegates to another generator or iterable. | |
Example: Fibonacci Sequence with Generators
function* fibonacci() {
let a = 0, b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
const fib = fibonacci();
console.log(fib.next().value); // 0
console.log(fib.next().value); // 1
console.log(fib.next().value); // 1
console.log(fib.next().value); // 2Example: Generator with Error Handling
function* errorGenerator() {
try {
yield 1;
throw new Error('Something went wrong');
} catch (e) {
console.error(e.message);
yield 'handled';
}
}
const gen = errorGenerator();
console.log(gen.next().value); // 1
console.log(gen.next().value); // handled10. Using Pointer Manipulation
| Technique | Description | Use Case | Complexity |
|---|---|---|---|
| Two Pointers | Use two indices to traverse the array or list from both ends towards the center. | Searching for pairs in a sorted array, reversing arrays, removing duplicates. | O(1) space |
| Fast and Slow Pointers | Use two pointers moving at different speeds to detect cycles or find middle elements. | Finding the middle of a linked list, detecting cycles in a linked list. | O(1) space |
| Sliding Window | Maintain a window of elements and adjust its size dynamically to optimize operations. | Maximum sum subarray, longest substring without repeating characters. | O(1) space |
Example: Two Pointers for Pair Sum
function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}
Example: Fast and Slow Pointers for Cycle Detection
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true;
}
}
return false;
}
11. Implementing Modulo Arithmetic
| Operation | Description | Example |
|---|---|---|
| Modulo (%) | Computes the remainder after division of two numbers. | let remainder = 17 % 5; // 2 |
| Modulo with Negative Numbers | Result has the same sign as the divisor. | let result = -17 % 5; // -2 |
| Modulo in Looping Contexts | Useful for circular indexing or wrapping around arrays. | let arr = [10, 20, 30, 40];<br>let index = (current + 1) % arr.length; |
| Modulo for Even/Odd Check | Check if a number is even or odd using n % 2. |
if (num % 2 === 0) {<br> // Even<br>} else {<br> // Odd<br>} |
Example: Circular Buffer Implementation
class CircularBuffer {<br> constructor(size) {<br> this.buffer = new Array(size);<br> this.size = size;<br> this.head = 0;<br> this.tail = 0;<br> this.count = 0;<br> }<br><br> enqueue(value) {<br> if (this.count === this.size) throw new Error("Buffer full");<br> this.buffer[this.tail] = value;<br> this.tail = (this.tail + 1) % this.size;<br> this.count++;<br> }<br><br> dequeue() {<br> if (this.count === 0) throw new Error("Buffer empty");<br> let value = this.buffer[this.head];<br> this.head = (this.head + 1) % this.size;<br> this.count--;<br> return value;<br> }<br>}12. Using Boolean Array Compression
Boolean array compression is a technique used to reduce the space complexity of algorithms that involve storing or processing large arrays of boolean values. By compressing these arrays, we can significantly reduce memory usage while maintaining the same logical behavior.
| Technique | Description | Space Complexity | Use Case |
|---|---|---|---|
| Bit Packing | Store multiple boolean values in a single integer using bitwise operations. | O(n/32) for 32-bit integers | Efficient storage of flags or binary states |
| Sparse Boolean Arrays | Only store indices of true values instead of full arrays. | O(k) where k is number of true values | Memory-constrained environments with sparse data |
| Run-Length Encoding (RLE) | Compress sequences of same boolean values. | O(k) where k is number of runs | Arrays with long sequences of same values |
Example: Bit Packing
function packBooleans(boolArray) {
const packed = [];
for (let i = 0; i < boolArray.length; i += 32) {
let word = 0;
for (let j = 0; j < 32 && i + j < boolArray.length; j++) {
if (boolArray[i + j]) {
word |= (1 << j);
}
}
packed.push(word);
}
return packed;
}
function unpackBooleans(packed, length) {
const result = new Array(length);
for (let i = 0; i < packed.length; i++) {
const word = packed[i];
for (let j = 0; j < 32 && i * 32 + j < length; j++) {
result[i * 32 + j] = (word & (1 << j)) !== 0;
}
}
return result;
}
// Example usage:
const bools = [true, false, true, true, false];
const packed = packBooleans(bools);
console.log(packed); // [5] (binary: 101)
const unpacked = unpackBooleans(packed, bools.length);
console.log(unpacked); // [true, false, true, true, false]
Example: Sparse Boolean Array
class SparseBooleanArray {
constructor(size) {
this.size = size;
this.trueIndices = new Set();
}
set(index, value) {
if (index < 0 || index >= this.size) {
throw new Error("Index out of bounds");
}
if (value) {
this.trueIndices.add(index);
} else {
this.trueIndices.delete(index);
}
}
get(index) {
return this.trueIndices.has(index);
}
size() {
return this.trueIndices.size;
}
}
// Example usage:
const sparse = new SparseBooleanArray(1000);
sparse.set(5, true);
sparse.set(100, true);
console.log(sparse.get(5)); // true
console.log(sparse.get(10)); // false
console.log(sparse.size()); // 2
Note: Bit packing is most effective when working with large arrays where the overhead of bit manipulation is amortized over many elements. Sparse arrays are ideal for scenarios with very few true values.