SDE Sheet

1. Prefix Sum

Problem 1: (Leetcode:)

Problem Statement

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

Problem 1: Subarray Sum Equals K (Leetcode:560)

Problem Statement

Code and Explaination

Approach 1Approach 2

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    sum_freq = {0: 1}  # prefix sum 0 occurs once

    for num in nums:
        prefix_sum += num

        if prefix_sum - k in sum_freq:
            count += sum_freq[prefix_sum - k]

        sum_freq[prefix_sum] = sum_freq.get(prefix_sum, 0) + 1

    return count

Explaination:
This is first approach

Explaination:
This is second approach

2. Two Pointers

Problem 1: Best time to buy and sell stock(Leetcode:121)

Problem Statement

Code and Explaination

Approach 1Approach 2Approach 3Approach 4Approach 5

def maxProfit(prices):
    max_profit = 0
    n = len(prices)
    for i in range(n):  # buy day
        for j in range(i + 1, n):  # sell day
            profit = prices[j] - prices[i]
            max_profit = max(max_profit, profit)
    return max_profit

Explaination:
This is Brute Force approach

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)           # best buy so far
        max_profit = max(max_profit, price - min_price)  # max profit so far

    return max_profit

Explaination:
This is One-Pass (Optimal) approach

def maxProfit(prices):
    n = len(prices)
    min_prices = [0] * n
    min_prices[0] = prices[0]

    for i in range(1, n):
        min_prices[i] = min(min_prices[i - 1], prices[i])

    max_profit = 0
    for i in range(1, n):
        profit = prices[i] - min_prices[i - 1]
        max_profit = max(max_profit, profit)

    return max_profit

Explaination:
This is Prefix Min Array approach

def maxProfit(prices):
    left = 0  # buy
    right = 1  # sell
    max_profit = 0

    while right < len(prices):
        if prices[right] > prices[left]:
            profit = prices[right] - prices[left]
            max_profit = max(max_profit, profit)
        else:
            left = right
        right += 1

    return max_profit

Explaination:
This is Sliding Window (Two Pointers) approach

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0

    dp = [0] * n
    min_price = prices[0]

    for i in range(1, n):
        min_price = min(min_price, prices[i])
        dp[i] = max(dp[i - 1], prices[i] - min_price)

    return dp[-1]

Explaination:
This is Dynamic Programming approach

Problem 2: Longest Substring Without Repeating Characters(Leetcode: 3)

Problem Statement

Code and Explaination

Approach 1

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}
    start = 0
    max_len = 0

    for end in range(len(s)):
        if s[end] in char_index and char_index[s[end]] >= start:
            start = char_index[s[end]] + 1
        char_index[s[end]] = end
        max_len = max(max_len, end - start + 1)

    return max_len

Explaination:
This is first approach

Problem 3: Rotate Array(Leetcode: 189)

Problem Statement

Code and Explaination

Approach 1

def rotate(nums, k):
    n = len(nums)
    k %= n  # Handle k > n

    def reverse(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    reverse(0, n - 1)        # Step 1: Reverse entire array
    reverse(0, k - 1)        # Step 2: Reverse first k elements
    reverse(k, n - 1)        # Step 3: Reverse rest

Explaination:
This is first approach

Problem 4: Three Sum (Leetcode:15)

Problem Statement

Code and Explaination

Approach 1

def threeSum(nums):
    nums.sort()
    res = []

    for i in range(len(nums) - 2):
        # Skip duplicates for i
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]

            if curr_sum == 0:
                res.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for left and right
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1

            elif curr_sum < 0:
                left += 1
            else:
                right -= 1

    return res

Explaination:
This is first approach

Problem 5: Container With Most Water(Leetcode:11)

Problem Statement

Code and Explaination

Approach 1

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        h = min(height[left], height[right])
        w = right - left
        max_area = max(max_area, h * w)

        # Move the shorter pointer inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

Explaination:
This is both two pointer and greedy approach

3. Fast and Slow Pointers

4. Sliding Window

5. Overlapping Intervals

Problem 1: Merge Intervals(Leetcode:56)

Problem Statement

Code and Explaination

Approach 1

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        # Step 1: Sort intervals by start time
        intervals.sort(key=lambda x: x[0])
        merged = []

        # Step 2: Merge overlapping intervals
        for interval in intervals:
            # If merged is empty or no overlap, append
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # Overlap: update the end of the last interval
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

Explaination:
This is first approach

6. Cyclic Sort

7. Bit Manipulation

8. Linked List

Problem 1: Reverse Linked List (Leetcode:206)

Problem Statement

Code and Explaination

Approach 1Approach 2Approach 3Approach 4

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next      # Store next
        curr.next = prev           # Reverse current node's pointer
        prev = curr                # Move prev to curr
        curr = next_node           # Move curr to next
    return prev

Explaination:
This is iterative approach (Most Optimal)

def reverseList(head):
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

Explaination:
This is recursion approach

def reverseList(head):
    if not head:
        return None

    stack = []

    while head:
        stack.append(head)
        head = head.next

    new_head = stack.pop()
    curr = new_head
    while stack:
        curr.next = stack.pop()
        curr = curr.next
    curr.next = None
    return new_head

Explaination:
This is stack based approach

def reverseList(head):
    def reverse(prev, curr):
        if not curr:
            return prev
        next_node = curr.next
        curr.next = prev
        return reverse(curr, next_node)
    return reverse(None, head)

Explaination:
This is using tail recursion(optimized recursion) approach

Problem 2: Merge Two Sorted Lists (Leetcode:21)

Problem Statement

Code and Explaination

Approach 1Approach 2Approach 3Approach 4

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

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    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

    current.next = list1 or list2  # Append remaining nodes
    return dummy.next

Explaination:
This is dummy node approach

def mergeTwoLists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1

    if list1.val < list2.val:
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    else:
        list2.next = mergeTwoLists(list1, list2.next)
        return list2

Explaination:
This is Recursive approach

def mergeTwoLists(list1, list2):
    values = []
    while list1:
        values.append(list1.val)
        list1 = list1.next
    while list2:
        values.append(list2.val)
        list2 = list2.next

    values.sort()

    dummy = ListNode()
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next

    return dummy.next

Explaination:
Convert to Array → Sort → Rebuild Linked List

def mergeTwoLists(list1, list2):
    if not list1 or (list2 and list1.val > list2.val):
        list1, list2 = list2, list1
    head = list1

    while list1 and list2:
        tmp = None
        while list1 and list1.val <= list2.val:
            tmp = list1
            list1 = list1.next
        tmp.next = list2
        list1, list2 = list2, list1
    return head

Explaination:
In-Place Merge without Dummy Node

9. Stack

Problem 1: Valid Parentheses(Leetcode:20)

Problem Statement

Code and Explaination

Approach 1

def isValid(s):
    stack = []
    pair = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in pair:
            if not stack or stack[-1] != pair[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

Explaination:
This is first approach

10. Binary Search

Problem 1: Longest Common Prefix(Leetcode:14)

Problem Statement

Code and Explaination

Approach 1Approach 2Approach 3Approach 4Approach 5

def longestCommonPrefix(strs):
    if not strs:
        return ""

    for i in range(len(strs[0])):  # iterate over characters of the first string
        for s in strs[1:]:
            if i >= len(s) or s[i] != strs[0][i]:
                return strs[0][:i]
    return strs[0]

Explaination:
This is Vertical Scanning approach

def longestCommonPrefix(strs):
    if not strs:
        return ""

    prefix = strs[0]

    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

Explaination:
This is Horizontal Scanning approach

def longestCommonPrefix(strs):
    def lcp(start, end):
        if start == end:
            return strs[start]
        mid = (start + end) // 2
        lcpLeft = lcp(start, mid)
        lcpRight = lcp(mid + 1, end)
        return commonPrefix(lcpLeft, lcpRight)

    def commonPrefix(left, right):
        min_len = min(len(left), len(right))
        for i in range(min_len):
            if left[i] != right[i]:
                return left[:i]
        return left[:min_len]

    if not strs:
        return ""
    return lcp(0, len(strs) - 1)

Explaination:
This is Divide and Conquer approach

def longestCommonPrefix(strs):
    def isCommonPrefix(length):
        prefix = strs[0][:length]
        return all(s.startswith(prefix) for s in strs)

    if not strs:
        return ""

    min_len = min(len(s) for s in strs)
    low, high = 0, min_len

    while low <= high:
        mid = (low + high) // 2
        if isCommonPrefix(mid):
            low = mid + 1
        else:
            high = mid - 1

    return strs[0][: (low + high) // 2]

Explaination:
This is Binary Search on Prefix Length approach

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""

        root = TrieNode()

        # Build Trie
        for word in strs:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                node.count += 1

        # Traverse Trie
        prefix = ""
        node = root
        for char in strs[0]:
            if char in node.children and node.children[char].count == len(strs):
                prefix += char
                node = node.children[char]
            else:
                break
        return prefix

Explaination:
This is trie based approach

Problem 2: Search in a rotated sorted array(Leetcode:33)

Problem Statement

Code and Explaination

Approach 1

def search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Determine which half is sorted
        if nums[left] <= nums[mid]:  # Left half is sorted
            if nums[left] <= target < nums[mid]:  # Target in left half
                right = mid - 1
            else:  # Target in right half
                left = mid + 1
        else:  # Right half is sorted
            if nums[mid] < target <= nums[right]:  # Target in right half
                left = mid + 1
            else:  # Target in left half
                right = mid - 1

    return -1

Explaination:
This is first approach

Problem 3: Koko eating bananas(Leetcode:875)

Problem Statement

Code and Explaination

Approach 1

import math

def minEatingSpeed(piles, h):
    left, right = 1, max(piles)  # min speed = 1, max = largest pile

    def canFinish(k):
        hours = 0
        for pile in piles:
            hours += math.ceil(pile / k)
        return hours <= h

    while left < right:
        mid = (left + right) // 2
        if canFinish(mid):
            right = mid  # try a smaller k
        else:
            left = mid + 1  # need to eat faster

    return left

Explaination:
This is first approach

11. Greedy Algorithm

Problem 1: Best Time to Buy and Sell Stock II (Leetcode:122)

Problem Statement

Code and Explaination

Approach 1

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

Explaination:
This is first approach

12. Divide and Conquer

13. Backtracking

14. Dynamic Programming

Problem 1: Fibonacci Number(Leetcode:509)

Problem Statement

Code and Explaination

Approach 1Approach 2Approach 3Approach 4

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Explaination:
This is Recursive approach

def fib(n, memo = {}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Explaination:
This is Top-Down DP (Memoization) approach

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Explaination:
This is Bottom-Up DP (Tabulation) approach

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Explaination:
This is Space Optimized DP approach

Problem 2: Climbing Stairs (Leetcode:70)

Problem Statement

Code and Explaination

Approach 1Approach 2Approach 3Approach 4

def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

Explaination:
This is Recursive (Naive) approach

def climbStairs(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return n
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
    return memo[n]

Explaination:
This is Top-Down DP (Memoization) approach

def climbStairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Explaination:
This is Bottom-Up DP (Tabulation) approach

def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Explaination:
This is Space Optimized DP approach

Problem 3: Word Break(Leetcode:139)

Problem Statement

Code and Explaination

Approach 1

def wordBreak(s, wordDict):
    word_set = set(wordDict)  # For O(1) lookups
    dp = [False] * (len(s) + 1)
    dp[0] = True  # Empty string is always "breakable"

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # No need to check further

    return dp[-1]

Explaination:
This is first approach

Problem 4: Maximum Subarray(Leetcode:53)

Problem Statement

Code and Explaination

Approach 1

def maxSubArray(nums):
    max_sum = nums[0]
    curr_sum = nums[0]

    for i in range(1, len(nums)):
        # Either extend the current subarray or start a new one at nums[i]
        curr_sum = max(nums[i], curr_sum + nums[i])
        max_sum = max(max_sum, curr_sum)

    return max_sum

Explaination:
This is first approach

Problem 5: Longest Palindromic substring(Leetcode:5)

Problem Statement

Code and Explaination

Approach 1Approach 2

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1

    # All substrings of length 1 are palindromes
    for i in range(n):
        dp[i][i] = True

    # Check substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start = i
            max_len = 2

    # Check substrings of length 3 and more
    for length in range(3, n + 1):  # length of the substring
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if length > max_len:
                    start = i
                    max_len = length

    return s[start:start + max_len]

Explaination:
This is first approach

def longestPalindrome(s: str) -> str:
    if not s or len(s) == 1:
        return s

    start = 0
    end = 0

    def expand_around_center(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for i in range(len(s)):
        # Odd-length palindrome
        l1, r1 = expand_around_center(i, i)
        # Even-length palindrome
        l2, r2 = expand_around_center(i, i + 1)

        # Update longest
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2

    return s[start:end+1]

Explaination:
This is second approach

Problem 6: Longest Increasing Subsequence(Leetcode:300)

Problem Statement

Code and Explaination

Approach 1

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n  # At least each number itself

    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:  # Can extend LIS ending at j
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Explaination:
This is first approach

15. K-way Merge

16. HashMap

Problem 1: Two Sum(Leetcode:1)

Problem Statement

Code and Explaination

Approach 1Approach 2Approach 3

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return [i, j]

Explaination:
This is first approach

def twoSum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        num_map[num] = i
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map and num_map[complement] != i:
            return [i, num_map[complement]]

Explaination:
This is second approach

def twoSum(nums, target):
    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

Problem 2: Group Anagrams(Leetcode:49)

Problem Statement

Code and Explaination

Approach 1

from collections import defaultdict

def groupAnagrams(strs):
    anagram_map = defaultdict(list)

    for word in strs:
        # Build frequency count tuple of 26 letters (assuming lowercase a-z)
        count = [0] * 26
        for char in word:
            count[ord(char) - ord('a')] += 1
        key = tuple(count)  # Immutable and hashable
        anagram_map[key].append(word)

    return list(anagram_map.values())

Explaination:
This is first approach

17. Heaps

18. Tree

Problem 1: Lowest Common Ancestor of a binary tree(Leetcode:236)

Problem Statement

Code and Explaination

Approach 1

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root  # p and q found in different subtrees
        return left if left else right  # return the non-null side

Explaination:
This is first approach

19. Graph

Problem 1: Number of islands(Leetcode:200)

Problem Statement

Code and Explaination

Approach 1

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        count = 0

        def dfs(r, c):
            # Base case: out of bounds or water
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
                return

            # Mark the cell as visited by sinking the land
            grid[r][c] = '0'

            # Visit all four directions
            dfs(r+1, c)
            dfs(r-1, c)
            dfs(r, c+1)
            dfs(r, c-1)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)

        return count

Explaination:
This is first approach

Problem 2: Course Schedule(Leetcode:207)

Problem Statement

Code and Explaination

Approach 1

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    # Build graph and in-degree array
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    # Initialize queue with all courses having in-degree 0 (no prerequisites)
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    completed_courses = 0

    while queue:
        course = queue.popleft()
        completed_courses += 1
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1  # remove dependency
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If all courses are completed, return True
    return completed_courses == numCourses

Explaination:
This is first approach

20. Segment Tree

21. Tries

22. String Matching

23. miscellaneous