Common LeetCode Patterns
// Two Pointers - In-place array modification
const modifyArray = ( arr ) => {
let writePointer = 0 ;
for ( let readPointer = 0 ; readPointer < arr . length ; readPointer ++ ) {
if ( /* condition */ ) {
[ arr [ writePointer ], arr [ readPointer ]] = [ arr [ readPointer ], arr [ writePointer ]];
writePointer ++ ;
}
}
return writePointer ; // Often returns new length or modified position
};
// Fast and Slow Pointers (Floyd's Cycle Detection)
const hasCycle = ( head ) => {
let slow = head , fast = head ;
while ( fast && fast . next ) {
slow = slow . next ;
fast = fast . next . next ;
if ( slow === fast ) return true ;
}
return false ;
};
// Sliding Window - Fixed Size
const fixedSlidingWindow = ( arr , k ) => {
let sum = 0 ;
// Initialize first window
for ( let i = 0 ; i < k ; i ++ ) {
sum += arr [ i ];
}
let maxSum = sum ;
// Slide window
for ( let i = k ; i < arr . length ; i ++ ) {
sum = sum - arr [ i - k ] + arr [ i ];
maxSum = Math . max ( maxSum , sum );
}
return maxSum ;
};
// Sliding Window - Variable Size
const varSlidingWindow = ( arr , target ) => {
let start = 0 , sum = 0 , minLen = Infinity ;
for ( let end = 0 ; end < arr . length ; end ++ ) {
sum += arr [ end ];
while ( sum >= target ) {
minLen = Math . min ( minLen , end - start + 1 );
sum -= arr [ start ];
start ++ ;
}
}
return minLen === Infinity ? 0 : minLen ;
};
// BFS - Level Order Traversal
const levelOrder = ( root ) => {
if ( ! root ) return [];
const result = [];
const queue = [ root ];
while ( queue . length ) {
const levelSize = queue . length ;
const currentLevel = [];
for ( let i = 0 ; i < levelSize ; i ++ ) {
const node = queue . shift ();
currentLevel . push ( node . val );
if ( node . left ) queue . push ( node . left );
if ( node . right ) queue . push ( node . right );
}
result . push ( currentLevel );
}
return result ;
};
// DFS - Recursive Template
const dfs = ( root ) => {
const result = [];
const traverse = ( node ) => {
if ( ! node ) return ;
// Pre-order
result . push ( node . val );
traverse ( node . left );
// In-order would be here
traverse ( node . right );
// Post-order would be here
};
traverse ( root );
return result ;
};
// Backtracking Template
const backtrack = ( nums ) => {
const result = [];
const bt = ( path , choices ) => {
if ( /* ending condition */ ) {
result . push ([... path ]);
return ;
}
for ( let i = 0 ; i < choices . length ; i ++ ) {
// Make choice
path . push ( choices [ i ]);
// Recurse
bt ( path , /* remaining choices */ );
// Undo choice
path . pop ();
}
};
bt ([], nums );
return result ;
};
// Dynamic Programming - Bottom Up Template
const dpBottomUp = ( n ) => {
const dp = new Array ( n + 1 ). fill ( 0 );
dp [ 0 ] = 1 ; // Base case
for ( let i = 1 ; i <= n ; i ++ ) {
for ( let j = 0 ; j < i ; j ++ ) {
dp [ i ] += dp [ j ] * /* some calculation */ ;
}
}
return dp [ n ];
};
// Dynamic Programming - Top Down Template
const dpTopDown = ( n ) => {
const memo = new Map ();
const dp = ( n ) => {
if ( n <= 1 ) return 1 ;
if ( memo . has ( n )) return memo . get ( n );
let result = 0 ;
for ( let i = 0 ; i < n ; i ++ ) {
result += dp ( i ) * /* some calculation */ ;
}
memo . set ( n , result );
return result ;
};
return dp ( n );
};
// Monotonic Stack Template
const monotonicStack = ( arr ) => {
const stack = []; // [index, value]
const result = new Array ( arr . length ). fill ( - 1 );
for ( let i = 0 ; i < arr . length ; i ++ ) {
while ( stack . length && stack [ stack . length - 1 ][ 1 ] > arr [ i ]) {
const [ prevIndex , _ ] = stack . pop ();
result [ prevIndex ] = i - prevIndex ;
}
stack . push ([ i , arr [ i ]]);
}
return result ;
};
// Prefix Sum
const prefixSum = ( arr ) => {
const prefix = [ 0 ];
for ( let i = 0 ; i < arr . length ; i ++ ) {
prefix . push ( prefix [ prefix . length - 1 ] + arr [ i ]);
}
// Sum of range [i, j] = prefix[j + 1] - prefix[i]
return prefix ;
};
// Binary Search Variations
const binarySearchLeftmost = ( arr , target ) => {
let left = 0 , right = arr . length ;
while ( left < right ) {
const mid = Math . floor (( left + right ) / 2 );
if ( arr [ mid ] < target ) left = mid + 1 ;
else right = mid ;
}
return left ;
};
const binarySearchRightmost = ( arr , target ) => {
let left = 0 , right = arr . length ;
while ( left < right ) {
const mid = Math . floor (( left + right ) / 2 );
if ( arr [ mid ] <= target ) left = mid + 1 ;
else right = mid ;
}
return left - 1 ;
};
// Trie Operations
class TrieNode {
constructor () {
this . children = new Map ();
this . isEndOfWord = false ;
}
}
class Trie {
constructor () {
this . root = new TrieNode ();
}
insert ( word ) {
let node = this . root ;
for ( const char of word ) {
if ( ! node . children . has ( char )) {
node . children . set ( char , new TrieNode ());
}
node = node . children . get ( char );
}
node . isEndOfWord = true ;
}
search ( word ) {
let node = this . root ;
for ( const char of word ) {
if ( ! node . children . has ( char )) return false ;
node = node . children . get ( char );
}
return node . isEndOfWord ;
}
startsWith ( prefix ) {
let node = this . root ;
for ( const char of prefix ) {
if ( ! node . children . has ( char )) return false ;
node = node . children . get ( char );
}
return true ;
}
}
// Union Find (Disjoint Set)
class UnionFind {
constructor ( n ) {
this . parent = Array . from ({ length : n }, ( _ , i ) => i );
this . rank = new Array ( n ). fill ( 0 );
}
find ( x ) {
if ( this . parent [ x ] !== x ) {
this . parent [ x ] = this . find ( this . parent [ x ]); // Path compression
}
return this . parent [ x ];
}
union ( x , y ) {
let rootX = this . find ( x );
let rootY = this . find ( y );
if ( rootX !== rootY ) {
if ( this . rank [ rootX ] < this . rank [ rootY ]) {
[ rootX , rootY ] = [ rootY , rootX ];
}
this . parent [ rootY ] = rootX ;
if ( this . rank [ rootX ] === this . rank [ rootY ]) {
this . rank [ rootX ] ++ ;
}
}
}
}
Enter fullscreen mode
Exit fullscreen mode
Common Time/Space Complexity Patterns
// O(1) - Constant
Array . push (), Array . pop (), Map . set (), Map . get ()
// O(log n) - Logarithmic
Binary Search , Balanced BST operations
// O(n) - Linear
Array traversal , Linear Search
// O(n log n) - Linearithmic
Efficient sorting ( Array . sort ())
// O(nΒ²) - Quadratic
Nested loops , Simple sorting algorithms
// O(2βΏ) - Exponential
Recursive solutions without memoization
Enter fullscreen mode
Exit fullscreen mode
Top comments (0)