ARRAYS & STRINGS
CHEAT SHEET.

Array Basics

String Basics

Two Pointers Technique

// Opposite direction (sorted array)
function twoSum(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        let sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        if (sum < target) left++;
        else right--;
    }
    return [];
}

// Same direction (fast & slow)
function removeDuplicates(arr) {
    let slow = 0;
    for (let fast = 1; fast < arr.length; fast++) {
        if (arr[fast] !== arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1;  // new length
}

Sliding Window

// Fixed window size
function maxSumSubarray(arr, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += arr[i];
    let maxSum = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

// Variable window size
function longestSubstringWithoutRepeating(s) {
    let set = new Set();
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        while (set.has(s[right])) {
            set.delete(s[left]);
            left++;
        }
        set.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Prefix Sum

// Build prefix sum array
function prefixSum(arr) {
    let prefix = [0];
    for (let i = 0; i < arr.length; i++) {
        prefix.push(prefix[i] + arr[i]);
    }
    return prefix;
}

// Range sum query (sum from i to j)
function rangeSum(prefix, i, j) {
    return prefix[j + 1] - prefix[i];
}

// Subarray sum equals k
function subarraySum(nums, k) {
    let map = new Map();
    map.set(0, 1);
    let sum = 0, count = 0;
    for (let num of nums) {
        sum += num;
        if (map.has(sum - k)) count += map.get(sum - k);
        map.set(sum, (map.get(sum) || 0) + 1);
    }
    return count;
}

Common Algorithms

Kadane's Algorithm (Max Subarray Sum)

function maxSubarraySum(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];
    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

Dutch Flag (3‑way Partitioning)

function sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
        }
    }
}

Moore's Voting Algorithm (Majority Element)

function majorityElement(nums) {
    let candidate = nums[0];
    let count = 0;
    for (let num of nums) {
        if (count === 0) candidate = num;
        count += (num === candidate) ? 1 : -1;
    }
    return candidate;  // guaranteed majority
}

Cyclic Sort (1‑n arrays)

function cyclicSort(arr) {
    let i = 0;
    while (i < arr.length) {
        let correct = arr[i] - 1;
        if (arr[i] !== arr[correct]) {
            [arr[i], arr[correct]] = [arr[correct], arr[i]];
        } else {
            i++;
        }
    }
    return arr;
}

String Algorithms

KMP (Knuth-Morris-Pratt) Pattern Matching

function buildLPS(pattern) {
    let lps = new Array(pattern.length).fill(0);
    let len = 0;
    let i = 1;
    while (i < pattern.length) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else if (len > 0) {
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return lps;
}

function kmp(text, pattern) {
    if (!pattern.length) return 0;
    let lps = buildLPS(pattern);
    let i = 0, j = 0;
    while (i < text.length) {
        if (text[i] === pattern[j]) {
            i++;
            j++;
            if (j === pattern.length) return i - j;
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return -1;
}

Rabin-Karp (Rolling Hash)

function rabinKarp(text, pattern) {
    const d = 256;
    const q = 101;
    let n = text.length, m = pattern.length;
    let p = 0, t = 0, h = 1;
    for (let i = 0; i < m - 1; i++) h = (h * d) % q;
    for (let i = 0; i < m; i++) {
        p = (d * p + pattern.charCodeAt(i)) % q;
        t = (d * t + text.charCodeAt(i)) % q;
    }
    for (let i = 0; i <= n - m; i++) {
        if (p === t) {
            let match = true;
            for (let j = 0; j < m; j++) {
                if (text[i + j] !== pattern[j]) { match = false; break; }
            }
            if (match) return i;
        }
        if (i < n - m) {
            t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
            if (t < 0) t += q;
        }
    }
    return -1;
}

Common Array Problems

Common String Problems

Complexities Summary

Operation	Time Complexity	Space Complexity
Array Access	O(1)	O(1)
Array Search (unsorted)	O(n)	O(1)
Array Search (sorted - binary)	O(log n)	O(1)
Array Insert (end)	O(1)	O(1)
Array Insert (middle)	O(n)	O(1)
Array Delete (end)	O(1)	O(1)
Array Delete (middle)	O(n)	O(1)
String Concatenation	O(n)	O(n)
String Substring	O(n)	O(n)
Two Pointers	O(n)	O(1)
Sliding Window	O(n)	O(k) or O(1)