DSA in Python
63 questionsCoding patterns that actually show up in DE interviews — two pointers, sliding window, binary search, trees, graphs. Each problem includes solution, follow-ups, and DE relevance.
Dutch National Flag Problem
Given an array containing only 0s, 1s, and 2s, sort it in-place in a single pass. Example: Input: [2, 0, 1, 2, 1, 0] Output: [0, 0, 1, 1, 2, 2] Constraints: O(n) time, O(1) space, single pass.
Remove Duplicates from Sorted Array
Given a sorted array, remove duplicates in-place and return the new length. The first k elements should contain the unique values. Example: Input: [1, 1, 2, 2, 3, 4, 4, 5] Output: 5 (array becomes [1, 2, 3, 4, 5, ...]) Constraints: O(1) extra space.
Container With Most Water
Given n non-negative integers representing heights of vertical lines, find two lines that together with the x-axis form a container that holds the most water. Example: Input: [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 (lines at index 1 and 8, height=min(8,7)=7, width=7) Constraints: O(n) time.
Merge Two Sorted Arrays In-Place
Given two sorted arrays nums1 (size m+n, with n zeros at end) and nums2 (size n), merge nums2 into nums1 in sorted order, in-place. Example: Input: nums1 = [1, 3, 5, 0, 0, 0], m = 3 nums2 = [2, 4, 6], n = 3 Output: [1, 2, 3, 4, 5, 6] Constraints: O(m+n) time, O(1) space.
Sliding Window Maximum
Given an array of integers and a window size k, return the maximum element in each sliding window. Example: Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Output: [3, 3, 5, 5, 6, 7] Constraints: O(n) time.
Longest Substring Without Repeating Characters
Find the length of the longest substring without repeating characters. Example: Input: "abcabcbb" Output: 3 ("abc") Input: "bbbbb" Output: 1 ("b") Input: "pwwkew" Output: 3 ("wke")
Minimum Window Substring
Given strings s and t, find the minimum window in s that contains all characters of t (including duplicates). Example: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Input: s = "a", t = "aa" Output: "" (not enough 'a's) Constraints: O(m + n) time.
Max Sum Subarray of Size K
Given an array and integer k, find the maximum sum of any contiguous subarray of size k. Example: Input: nums = [2, 1, 5, 1, 3, 2], k = 3 Output: 9 (subarray [5, 1, 3])
First and Last Occurrence in Sorted Array
Given a sorted array and a target, find the first and last index where target appears. Return [-1, -1] if not found. Example: Input: nums = [1, 2, 2, 2, 3, 4, 5], target = 2 Output: [1, 3] Constraints: O(log n) time.
Search in Rotated Sorted Array
A sorted array is rotated at some pivot. Given a target, return its index or -1. Example: Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: 4 Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Output: -1 Constraints: O(log n) time. No duplicates.
Find Peak Element
An element is a peak if it's strictly greater than its neighbors. Find any peak element's index. Assume nums[-1] = nums[n] = -∞. Example: Input: [1, 2, 3, 1] Output: 2 (nums[2] = 3) Input: [1, 2, 1, 3, 5, 6, 4] Output: 5 (or 1 — any peak is valid) Constraints: O(log n) time.
Koko Eating Bananas (Binary Search on Answer)
Koko has n piles of bananas. She can eat at speed k bananas/hour (one pile per hour, even if pile < k). Guards return in h hours. Find the minimum k so she finishes all piles in h hours. Example: Input: piles = [3, 6, 7, 11], h = 8 Output: 4 Explanation: At speed 4: pile 3 → 1 hour, pile 6 → 2 hours, pile 7 → 2 hours, pile 11 → 3 hours Total = 8 hours ✓
Two Sum
Given an array and a target sum, return indices of two numbers that add up to target. Exactly one solution exists. Example: Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] (2 + 7 = 9)
Group Anagrams
Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
Subarray Sum Equals K
Given an array and integer k, find the total number of contiguous subarrays whose sum equals k. Example: Input: nums = [1, 1, 1], k = 2 Output: 2 ([1,1] starting at index 0 and 1) Input: nums = [1, 2, 3], k = 3 Output: 2 ([1,2] and [3]) Note: Array can contain negative numbers.
First Non-Repeating Character
Given a string, find the index of the first non-repeating character. Return -1 if none. Example: Input: "leetcode" Output: 0 ('l') Input: "aabb" Output: -1
Valid Parentheses
Given a string containing '(', ')', '{', '}', '[', ']', determine if it's valid. Every open bracket must close in the correct order. Example: Input: "()[]{}" → true Input: "(]" → false Input: "([)]" → false Input: "{[]}" → true
Next Greater Element
Given an array, for each element find the next greater element to its right. Return -1 if none exists. Example: Input: [4, 5, 2, 25] Output: [5, 25, 25, -1] Input: [13, 7, 6, 12] Output: [-1, 12, 12, -1] Constraints: O(n) time.
Min Stack
Design a stack that supports push, pop, top, and getMin — all in O(1) time. Example: push(-2), push(0), push(-3) getMin() → -3 pop() top() → 0 getMin() → -2
Daily Temperatures
Given daily temperatures, return an array where answer[i] = number of days until a warmer temperature. If no warmer day exists, answer[i] = 0. Example: Input: [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0]
Merge Intervals
Given a collection of intervals, merge all overlapping intervals. Example: Input: [[1,3], [2,6], [8,10], [15,18]] Output: [[1,6], [8,10], [15,18]] Input: [[1,4], [4,5]] Output: [[1,5]]
Sort by Custom Key (Sort Colors variant)
Given a list of log entries with format "id:timestamp:level", sort them by: 1. Level priority: ERROR > WARN > INFO 2. Within same level, by timestamp (ascending) Example: Input: ["a1:1000:INFO", "b2:900:ERROR", "c3:950:WARN", "d4:800:ERROR"] Output: ["d4:800:ERROR", "b2:900:ERROR", "c3:950:WARN", "a1:1000:INFO"]
Top K Frequent Elements
Given an array and integer k, return the k most frequent elements. Example: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1, 2] Constraints: Better than O(n log n).
Sort Characters by Frequency
Sort a string in decreasing order of character frequency. Example: Input: "tree" Output: "eert" (or "eetr") Input: "cccaaa" Output: "aaaccc" (or "cccaaa")
Merge K Sorted Lists
Merge k sorted linked lists into one sorted list. Example: Input: [[1,4,5], [1,3,4], [2,6]] Output: [1, 1, 2, 3, 4, 4, 5, 6] Constraints: Optimal time complexity.
Find Median from Data Stream
Design a data structure that supports: - addNum(num) — add integer from stream - findMedian() — return median of all elements so far Example: addNum(1), addNum(2) → median = 1.5 addNum(3) → median = 2
Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Example: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 Note: kth largest, not kth distinct.
Reorganize String (No Two Adjacent Same)
Rearrange a string so no two adjacent characters are the same. Return "" if impossible. Example: Input: "aab" Output: "aba" Input: "aaab" Output: "" (impossible)
Detect Cycle in Linked List
Given head of a linked list, determine if it has a cycle. Follow-up: Find the node where the cycle begins.
Reverse a Linked List
Reverse a singly linked list. Do it both iteratively and recursively. Example: Input: 1 → 2 → 3 → 4 → 5 Output: 5 → 4 → 3 → 2 → 1
LRU Cache
Design a data structure for Least Recently Used (LRU) Cache: - get(key): Return value if key exists, else -1. Marks as recently used. - put(key, value): Insert or update. If at capacity, evict the least recently used item. Both operations must be O(1).
Level Order Traversal (BFS)
Given the root of a binary tree, return level order traversal (values grouped by level). Example: 3 / \ 9 20 / \ 15 7 Output: [[3], [9, 20], [15, 7]]
Validate Binary Search Tree
Determine if a binary tree is a valid BST. A valid BST has: - Left subtree values < node value - Right subtree values > node value - Both subtrees are also valid BSTs Example: 5 / \ 1 7 → True / \ 6 8 5 / \ 1 4 → False (4 < 5 but in right subtree)
Topological Sort (Course Schedule)
There are n courses (0 to n-1). Some have prerequisites: [a, b] means you must take b before a. Return a valid order to take all courses, or empty array if impossible. Example: Input: n = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]] Output: [0, 1, 2, 3] or [0, 2, 1, 3] Input: n = 2, prerequisites = [[0,1], [1,0]] Output: [] (cycle — impossible)
Number of Islands
Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically. Example: Input: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Output: 3
Serialize and Deserialize Binary Tree
Design an algorithm to serialize a binary tree to a string and deserialize it back. Example: 1 / \ 2 3 / \ 4 5 serialize → "1,2,#,#,3,4,#,#,5,#,#" deserialize → original tree
Climbing Stairs
You can climb 1 or 2 steps at a time. How many distinct ways to reach the top of n stairs? Example: n = 3 → 3 ways: (1+1+1), (1+2), (2+1) n = 5 → 8 ways
Coin Change
Given coin denominations and a target amount, find the minimum number of coins needed. Return -1 if not possible. Example: Input: coins = [1, 5, 10, 25], amount = 30 Output: 2 (25 + 5) Input: coins = [2], amount = 3 Output: -1
Longest Common Subsequence
Find the length of the longest common subsequence (LCS) of two strings. Example: Input: "abcde", "ace" Output: 3 ("ace") Input: "abc", "def" Output: 0
House Robber
You're a robber. Each house has money. You can't rob two adjacent houses. Find the maximum you can rob. Example: Input: [2, 7, 9, 3, 1] Output: 12 (2 + 9 + 1) Input: [1, 2, 3, 1] Output: 4 (1 + 3)
Edit Distance
Given two strings, find the minimum number of operations (insert, delete, replace) to convert word1 to word2. Example: Input: word1 = "horse", word2 = "ros" Output: 3 (horse → rorse → ros → ros... actually: horse→rorse→rose→ros)
Jump Game
Given an array where each element is the max jump length from that position, determine if you can reach the last index. Example: Input: [2, 3, 1, 1, 4] → true (2→3→4 or various paths) Input: [3, 2, 1, 0, 4] → false (stuck at index 3)
Generate Parentheses
Generate all combinations of n pairs of well-formed parentheses. Example: n = 3 → ["((()))", "(()())", "(())()", "()(())", "()()()"]
Subsets (Power Set)
Given an array of unique integers, return all possible subsets. Example: Input: [1, 2, 3] Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
Partition Labels
Partition a string into as many parts as possible so that each letter appears in at most one part. Return the sizes. Example: Input: "ababcbacadefegdehijhklij" Output: [9, 7, 8] Explanation: "ababcbaca" | "defegde" | "hijhklij" Each letter appears in exactly one partition.
Longest Palindromic Substring
Find the longest palindromic substring. Example: Input: "babad" Output: "bab" (or "aba") Input: "cbbd" Output: "bb"
String Compression
Compress a string in-place: consecutive duplicates become char + count. If count is 1, don't add it. Return the new length. Example: Input: ['a','a','b','b','c','c','c'] Output: 6, chars = ['a','2','b','2','c','3'] Input: ['a','b','c'] Output: 3, chars = ['a','b','c']
Product of Array Except Self
Given an array, return an array where each element is the product of all other elements. No division allowed. Example: Input: [1, 2, 3, 4] Output: [24, 12, 8, 6] Constraints: O(n) time, no division.
Trapping Rain Water
Given elevation map (array of non-negative integers), compute how much water it can trap. Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Spiral Order Matrix
Return all elements of an m×n matrix in spiral order. Example: Input: [[1,2,3], [4,5,6], [7,8,9]] Output: [1,2,3,6,9,8,7,4,5]
Rotate Image (Matrix 90°)
Rotate an n×n matrix 90 degrees clockwise in-place. Example: Input: [[1,2,3], Output: [[7,4,1], [4,5,6], [8,5,2], [7,8,9]] [9,6,3]]
Search in Sorted 2D Matrix
Search for a value in an m×n matrix where: - Each row is sorted left to right - First integer of each row > last integer of previous row Example: Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: True
Single Number
Every element appears twice except one. Find the single one. Example: Input: [4, 1, 2, 1, 2] Output: 4 Constraints: O(n) time, O(1) space.
Count Set Bits (Hamming Weight)
Count the number of 1-bits in an integer's binary representation. Example: Input: 11 (binary: 1011) Output: 3 Input: 128 (binary: 10000000) Output: 1
Power of Two
Determine if an integer is a power of two. Example: Input: 16 → true (2⁴) Input: 6 → false Input: 1 → true (2⁰)
Insert Interval
Given a sorted list of non-overlapping intervals and a new interval, insert it and merge if necessary. Example: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]]
Meeting Rooms II (Minimum Rooms)
Given an array of meeting time intervals [start, end], find the minimum number of conference rooms required. Example: Input: [[0,30], [5,10], [15,20]] Output: 2 Input: [[7,10], [2,4]] Output: 1
Range Sum Query (Prefix Sum Array)
Given an array, answer multiple queries for the sum of elements between indices i and j (inclusive) efficiently. Example: nums = [-2, 0, 3, -5, 2, -1] query(0, 2) → 1 (-2+0+3) query(2, 5) → -1 (3-5+2-1) query(0, 5) → -3
Subarray Sum Divisible by K
Given an array of integers and an integer k, find the number of contiguous subarrays whose sum is divisible by k. Example: Input: nums = [4, 5, 0, -2, -3, 1], k = 5 Output: 7 ([4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3])
Implement Iterator for Nested List
Implement an iterator to flatten a nested list of integers. Each element is either an integer or a list (which may also contain integers or other lists). Example: Input: [[1,1],2,[1,1]] next() → 1, 1, 2, 1, 1 Input: [1,[4,[6]]] next() → 1, 4, 6
Rate Limiter (Fixed Window)
Design a rate limiter that allows at most k requests per second for each user. is_allowed("user1") → True (first request) is_allowed("user1") → True (second, if within limit) is_allowed("user1") → False (exceeded k requests in this second)
Implement Trie (Prefix Tree)
Implement a Trie with: - insert(word) — inserts a word - search(word) — returns true if word exists - startsWith(prefix) — returns true if any word starts with prefix Example: insert("apple") search("apple") → true search("app") → false startsWith("app") → true
Design HashMap
Design a HashMap without using built-in hash table libraries. Implement: - put(key, value) - get(key) → value or -1 - remove(key)