100 Data Structures and Algorithms (DSA) Coding Problems

Arrays and Strings

1. Two Sum

Problem: Given an array of integers and a target sum, return the indices of two numbers that add up to the target.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] (because nums[0] + nums[1] = 2 + 7 = 9)

Solution:

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Time Complexity: O(n), Space Complexity: O(n)

2. Maximum Subarray

Problem: Find the contiguous subarray with the largest sum.

Example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (subarray [4, -1, 2, 1])

Solution:

def max_subarray(nums):
    max_so_far = nums[0]
    current_max = nums[0]
    
    for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        max_so_far = max(max_so_far, current_max)
    
    return max_so_far

Time Complexity: O(n), Space Complexity: O(1)

3. Container With Most Water

Problem: Given n non-negative integers representing heights of lines, find two lines that together with the x-axis forms a container that holds the most water.

Example:

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49 (between heights 8 and 7)

Solution:

def max_area(height):
    max_water = 0
    left = 0
    right = len(height) - 1
    
    while left < right:
        width = right - left
        max_water = max(max_water, min(height[left], height[right]) * width)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

Time Complexity: O(n), Space Complexity: O(1)

4. Valid Anagram

Problem: Given two strings, determine if the second is an anagram of the first.

Example:

Input: s = "anagram", t = "nagaram"
Output: true

Solution:

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    
    char_count = {}
    
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    for char in t:
        if char not in char_count or char_count[char] == 0:
            return False
        char_count[char] -= 1
    
    return True

Time Complexity: O(n), Space Complexity: O(1) - Since we have a fixed character set

5. Rotate Array

Problem: Rotate an array to the right by k steps.

Example:

Input: [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

Solution:

def rotate(nums, k):
    n = len(nums)
    k %= n  # In case k > n
    
    # Reverse the entire array
    reverse(nums, 0, n - 1)
    # Reverse the first k elements
    reverse(nums, 0, k - 1)
    # Reverse the remaining elements
    reverse(nums, k, n - 1)
    
def reverse(nums, start, end):
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1

Time Complexity: O(n), Space Complexity: O(1)

Linked Lists

6. Reverse Linked List

Problem: Reverse a singly linked list.

Example:

Input: 1->2->3->4->5
Output: 5->4->3->2->1

Solution:

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

def reverse_list(head):
    prev = None
    current = head
    
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    
    return prev

Time Complexity: O(n), Space Complexity: O(1)

7. Detect Cycle in Linked List

Problem: Given a linked list, determine if it has a cycle.

Solution:

def has_cycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

Time Complexity: O(n), Space Complexity: O(1)

8. Merge Two Sorted Lists

Problem: Merge two sorted linked lists into one sorted list.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution:

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # Attach remaining nodes
    current.next = l1 if l1 else l2
    
    return dummy.next

Time Complexity: O(n+m), Space Complexity: O(1)

9. Remove Nth Node From End

Problem: Remove the nth node from the end of a linked list and return its head.

Example:

Input: 1->2->3->4->5, n = 2
Output: 1->2->3->5

Solution:

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    
    # Advance first pointer by n+1 steps
    for i in range(n + 1):
        first = first.next
    
    # Move both pointers until first reaches the end
    while first:
        first = first.next
        second = second.next
    
    # Remove the nth node
    second.next = second.next.next
    
    return dummy.next

Time Complexity: O(n), Space Complexity: O(1)

10. Palindrome Linked List

Problem: Determine if a linked list is a palindrome.

Example:

Input: 1->2->2->1
Output: true

Solution:

def is_palindrome(head):
    if not head or not head.next:
        return True
    
    # Find the middle of the linked list
    slow = head
    fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse the second half
    second_half = reverse_list(slow.next)
    
    # Compare first and second half
    first_half = head
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next
    
    return True

Time Complexity: O(n), Space Complexity: O(1)

Additional Problems

These are just the first 10 DSA problems. The same pattern continues for more advanced topics including:

Each problem includes a clear description, examples where applicable, and optimized solutions with time and space complexity analysis.