In this article, we will dive into the world of dynamic programming (DP) and related optimization techniques, focusing on solving some programming challenges step by step.
We’ll break down each problem, present multiple solutions in JavaScript, and explain the time and space complexities.

These problems remain high-value interview questions in 2025, commonly appearing on platforms like LeetCode, HackerRank, and coding assessments.

---

2. Longest Increasing Subsequence (LIS)

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)

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)

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 in 2025 for LIS.

---

3. 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

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

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))

---

4. 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)

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)

Optimal solution for interviews.

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);
}

---

5. Longest Palindromic Subsequence

Problem Description

Find the longest subsequence (not substring) that is a palindrome.

O(n²) DP Solution

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.

---

6. Maximum Product Subarray

Problem Description

Find the contiguous subarray with the maximum product.

O(n), O(1) Solution

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;
}

---

7. Largest Rectangle in a Histogram

Problem Description

Find the largest rectangle area in a histogram.

Stack-Based O(n) Solution

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 optimal solution in 2025.

---

8. 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

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).
• Still a tough interview classic in 2025.

---

9. Counting Bits

Problem Description

Given a number num, return an array of the count of 1s in binary for every number ≤ num.

O(n) Solution

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)

---

10. Perfect Squares

Problem Description

Find the least number of perfect square numbers that sum to n.

DP Solution

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)

---

11. Unique Paths

Problem Description

Find the number of unique paths in an m × n grid, moving only down or right.

DP Solution

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)

---

Conclusion

Dynamic programming and related techniques (binary search, stack-based optimizations, memoization) are essential interview skills in 2025. 🚀