Top 10 DSA Problems Every Developer Must Master in 2025

1. Two Sum Problem

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Each problem instance contains precisely one valid answer, with no element being reused in the solution.

Real-World Applications

E-commerce: Finding complementary products that together meet a budget constraint
Financial Trading: Identifying pairs of stocks whose combined price meets investment criteria
Game Development: Finding item combinations that achieve specific stat totals

Visual Representation

Array: [2, 7, 11, 15]
Target: 9

Index:  0  1   2   3
Value: [2, 7, 11, 15]
        ↑  ↑
       2 + 7 = 9 ✓

Steps to Solve

Brute Force Approach: Check every pair of numbers
Optimized Approach: Use a hash map to store complements
Single Pass: Store values while checking for complements

JavaScript Solution

/**
 * Two Sum - Optimized Hash Map Solution
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
function twoSum(nums, target) {
    const numMap = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        
        numMap.set(nums[i], i);
    }
    
    return []; // No solution found
}

// Example usage
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // Output: [0, 1]

Python Solution

def two_sum(nums, target):
    """
    Two Sum - Optimized Hash Map Solution
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    num_map = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        if complement in num_map:
            return [num_map[complement], i]
        
        num_map[num] = i
    
    return []  # No solution found

# Example usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

2. Reverse a Linked List

Problem Statement

Provided with the starting node of a unidirectional linked structure, invert the sequence and output the modified list.

Real-World Applications

Browser History: Implementing back navigation functionality
Undo Operations: Reversing a sequence of operations in text editors
Music Playlist: Reversing the order of songs in a playlist

Visual Representation

Original: 1 → 2 → 3 → 4 → 5 → NULL
Reversed: 5 → 4 → 3 → 2 → 1 → NULL

Steps to Solve

Initialize: Three pointers - previous, current, and next
Iterate: Through the linked list
Reverse: The direction of each link
Update: Move all pointers forward

JavaScript Solution

/**
 * Definition for singly-linked list node
 */
class ListNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

/**
 * Reverse Linked List - Iterative Solution
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function reverseList(head) {
    let prev = null;
    let current = head;
    
    while (current !== null) {
        const nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    
    return prev;
}

/**
 * Reverse Linked List - Recursive Solution
 * Time Complexity: O(n)
 * Space Complexity: O(n) due to recursion stack
 */
function reverseListRecursive(head) {
    if (head === null || head.next === null) {
        return head;
    }
    
    const reversedHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return reversedHead;
}

Python Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    """
    Reverse Linked List - Iterative Solution
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    prev = None
    current = head
    
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    
    return prev

def reverse_list_recursive(head):
    """
    Reverse Linked List - Recursive Solution
    Time Complexity: O(n)
    Space Complexity: O(n) due to recursion stack
    """
    if not head or not head.next:
        return head
    
    reversed_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    
    return reversed_head

3. Valid Parentheses

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if brackets are opened and closed in the correct order.

Real-World Applications

Code Editors: Syntax validation and bracket matching
Mathematical Expressions: Validating equation syntax
XML/HTML Parsing: Ensuring proper tag nesting

Visual Representation

Valid:   "({[]})"
Stack:   [ ( { [    →    [ ( {    →    [ (    →    [    →    []

Invalid: "([)]"
Stack:   [ ( [    →    [ (    →    Stack not empty ✗

Steps to Solve

Use a Stack: To keep track of opening brackets
Iterate: Through each character in the string
Push: Opening brackets onto the stack
Match: Closing brackets with stack top
Validate: Stack should be empty at the end

JavaScript Solution

/**
 * Valid Parentheses
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
function isValid(s) {
    const stack = [];
    const mapping = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (let char of s) {
        if (char in mapping) {
            // Closing bracket
            const topElement = stack.length === 0 ? '#' : stack.pop();
            if (mapping[char] !== topElement) {
                return false;
            }
        } else {
            // Opening bracket
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

// Example usage
console.log(isValid("()"));        // true
console.log(isValid("()[]{}"));    // true
console.log(isValid("(]"));        // false
console.log(isValid("([)]"));      // false

Python Solution

def is_valid(s):
    """
    Valid Parentheses
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            # Closing bracket
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            # Opening bracket
            stack.append(char)
    
    return len(stack) == 0

# Example usage
print(is_valid("()"))        # True
print(is_valid("()[]{}"))    # True
print(is_valid("(]"))        # False
print(is_valid("([)]"))      # False

4. Binary Tree Traversal

Problem Statement

Implement three different ways to traverse a binary tree: Inorder, Preorder, and Postorder traversal.

Real-World Applications

File System Navigation: Traversing directory structures
Expression Evaluation: Converting infix to postfix notation
Database Indexing: B-tree traversal for efficient searching

Visual Representation

Binary Tree:
        1
       / \
      2   3
     / \
    4   5

Inorder (Left, Root, Right): 4, 2, 5, 1, 3
Preorder (Root, Left, Right): 1, 2, 4, 5, 3
Postorder (Left, Right, Root): 4, 5, 2, 3, 1

Steps to Solve

Recursive Approach: Use the call stack naturally
Iterative Approach: Use an explicit stack
Handle Base Case: When node is null

JavaScript Solution

/**
 * Definition for a binary tree node
 */
class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

/**
 * Inorder Traversal - Recursive
 * Time Complexity: O(n)
 * Space Complexity: O(h) where h is height of tree
 */
function inorderTraversal(root) {
    const result = [];
    
    function inorder(node) {
        if (node !== null) {
            inorder(node.left);
            result.push(node.val);
            inorder(node.right);
        }
    }
    
    inorder(root);
    return result;
}

/**
 * Inorder Traversal - Iterative
 * Time Complexity: O(n)
 * Space Complexity: O(h)
 */
function inorderTraversalIterative(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current !== null || stack.length > 0) {
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    
    return result;
}

/**
 * Preorder Traversal - Recursive
 */
function preorderTraversal(root) {
    const result = [];
    
    function preorder(node) {
        if (node !== null) {
            result.push(node.val);
            preorder(node.left);
            preorder(node.right);
        }
    }
    
    preorder(root);
    return result;
}

/**
 * Postorder Traversal - Recursive
 */
function postorderTraversal(root) {
    const result = [];
    
    function postorder(node) {
        if (node !== null) {
            postorder(node.left);
            postorder(node.right);
            result.push(node.val);
        }
    }
    
    postorder(root);
    return result;
}

Python Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    """
    Inorder Traversal - Recursive
    Time Complexity: O(n)
    Space Complexity: O(h) where h is height of tree
    """
    result = []
    
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    
    inorder(root)
    return result

def inorder_traversal_iterative(root):
    """
    Inorder Traversal - Iterative
    Time Complexity: O(n)
    Space Complexity: O(h)
    """
    result = []
    stack = []
    current = root
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        result.append(current.val)
        current = current.right
    
    return result

def preorder_traversal(root):
    """Preorder Traversal - Recursive"""
    result = []
    
    def preorder(node):
        if node:
            result.append(node.val)
            preorder(node.left)
            preorder(node.right)
    
    preorder(root)
    return result

def postorder_traversal(root):
    """Postorder Traversal - Recursive"""
    result = []
    
    def postorder(node):
        if node:
            postorder(node.left)
            postorder(node.right)
            result.append(node.val)
    
    postorder(root)
    return result

5. Merge Two Sorted Lists

Problem Statement

Two ordered linked structures are provided, each identified by their respective starting nodes. Merge the two lists in a sorted fashion and return the head of the merged linked list.

Real-World Applications

Database Operations: Merging sorted result sets
Log File Processing: Combining chronologically sorted log files
Version Control: Merging sorted commit histories

Visual Representation

List1: 1 → 2 → 4
List2:      1 → 3 → 4
Merged: 1 → 1 → 2 → 3 → 4 → 4

Steps to Solve

Create Dummy Node: To simplify edge cases
Compare Values: From both lists
Link Smaller Value: To the result list
Advance Pointer: Of the chosen list
Handle Remaining: Elements from non-empty list

JavaScript Solution

/**
 * Merge Two Sorted Lists
 * Time Complexity: O(n + m)
 * Space Complexity: O(1)
 */
function mergeTwoLists(list1, list2) {
    // Create a dummy node to simplify the logic
    const dummy = new ListNode(0);
    let current = dummy;
    
    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    // Attach the remaining elements
    current.next = list1 !== null ? list1 : list2;
    
    return dummy.next;
}

/**
 * Merge Two Sorted Lists - Recursive Solution
 * Time Complexity: O(n + m)
 * Space Complexity: O(n + m) due to recursion stack
 */
function mergeTwoListsRecursive(list1, list2) {
    if (list1 === null) return list2;
    if (list2 === null) return list1;
    
    if (list1.val <= list2.val) {
        list1.next = mergeTwoListsRecursive(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoListsRecursive(list1, list2.next);
        return list2;
    }
}

Python Solution

def merge_two_lists(list1, list2):
    """
    Merge Two Sorted Lists - Iterative
    Time Complexity: O(n + m)
    Space Complexity: O(1)
    """
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # Attach remaining elements
    current.next = list1 if list1 else list2
    
    return dummy.next

def merge_two_lists_recursive(list1, list2):
    """
    Merge Two Sorted Lists - Recursive
    Time Complexity: O(n + m)
    Space Complexity: O(n + m) due to recursion stack
    """
    if not list1:
        return list2
    if not list2:
        return list1
    
    if list1.val <= list2.val:
        list1.next = merge_two_lists_recursive(list1.next, list2)
        return list1
    else:
        list2.next = merge_two_lists_recursive(list1, list2.next)
        return list2

6. Maximum Subarray (Kadane's Algorithm)

Problem Statement

Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.

Real-World Applications

Stock Trading: Finding the best time period to hold stocks
Image Processing: Finding the brightest rectangular region
Data Analytics: Identifying peak performance periods

Visual Representation

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Subarray: [4, -1, 2, 1] has the largest sum = 6

Current Sum tracking:
-2 → 1 → -2 → 4 → 3 → 5 → 6 → 1 → 5
     ↑         ↑         ↑
   Reset    Start      Max

Steps to Solve

Initialize: Current sum and maximum sum
Iterate: Through the array
Update Current Sum: Add current element or start fresh
Update Maximum: Keep track of the best sum seen so far

JavaScript Solution

/**
 * Maximum Subarray - Kadane's Algorithm
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function maxSubArray(nums) {
    let currentSum = nums[0];
    let maxSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // Either extend the existing subarray or start a new one
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

/**
 * Maximum Subarray - Return the actual subarray
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function maxSubArrayWithIndices(nums) {
    let currentSum = nums[0];
    let maxSum = nums[0];
    let start = 0, end = 0, tempStart = 0;
    
    for (let i = 1; i < nums.length; i++) {
        if (currentSum < 0) {
            currentSum = nums[i];
            tempStart = i;
        } else {
            currentSum += nums[i];
        }
        
        if (currentSum > maxSum) {
            maxSum = currentSum;
            start = tempStart;
            end = i;
        }
    }
    
    return {
        sum: maxSum,
        subarray: nums.slice(start, end + 1),
        startIndex: start,
        endIndex: end
    };
}

// Example usage
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // Output: 6
console.log(maxSubArrayWithIndices(nums));

Python Solution

def max_subarray(nums):
    """
    Maximum Subarray - Kadane's Algorithm
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    current_sum = nums[0]
    max_sum = nums[0]
    
    for i in range(1, len(nums)):
        # Either extend the existing subarray or start a new one
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

def max_subarray_with_indices(nums):
    """
    Maximum Subarray - Return the actual subarray
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    current_sum = nums[0]
    max_sum = nums[0]
    start = end = temp_start = 0
    
    for i in range(1, len(nums)):
        if current_sum < 0:
            current_sum = nums[i]
            temp_start = i
        else:
            current_sum += nums[i]
        
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i
    
    return {
        'sum': max_sum,
        'subarray': nums[start:end+1],
        'start_index': start,
        'end_index': end
    }

# Example usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums))  # Output: 6
print(max_subarray_with_indices(nums))

7. Binary Search

Problem Statement

Within an ordered integer collection, locate the position of a specified value, returning its index when found or -1 when absent.

Real-World Applications

Database Indexing: Finding records in sorted databases
Version Control: Finding specific commits in sorted history
Game Development: Finding optimal difficulty levels

Visual Representation

Array: [1, 3, 5, 7, 9, 11, 13, 15]
Target: 7

Step 1: [1, 3, 5, 7, 9, 11, 13, 15]
             ↑     ↑      ↑
           left  mid    right
        nums[mid] = 7 = target ✓

Steps to Solve

Initialize: Left and right pointers
Calculate Middle: Avoid integer overflow
Compare: Target with middle element
Adjust Boundaries: Based on comparison
Repeat: Until target found or search space exhausted

JavaScript Solution

/**
 * Binary Search - Iterative
 * Time Complexity: O(log n)
 * Space Complexity: O(1)
 */
function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        // Avoid potential integer overflow
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Target not found
}

/**
 * Binary Search - Recursive
 * Time Complexity: O(log n)
 * Space Complexity: O(log n) due to recursion stack
 */
function binarySearchRecursive(nums, target, left = 0, right = nums.length - 1) {
    if (left > right) {
        return -1; // Base case: target not found
    }
    
    const mid = left + Math.floor((right - left) / 2);
    
    if (nums[mid] === target) {
        return mid;
    } else if (nums[mid] < target) {
        return binarySearchRecursive(nums, target, mid + 1, right);
    } else {
        return binarySearchRecursive(nums, target, left, mid - 1);
    }
}

/**
 * Binary Search - Find Insert Position
 * Time Complexity: O(log n)
 * Space Complexity: O(1)
 */
function searchInsert(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left; // Insert position
}

// Example usage
const nums = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(nums, 7));        // Output: 3
console.log(binarySearch(nums, 6));        // Output: -1
console.log(searchInsert(nums, 6));        // Output: 3

Python Solution

def binary_search(nums, target):
    """
    Binary Search - Iterative
    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        # Avoid potential integer overflow
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Target not found

def binary_search_recursive(nums, target, left=0, right=None):
    """
    Binary Search - Recursive
    Time Complexity: O(log n)
    Space Complexity: O(log n) due to recursion stack
    """
    if right is None:
        right = len(nums) - 1
    
    if left > right:
        return -1  # Base case: target not found
    
    mid = left + (right - left) // 2
    
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_recursive(nums, target, mid + 1, right)
    else:
        return binary_search_recursive(nums, target, left, mid - 1)

def search_insert(nums, target):
    """
    Binary Search - Find Insert Position
    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left  # Insert position

# Example usage
nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))        # Output: 3
print(binary_search(nums, 6))        # Output: -1
print(search_insert(nums, 6))        # Output: 3

8. Longest Common Subsequence

Problem Statement

For two character sequences, determine the maximum length of their shared subsequence pattern. A subsequence emerges by removing zero or more characters while preserving the relative positioning of retained elements.

Real-World Applications

DNA Sequencing: Finding similarities between genetic sequences
Version Control: Calculating differences between file versions
Plagiarism Detection: Identifying common text patterns

Visual Representation

text1: "abcde"
text2: "ace"

DP Table:
    ""  a  c  e
""   0  0  0  0
a    0  1  1  1
b    0  1  1  1
c    0  1  2  2
d    0  1  2  2
e    0  1  2  3

LCS: "ace" (length = 3)

Steps to Solve

Create DP Table: (m+1) x (n+1) dimensions
Base Cases: Empty string scenarios
Fill Table: Compare characters and take maximum
Character Match: Diagonal + 1
No Match: Maximum of left or top

JavaScript Solution

/**
 * Longest Common Subsequence - Dynamic Programming
 * Time Complexity: O(m * n)
 * Space Complexity: O(m * n)
 */
function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    
    // Create DP table
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    // Fill the DP table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

/**
 * LCS - Space Optimized Version
 * Time Complexity: O(m * n)
 * Space Complexity: O(min(m, n))
 */
function longestCommonSubsequenceOptimized(text1, text2) {
    // Ensure text1 is the shorter string
    if (text1.length > text2.length) {
        [text1, text2] = [text2, text1];
    }
    
    const m = text1.length;
    const n = text2.length;
    
    let prev = Array(n + 1).fill(0);
    let curr = Array(n + 1).fill(0);
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
        }
        [prev, curr] = [curr, prev];
    }
    
    return prev[n];
}

/**
 * LCS - Return the actual subsequence
 * Time Complexity: O(m * n)
 * Space Complexity: O(m * n)
 */
function getLongestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    // Fill the DP table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // Reconstruct the LCS
    const lcs = [];
    let i = m, j = n;
    
    while (i > 0 && j > 0) {
        if (text1[i - 1] === text2[j - 1]) {
            lcs.unshift(text1[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return lcs.join('');
}

// Example usage
console.log(longestCommonSubsequence("abcde", "ace")); // Output: 3
console.log(getLongestCommonSubsequence("abcde", "ace")); // Output: "ace"

Python Solution

def longest_common_subsequence(text1, text2):
    """
    Longest Common Subsequence - Dynamic Programming
    Time Complexity: O(m * n)
    Space Complexity: O(m * n)
    """
    m, n = len(text1), len(text2)
    
    # Create DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

def longest_common_subsequence_optimized(text1, text2):
    """
    LCS - Space Optimized Version
    Time Complexity: O(m * n)
    Space Complexity: O(min(m, n))
    """
    # Ensure text1 is the shorter string
    if len(text1) > len(text2):
        text1, text2 = text2, text1
    
    m, n = len(text1), len(text2)
    
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, prev
    
    return prev[n]

def get_longest_common_subsequence(text1, text2):
    """
    LCS - Return the actual subsequence
    Time Complexity: O(m * n)
    Space Complexity: O(m * n)
    """
    m, n = len(text1), len(text2)
    
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # Reconstruct the LCS
    lcs = []
    i, j = m, n
    
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:
            lcs.append(text1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(lcs))

# Example usage
print(longest_common_subsequence("abcde", "ace"))  # Output: 3
print(get_longest_common_subsequence("abcde", "ace"))  # Output: "ace"

9. Clone Graph

Problem Statement

Starting from a single vertex within an undirected connected network, create a complete duplicate of the entire graph structure. Each node in the graph contains a value and a list of its neighbors.

Real-World Applications

Social Networks: Copying user connection graphs for analysis
Network Topology: Creating backup copies of network structures
Game Development: Duplicating game world graphs for different levels

Visual Representation

Original Graph:
1 ── 2
│    │
4 ── 3

Cloned Graph:
1' ── 2'
│     │
4' ── 3'

Steps to Solve

Use HashMap: To track visited nodes and their clones
DFS/BFS Traversal: To visit all nodes
Create Clone: For each unvisited node
Clone Neighbors: Recursively clone all neighbor nodes

JavaScript Solution

/**
 * Definition for a Node
 */
class Node {
    constructor(val, neighbors) {
        this.val = val === undefined ? 0 : val;
        this.neighbors = neighbors === undefined ? [] : neighbors;
    }
}

/**
 * Clone Graph - DFS Approach
 * Time Complexity: O(V + E)
 * Space Complexity: O(V)
 */
function cloneGraph(node) {
    if (!node) return null;
    
    const visited = new Map();
    
    function dfs(node) {
        if (visited.has(node)) {
            return visited.get(node);
        }
        
        // Create a clone of the current node
        const clone = new Node(node.val);
        visited.set(node, clone);
        
        // Clone all neighbors
        for (let neighbor of node.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        
        return clone;
    }
    
    return dfs(node);
}

/**
 * Clone Graph - BFS Approach
 * Time Complexity: O(V + E)
 * Space Complexity: O(V)
 */
function cloneGraphBFS(node) {
    if (!node) return null;
    
    const visited = new Map();
    const queue = [node];
    
    // Clone the first node
    visited.set(node, new Node(node.val));
    
    while (queue.length > 0) {
        const current = queue.shift();
        const clone = visited.get(current);
        
        for (let neighbor of current.neighbors) {
            if (!visited.has(neighbor)) {
                // Create clone for unvisited neighbor
                visited.set(neighbor, new Node(neighbor.val));
                queue.push(neighbor);
            }
            
            // Add neighbor to current node's clone
            clone.neighbors.push(visited.get(neighbor));
        }
    }
    
    return visited.get(node);
}

// Example usage - Creating a simple graph
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);

node1.neighbors = [node2, node4];
node2.neighbors = [node1, node3];
node3.neighbors = [node2, node4];
node4.neighbors = [node1, node3];

const clonedGraph = cloneGraph(node1);

Python Solution

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    """
    Clone Graph - DFS Approach
    Time Complexity: O(V + E)
    Space Complexity: O(V)
    """
    if not node:
        return None
    
    visited = {}
    
    def dfs(node):
        if node in visited:
            return visited[node]
        
        # Create a clone of the current node
        clone = Node(node.val)
        visited[node] = clone
        
        # Clone all neighbors
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

def clone_graph_bfs(node):
    """
    Clone Graph - BFS Approach
    Time Complexity: O(V + E)
    Space Complexity: O(V)
    """
    if not node:
        return None
    
    from collections import deque
    
    visited = {}
    queue = deque([node])
    
    # Clone the first node
    visited[node] = Node(node.val)
    
    while queue:
        current = queue.popleft()
        clone = visited[current]
        
        for neighbor in current.neighbors:
            if neighbor not in visited:
                # Create clone for unvisited neighbor
                visited[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            
            # Add neighbor to current node's clone
            clone.neighbors.append(visited[neighbor])
    
    return visited[node]

# Example usage - Creating a simple graph
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

node1.neighbors = [node2, node4]
node2.neighbors = [node1, node3]
node3.neighbors = [node2, node4]
node4.neighbors = [node1, node3]

cloned_graph = clone_graph(node1)

10. Serialize and Deserialize Binary Tree

Problem Statement

Design an algorithm to serialize and deserialize a binary tree. Serialization is the process of converting a data structure into a sequence of bits so that it can be stored or transmitted and reconstructed later.

Real-World Applications

Database Storage: Storing hierarchical data structures
Network Communication: Transmitting tree structures between systems
Caching: Saving and restoring tree states in memory

Visual Representation

Binary Tree:
    1
   / \
  2   3
     / \
    4   5

Serialized: "1,2,null,null,3,4,null,null,5,null,null"

Steps to Solve

Serialization: Use preorder traversal with null markers
Deserialization: Reconstruct tree using the serialized string
Handle Null Nodes: Use placeholders for missing nodes
Use Delimiter: To separate values in the string

JavaScript Solution

/**
 * Serialize and Deserialize Binary Tree
 * Time Complexity: O(n) for both operations
 * Space Complexity: O(n) for both operations
 */

class Codec {
    /**
     * Encodes a tree to a single string
     * @param {TreeNode} root
     * @return {string}
     */
    serialize(root) {
        const result = [];
        
        function preorder(node) {
            if (node === null) {
                result.push('null');
                return;
            }
            
            result.push(node.val.toString());
            preorder(node.left);
            preorder(node.right);
        }
        
        preorder(root);
        return result.join(',');
    }
    
    /**
     * Decodes your encoded data to tree
     * @param {string} data
     * @return {TreeNode}
     */
    deserialize(data) {
        const values = data.split(',');
        let index = 0;
        
        function buildTree() {
            if (index >= values.length || values[index] === 'null') {
                index++;
                return null;
            }
            
            const node = new TreeNode(parseInt(values[index]));
            index++;
            
            node.left = buildTree();
            node.right = buildTree();
            
            return node;
        }
        
        return buildTree();
    }
}

/**
 * Alternative approach using level-order traversal
 */
class CodecLevelOrder {
    serialize(root) {
        if (!root) return '';
        
        const result = [];
        const queue = [root];
        
        while (queue.length > 0) {
            const node = queue.shift();
            
            if (node) {
                result.push(node.val.toString());
                queue.push(node.left);
                queue.push(node.right);
            } else {
                result.push('null');
            }
        }
        
        return result.join(',');
    }
    
    deserialize(data) {
        if (!data) return null;
        
        const values = data.split(',');
        const root = new TreeNode(parseInt(values[0]));
        const queue = [root];
        let index = 1;
        
        while (queue.length > 0 && index < values.length) {
            const node = queue.shift();
            
            // Left child
            if (values[index] !== 'null') {
                node.left = new TreeNode(parseInt(values[index]));
                queue.push(node.left);
            }
            index++;
            
            // Right child
            if (index < values.length && values[index] !== 'null') {
                node.right = new TreeNode(parseInt(values[index]));
                queue.push(node.right);
            }
            index++;
        }
        
        return root;
    }
}

// Example usage
const codec = new Codec();
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
const serialized = codec.serialize(root);
console.log('Serialized:', serialized);
const deserialized = codec.deserialize(serialized);

Python Solution

class Codec:
    """
    Serialize and Deserialize Binary Tree
    Time Complexity: O(n) for both operations
    Space Complexity: O(n) for both operations
    """
    
    def serialize(self, root):
        """Encodes a tree to a single string."""
        result = []
        
        def preorder(node):
            if not node:
                result.append('null')
                return
            
            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return ','.join(result)
    
    def deserialize(self, data):
        """Decodes your encoded data to tree."""
        values = data.split(',')
        self.index = 0
        
        def build_tree():
            if self.index >= len(values) or values[self.index] == 'null':
                self.index += 1
                return None
            
            node = TreeNode(int(values[self.index]))
            self.index += 1
            
            node.left = build_tree()
            node.right = build_tree()
            
            return node
        
        return build_tree()

class CodecLevelOrder:
    """Alternative approach using level-order traversal"""
    
    def serialize(self, root):
        if not root:
            return ''
        
        from collections import deque
        result = []
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append('null')
        
        return ','.join(result)
    
    def deserialize(self, data):
        if not data:
            return None
        
        from collections import deque
        values = data.split(',')
        root = TreeNode(int(values[0]))
        queue = deque([root])
        index = 1
        
        while queue and index < len(values):
            node = queue.popleft()
            
            # Left child
            if values[index] != 'null':
                node.left = TreeNode(int(values[index]))
                queue.append(node.left)
            index += 1
            
            # Right child
            if index < len(values) and values[index] != 'null':
                node.right = TreeNode(int(values[index]))
                queue.append(node.right)
            index += 1
        
        return root

# Example usage
codec = Codec()
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
serialized = codec.serialize(root)
print('Serialized:', serialized)
deserialized = codec.deserialize(serialized)

Frequently Asked Questions (FAQ)

Q1: How should I approach these problems during an interview?

A: Follow the UFCE approach:

Understand: Clarify the problem statement and constraints
Function signature: Discuss input/output format
Come up with examples: Walk through test cases
Explain: Your approach before coding

Q2: Should I memorize these solutions?

A: Focus on understanding the underlying patterns and techniques rather than memorizing. Practice implementing these solutions from scratch multiple times.

Q3: Which language should I use for interviews?

A: Use the language you're most comfortable with. Both JavaScript and Python are excellent choices for technical interviews due to their readability and extensive built-in functions.

Q4: How do I optimize my solutions?

A: Always consider:

Time complexity: Can you reduce the number of operations?
Space complexity: Can you use less memory?
Edge cases: Handle null inputs, empty arrays, etc.

Q5: What if I can't solve a problem completely?

A: Communicate your thought process clearly. Even a brute force solution shows problem-solving ability. Discuss potential optimizations and trade-offs.

Q6: How much should I practice these problems?

A: Aim to solve each problem at least 3-4 times without looking at the solution. Focus on understanding the pattern rather than memorizing the code.

Q7: Are there variations of these problems I should know?

A: Yes! For example:

Two Sum has variations like Three Sum, Four Sum
Binary Search has variations like Search in Rotated Array
Tree problems have many variations with different constraints

Q8: How do I handle follow-up questions?

A: Common follow-ups include:

"What if the input was much larger?"
"Can you optimize space complexity?"
"How would you handle invalid inputs?"

Always think about scalability and edge cases.

Top 10 DSA Problems Every Developer Must Master in 2025