Algos.Guru — LeetCode DSA Problem Solutions
A curated collection of 57 LeetCode-style problems with complete Java solutions, approach explanations, and time/space complexity analysis for FAANG coding interview preparation.
Difficulty Breakdown
- Easy: 19 problems
- Medium: 24 problems
- Hard: 13 problems
Algorithm Topics
Array, BFS, BFS/DFS, Backtracking, Binary Search, Bit Manipulation, Cyclic Sort, DFS, DFS/BFS, Design, Dynamic Programming, Graph, Hash Map, HashMap + Doubly Linked List, Heap, Heap / Priority Queue, Linked List, Math, Monotonic Deque, QuickSelect, Sliding Window, Stack, String, Topological Sort, Topological Sort (BFS / Kahn's Algorithm), Tree, Two Pointers
All Problems
- LC001: Two Sum (Easy) — Array, Hash Map
- Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution , and you may not use the same element twice. You can return the answer in any order. Approach: One-pass HashMap. Store complement (target - num) as we iterate. Time: O(n), Space: O(n)
- LC003: Longest Substring Without Repeating Characters (Medium) — Sliding Window, Hash Map
- Given a string s, find the length of the longest substring without repeating characters. Approach: Sliding window with char->index map. Time: O(n), Space: O(min(n, charset))
- LC004: Median of Two Sorted Arrays (Hard) — Binary Search
- Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)). Approach: Binary search on the shorter array to find the correct partition so that all elements on the left half ≤ all elements on the right half. Time: O(log(min(m,n))), Space: O(1)
- LC010: Regular Expression Matching (Hard) — Dynamic Programming, String
- Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Approach: DP - dp[i][j] = match s[0..i) with p[0..j). Time: O(m*n), Space: O(m*n)
- LC011: Container With Most Water (Medium) — Two Pointers, Array
- You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. Approach: Two pointers at ends; move the shorter inward. Time: O(n), Space: O(1)
- LC015: 3Sum (Medium) — Array, Two Pointers
- Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Approach: Sort + two pointers for each fixed first element. Time: O(n²), Space: O(1) excluding output
- LC016: 3Sum Closest (Medium) — Two Pointers, Array
- Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Approach: Sort + two pointers. Time: O(n²), Space: O(1)
- LC020: Valid Parentheses (Easy) — Stack, String
- Given a string s containing just the characters '(', ')', '{', '', '[' and ']', determine if the input string is valid. An input string is valid if: (1) Open brackets must be closed by the same type of brackets. (2) Open brackets must be closed in the correct order. (3) Every close bracket has a corresponding open bracket of the same type. Approach: Stack to match opening brackets. Time: O(n), Space: O(n)
- LC021: Merge Two Sorted Lists (Easy) — Linked List
- You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. Approach: Dummy node, compare and link. Time: O(m+n), Space: O(1)
- LC023: Merge K Sorted Lists (Hard) — Linked List, Heap
- You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Approach: Min-heap holding one node from each list. Poll the smallest, advance its pointer, push its next back into the heap. Time: O(N log k) where N = total nodes, Space: O(k)
- LC033: Search in Rotated Sorted Array (Medium) — Binary Search
- There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 ≤ k Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity. Approach: Binary search; one half is always sorted. Time: O(log n), Space: O(1)
- LC034: Find First and Last Position of Element in Sorted Array (Medium) — Binary Search
- Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. Approach: Two binary searches - one for left bound, one for right. Time: O(log n), Space: O(1)
- LC035: Search Insert Position (Easy) — Binary Search
- Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Approach: Binary search; return left when not found. Time: O(log n), Space: O(1)
- LC039: Combination Sum (Medium) — Backtracking
- Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times . Two combinations are unique if the frequency of at least one of the chosen numbers is different. Approach: Backtrack with start index to avoid duplicates. Time: O(2^target), Space: O(target)
- LC041: First Missing Positive (Hard) — Array, Cyclic Sort
- Given an unsorted integer array nums, return the smallest positive integer that is not present in nums. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space. Approach: Place each positive in its correct index (1 at 0, 2 at 1, ...). Time: O(n), Space: O(1)
- LC042: Trapping Rain Water (Hard) — Array, Two Pointers
- Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Each bar has width 1 and height given by the array. Approach: Two pointers; track maxLeft and maxRight. Time: O(n), Space: O(1)
- LC046: Permutations (Medium) — Backtracking
- Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Approach: Backtrack with swap. Time: O(n! * n), Space: O(n)
- LC049: Group Anagrams (Medium) — Hash Map, String
- Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once. Approach: Frequency array signature. For each word, build an int[26] character count and convert it to a string key. All anagrams produce the same key. O(n*k) instead of O(n*k log k) from sorting each word. Time: O(n * k), Space: O(n * k)
- LC053: Maximum Subarray (Kadane's Algorithm) (Easy) — Array, Dynamic Programming
- Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous part of an array. Approach: Kadane's - track current sum, reset if negative. Time: O(n), Space: O(1)
- LC070: Climbing Stairs (Easy) — Dynamic Programming
- You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Approach: Fibonacci-like DP. dp[i] = dp[i-1] + dp[i-2]. Time: O(n), Space: O(1)
- LC072: Edit Distance (Levenshtein) (Hard) — Dynamic Programming
- Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character, Delete a character, Replace a character. Approach: dp[i][j] = min edits for word1[0..i) to word2[0..j). Time: O(m*n), Space: O(m*n)
- LC076: Minimum Window Substring (Hard) — Sliding Window, Hash Map
- Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". Approach: Expand right pointer to satisfy the window, then shrink left pointer to minimise. Track how many characters of t are satisfied with a frequency map and a "formed" counter.
- LC084: Largest Rectangle in Histogram (Hard) — Stack, Array
- Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Approach: Monotonic increasing stack of indices. When a bar shorter than the stack top is encountered, pop and compute the area with the popped bar as the shortest bar in the range. Time: O(n), Space: O(n)
- LC098: Validate Binary Search Tree (Medium) — Tree, DFS
- Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: (1) The left subtree of a node contains only nodes with keys less than the node's key. (2) The right subtree of a node contains only nodes with keys greater than the node's key. (3) Both the left and right subtrees must also be binary search trees. Approach: DFS with min/max bounds. Time: O(n), Space: O(h)
- LC102: Binary Tree Level Order Traversal (Medium) — Tree, BFS
- Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Approach: BFS with queue. Time: O(n), Space: O(n)
- LC104: Maximum Depth of Binary Tree (Easy) — Tree, DFS
- Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Approach: Recursive DFS. Time: O(n), Space: O(h) - recursion stack
- LC121: Best Time to Buy and Sell Stock (Easy) — Dynamic Programming, Array
- You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Approach: Track min price seen, max profit = price - min. Time: O(n), Space: O(1)
- LC124: Binary Tree Maximum Path Sum (Hard) — Tree, DFS
- A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. Approach: DFS; return max path through node (single branch); track global max. Time: O(n), Space: O(h)
- LC125: Valid Palindrome (Easy) — Two Pointers, String
- A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise. Approach: Two pointers from both ends. Time: O(n), Space: O(1)
- LC127: Word Ladder () — Graph, BFS
- A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord → s₁ → s₂ → ... → sₖ such that: Every adjacent pair of words differs by a single letter. Every sᵢ for 1 ≤ i ≤ k is in wordList. Note that beginWord does not need to be in wordList. sₖ == endWord. Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists. Approach: BFS; try changing each char to 'a'-'z'. Time: O(M² * N) where M=word length, N=wordList size, Space: O(N)
- LC133: Clone Graph (Medium) — Graph, DFS/BFS
- Given a reference of a node in a connected undirected graph , return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list of its neighbors (List ). Approach: DFS with a visited map (original → clone). For each node, create its clone, then recursively clone each neighbor. Time: O(V + E), Space: O(V)
- LC136: Single Number (Easy) — Bit Manipulation
- Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space. Approach: XOR all numbers. a ^ a = 0, so pairs cancel; remaining is the answer. Time: O(n), Space: O(1)
- LC146: LRU Cache (Medium) — Design, HashMap + Doubly Linked List
- Design a data structure that follows the constraints of a Least Recently Used (LRU) cache . Implement the LRUCache class: * LRUCache(int capacity) — initialise with positive capacity. int get(int key) — return the value if the key exists, otherwise -1. void put(int key, int value) — update or insert. If capacity exceeded, evict the least recently used key before inserting. * Both operations must run in O(1) average time. Approach: HashMap for O(1) lookup + doubly-linked list for O(1) insertion/removal at head/tail. Most-recently-used nodes are moved to the head; eviction removes from the tail. Time: O(1) per operation, Space: O(capacity)
- LC155: Min Stack (Easy) — Stack, Design
- Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: * MinStack() - initializes the stack object void push(int val) - pushes val onto the stack void pop() - removes the element on the top int top() - gets the top element int getMin() - retrieves the minimum element in the stack * You must implement a solution with O(1) time complexity for each function. Approach: Two stacks - one for values, one for min at each level. Time: O(1) all ops, Space: O(n)
- LC191: Number of 1 Bits (Hamming Weight) (Easy) — Bit Manipulation
- Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. Approach: n & (n-1) clears lowest set bit. Time: O(k) k=number of 1 bits, Space: O(1)
- LC200: Number of Islands (Medium) — Graph, DFS/BFS
- Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water. Approach: DFS from each unvisited '1', mark visited. Time: O(m*n), Space: O(m*n) - recursion
- LC202: Happy Number (Easy) — Hash Map, Math
- Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Approach: Set to detect cycle. Time: O(log n), Space: O(log n)
- LC206: Reverse Linked List (Easy) — Linked List
- Given the head of a singly linked list, reverse the list, and return the reversed list . Approach: Iterative with prev/curr/next pointers. Time: O(n), Space: O(1)
- LC207: Course Schedule (Medium) — Graph, Topological Sort, DFS
- There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a. For example, [0, 1] means to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false. Approach: DFS cycle detection with 3-state coloring. Time: O(V+E), Space: O(V)
- LC210: Course Schedule II (Topological Sort) (Medium) — Graph, Topological Sort (BFS / Kahn's Algorithm)
- There are a total of numCourses courses you have to take, labeled 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b before course a. Return the ordering of courses you should take to finish all courses. If it is impossible, return an empty array. Approach: Kahn's algorithm — BFS with in-degree array. Enqueue all nodes with in-degree 0, then process each, decrementing neighbors' in-degrees. If all nodes are processed, return the order; otherwise a cycle exists. Time: O(V + E), Space: O(V + E)
- LC215: Kth Largest Element in an Array (Medium) — Heap, QuickSelect
- Given an integer array nums and an integer k, return the k-th largest element in the array. Note that it is the k-th largest element in the sorted order, not the k-th distinct element. Can you solve it without sorting? Approach: Min-heap of size k. Poll when size > k. Time: O(n log k), Space: O(k)
- LC226: Invert Binary Tree (Easy) — Tree, DFS
- Given the root of a binary tree, invert the tree, and return its root. To invert a binary tree: swap the left and right child of every node. Approach: Recursive swap. Time: O(n), Space: O(h)
- LC236: Lowest Common Ancestor of a Binary Tree (Medium) — Tree, DFS
- Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The LCA is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself). Approach: Post-order DFS. If current node is p or q, return it. Recurse left and right. If both sides return non-null, current node is the LCA. Otherwise propagate the non-null side. Time: O(n), Space: O(n) — recursion stack
- LC238: Product of Array Except Self (Medium) — Array
- Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. You must write an algorithm that runs in O(n) time and without using the division operation. Approach: Two passes - left products, then right products. Time: O(n), Space: O(1) excluding output
- LC239: Sliding Window Maximum (Hard) — Sliding Window, Monotonic Deque
- You are given an array of integers nums, there is a sliding window of size k which moves from the very left to the very right. You can only see the k numbers in the window. Each time the window moves right by one position. Return the max sliding window. Approach: Monotonic decreasing deque of indices. The front of the deque always holds the index of the current window maximum. Time: O(n), Space: O(k)
- LC242: Valid Anagram (Easy) — Hash Map, String
- Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. Approach: Count character frequencies in both strings. Time: O(n), Space: O(1) - fixed 26 chars
- LC269: Alien Dictionary (Premium) (Hard) — Graph, Topological Sort
- There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings are sorted lexicographically by the rules of this new language. Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them. Approach: Build graph from adjacent word pairs, topological sort. Time: O(C) total chars, Space: O(1)
- LC283: Move Zeroes (Easy) — Two Pointers, Array
- Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array. Approach: Two pointers - slow for write position, fast for scan. Time: O(n), Space: O(1)
- LC295: Find Median from Data Stream (Hard) — Heap / Priority Queue, Design
- The median is the middle value in an ordered integer list. If the size is even, the median is the mean of the two middle values. Implement the MedianFinder class: * MedianFinder() — initialises the object. void addNum(int num) — adds the integer to the data structure. double findMedian() — returns the median of all elements so far. Approach: Two heaps — a max-heap for the lower half and a min-heap for the upper half. Keep them balanced so the median is always available from the heap tops. Time: O(log n) addNum, O(1) findMedian, Space: O(n)
- LC297: Serialize and Deserialize Binary Tree (Hard) — Tree, BFS/DFS
- Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. Approach: BFS level-order with "null" for missing nodes. Time: O(n), Space: O(n)
- LC300: Longest Increasing Subsequence (Medium) — Dynamic Programming, Binary Search
- Given an integer array nums, return the length of the longest strictly increasing subsequence . A subsequence is derived by deleting some or no elements without changing the order of the remaining elements. Approach: DP - dp[i] = LIS ending at i. O(n²). Time: O(n²), Space: O(n)
- LC322: Coin Change (Medium) — Dynamic Programming
- You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Approach: dp[i] = min coins for amount i. dp[i] = 1 + min(dp[i-coin]). Time: O(amount * coins), Space: O(amount)
- LC344: Reverse String (Easy) — String, Two Pointers
- Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory. Approach: Two pointers swap from both ends. Time: O(n), Space: O(1)
- LC347: Top K Frequent Elements (Medium) — Heap, Hash Map
- Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. It is guaranteed that the answer is unique. Approach: Count frequencies, min-heap of size k. Time: O(n log k), Space: O(n)
- LC416: 0/1 Knapsack (Medium) — Dynamic Programming
- Given n items with weights weights[] and values values[], and a knapsack of capacity W, find the maximum value you can obtain by selecting items such that the total weight does not exceed the capacity. Each item can be used at most once (0/1 choice). Approach: dp[i][w] = max value using first i items with capacity w. Either skip item i or take it. Time: O(n * W), Space: O(W) with 1D optimization
- LC496: Next Greater Element (Medium) — Stack, Array
- Given an integer array arr, for each element find the first greater element to its right. The Next Greater Element (NGE) of an element x is the first element greater than x that appears to the right of x in the array. If no such element exists, the result is -1. Approach: Monotonic stack. Traverse right to left, maintaining a decreasing stack. Pop elements smaller than current — the stack top is the next greater element. Each element is pushed and popped at most once. Time: O(n), Space: O(n)
- LC704: Binary Search (Easy) — Binary Search
- Given an array of integers nums which is sorted in ascending order , and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. Approach: Classic binary search. Time: O(log n), Space: O(1)
About Algos.Guru
Each problem includes a clear problem statement, input/output examples, constraints, a step-by-step approach breakdown, and a complete Java solution with Big-O time and space complexity analysis. Problems are organized by difficulty (Easy, Medium, Hard) and by algorithm type to help you systematically build your skills.
Topics covered include Arrays, Hash Maps, Dynamic Programming, Binary Search, Sliding Window, BFS, DFS, Graphs, Trees, Linked Lists, Backtracking, Heaps, Tries, Stacks, Two Pointers, Bit Manipulation, Math, and Design patterns.