# Dynamic Programming in JavaScript: Complete Guide with Examples In this comprehensive **dynamic programming tutorial**, we dive into **DP algorithms** and optimization techniques, solving classic **coding interview problems** step by step. Whether you're preparing for **FAANG interviews** or improving your **data structures and algorithms** skills, these patterns are essential. We'll break down each problem with multiple **JavaScript solutions**, explain **time and space complexity**, and show you optimized approaches used in **technical interviews** at Google, Meta, Amazon, and Microsoft. These **LeetCode problems** remain high-value coding interview questions, commonly appearing on platforms like LeetCode, HackerRank, and company assessments. --- ## 1. Longest Increasing Subsequence (LIS) The **Longest Increasing Subsequence** is a classic **DP problem** frequently asked in **coding interviews**. It tests your understanding of **memoization** and **binary search optimization**. ### Problem Description Find the length of the longest subsequence of a given sequence, such that all elements are sorted in increasing order. Example: `[10, 9, 2, 5, 3, 7, 101, 18]` → LIS is `[2, 3, 7, 101]`, length = 4. ### O(n²) DP Solution (Classic) ```js function longestIncreasingSubsequence(nums) { const n = nums.length; if (n === 0) return 0; const dp = Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } return Math.max(...dp); } ``` - **Time complexity:** O(n²) - **Space complexity:** O(n) ### Optimized O(n log n) Solution (Binary Search) ```js function longestIncreasingSubsequence(nums) { const tails = []; for (let num of nums) { let l = 0, r = tails.length; while (l < r) { const mid = Math.floor((l + r) / 2); if (tails[mid] < num) l = mid + 1; else r = mid; } tails[l] = num; } return tails.length; } ``` - **Time complexity:** O(n log n) - **Space complexity:** O(n) This optimized solution is the standard approach for LIS when an O(n log n) bound is required. --- ## 2. Longest Common Subsequence (LCS) ### Problem Description Find the longest subsequence common to two strings. Example: `"ABCD"` and `"ACDF"` → LCS is `"ACD"`. ### O(m × n) DP Solution ```js function longestCommonSubsequence(str1, str2) { const m = str1.length, n = str2.length; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (str1[i - 1] === str2[j - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } ``` - **Time complexity:** O(m × n) - **Space complexity:** O(m × n) ### Space-Optimized O(min(m, n)) Version ```js function longestCommonSubsequence(str1, str2) { if (str1.length < str2.length) [str1, str2] = [str2, str1]; const m = str1.length, n = str2.length; const dp = Array.from({ length: 2 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (str1[i - 1] === str2[j - 1]) { dp[i % 2][j] = 1 + dp[(i - 1) % 2][j - 1]; } else { dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]); } } } return dp[m % 2][n]; } ``` - **Time complexity:** O(m × n) - **Space complexity:** O(min(m, n)) --- ## 3. Longest Palindromic Substring ### Problem Description Find the longest contiguous substring of a string that is a palindrome. Example: `"babad"` → `"bab"` or `"aba"`. ### Expand Around Center (O(n²), O(1) space) ```js function expandAroundCenter(s, left, right) { while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } return right - left - 1; } function longestPalindromicSubstring(s) { let start = 0, end = 0; for (let i = 0; i < s.length; i++) { const len = Math.max( expandAroundCenter(s, i, i), expandAroundCenter(s, i, i + 1) ); if (len > end - start) { start = i - Math.floor((len - 1) / 2); end = i + Math.floor(len / 2); } } return s.substring(start, end + 1); } ``` ### Manacher's Algorithm (O(n), O(n) space) A linear-time approach worth knowing for harder interview rounds, though the simpler expand-around-center solution above is usually sufficient. ```js function manachersAlgorithm(s) { let T = "#" + s.split("").join("#") + "#"; const P = Array(T.length).fill(0); let C = 0, R = 0, maxLen = 0, centerIndex = 0; for (let i = 1; i < T.length - 1; i++) { if (i < R) P[i] = Math.min(R - i, P[2 * C - i]); while (T[i + P[i] + 1] === T[i - P[i] - 1]) P[i]++; if (i + P[i] > R) [C, R] = [i, i + P[i]]; if (P[i] > maxLen) [maxLen, centerIndex] = [P[i], i]; } const start = Math.floor((centerIndex - maxLen) / 2); return s.substring(start, start + maxLen); } ``` --- ## 4. Longest Palindromic Subsequence ### Problem Description Find the longest subsequence (not substring) that is a palindrome. ### O(n²) DP Solution ```js function longestPalindromicSubsequence(s) { const n = s.length; const dp = Array.from({ length: n }, () => Array(n).fill(0)); for (let i = 0; i < n; i++) dp[i][i] = 1; for (let len = 2; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; if (s[i] === s[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } ``` - **Time complexity:** O(n²) - **Space complexity:** O(n²), reducible to O(n) with rolling arrays. --- ## 5. Maximum Product Subarray ### Problem Description Find the contiguous subarray with the maximum product. ### O(n), O(1) Solution ```js function maxProductSubarray(nums) { let maxProd = nums[0], minProd = nums[0], result = nums[0]; for (let i = 1; i < nums.length; i++) { const curr = nums[i]; const temp = maxProd; maxProd = Math.max(curr, curr * maxProd, curr * minProd); minProd = Math.min(curr, curr * temp, curr * minProd); result = Math.max(result, maxProd); } return result; } ``` --- ## 6. Largest Rectangle in a Histogram ### Problem Description Find the largest rectangle area in a histogram. ### Stack-Based O(n) Solution ```js function largestRectangleArea(heights) { const stack = []; let maxArea = 0; for (let i = 0; i <= heights.length; i++) { const h = i === heights.length ? 0 : heights[i]; while (stack.length && h < heights[stack.at(-1)]) { const height = heights[stack.pop()]; const width = stack.length === 0 ? i : i - stack.at(-1) - 1; maxArea = Math.max(maxArea, height * width); } stack.push(i); } return maxArea; } ``` - **Time complexity:** O(n) - **Space complexity:** O(n) This remains the textbook optimal solution and is what most interviewers expect. --- ## 7. Egg Dropping Problem ### Problem Description Given `n` eggs and `k` floors, find the minimum number of attempts needed to find the highest floor an egg can be dropped without breaking. ### DP Solution ```js function eggDrop(n, k) { const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0)); for (let i = 1; i <= n; i++) { dp[i][1] = 1; dp[i][0] = 0; } for (let j = 1; j <= k; j++) dp[1][j] = j; for (let i = 2; i <= n; i++) { for (let j = 2; j <= k; j++) { dp[i][j] = Infinity; for (let x = 1; x <= j; x++) { const res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]); dp[i][j] = Math.min(dp[i][j], res); } } } return dp[n][k]; } ``` - **Time complexity:** O(n × k²) → can be optimized to O(n × k log k) with binary search inside the inner loop, or O(n × k) by exploiting the monotonicity of the optimal split. - Still a tough interview classic. --- ## 8. Counting Bits ### Problem Description Given a number `num`, return an array of the count of `1`s in binary for every number ≤ num. ### O(n) Solution ```js function countBits(num) { const dp = new Array(num + 1).fill(0); for (let i = 1; i <= num; i++) { dp[i] = dp[i >> 1] + (i & 1); } return dp; } ``` - **Time complexity:** O(n) - **Space complexity:** O(n) --- ## 9. Perfect Squares ### Problem Description Find the least number of perfect square numbers that sum to `n`. ### DP Solution ```js function numSquares(n) { const dp = Array(n + 1).fill(Infinity); dp[0] = 0; for (let i = 1; i <= n; i++) { for (let j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; } ``` - **Time complexity:** O(n√n) - **Space complexity:** O(n) --- ## 10. Unique Paths ### Problem Description Find the number of unique paths in an m × n grid, moving only down or right. ### DP Solution ```js function uniquePaths(m, n) { const dp = Array(m).fill().map(() => Array(n).fill(1)); for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } ``` - **Time complexity:** O(m × n) - **Space complexity:** O(m × n), reducible to O(min(m, n)) with a single rolling row, or O(1) using the closed-form C(m + n − 2, m − 1) binomial coefficient. --- ## Conclusion **Dynamic programming** and related techniques (binary search optimization, stack-based algorithms, memoization) remain core coding interview skills. These **algorithm patterns** appear consistently in **technical interviews** at top tech companies. Key takeaways for mastering **DP problems**: - Identify **overlapping subproblems** and **optimal substructure** - Start with the **brute force recursive solution**, then optimize with **memoization** or **tabulation** - Practice problems on **LeetCode**, **HackerRank**, and **NeetCode** to build pattern recognition - Focus on **time and space complexity analysis** to explain trade-offs in interviews Whether you're preparing for **software engineering interviews** or building **high-performance JavaScript applications**, these **algorithmic techniques** form the foundation of efficient problem-solving. [^mdn-js]: MDN Web Docs — JavaScript Guide. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide

#dynamic-programming

شرح البرمجة الديناميكية وتقنيات أخرى مع أمثلة