LeetCode Solutions

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. **Explanation:** The brute force approach would check every pair of numbers (O(n²)). A better approach uses a hash map to store numbers we've seen, allowing us to check if the complement (target - current number) exists in O(1) time. **Solution Approach:** 1. Create a hash map to store number -> index pairs 2. For each number, calculate its complement (target - number) 3. Check if complement exists in map 4. If yes, return [complement_index, current_index] 5. If no, add current number to map and continue

Given a string s, find the length of the longest substring without repeating characters.

Given a string s, return the longest palindromic substring in s.

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. **Explanation:** The area is determined by width (distance between lines) × height (minimum of two line heights). **Key Insight:** Start with widest container (left and right ends). To find a potentially larger area, move the pointer with shorter height inward. **Why move the shorter one?** If we move the taller one, width decreases and height can only stay same or decrease, so area decreases. Moving shorter one might find a taller line. **Brute Force (O(n²)):** Check all pairs of lines. **Optimized (O(n)):** Two pointers from both ends, greedily moving the shorter one.

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Given the head of a linked list, remove the nth node from the end of the list and return its head. **Explanation:** Use two pointers with n nodes gap between them. When fast reaches end, slow is at the node before the one to remove. **Key Trick:** Use a dummy node to handle edge case where we need to remove the head.

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. **Explanation:** This is a classic stack problem. When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check if the top of the stack has the matching opening bracket. If not, or if the stack is empty, the string is invalid. **Solution Approach:** 1. Use a stack to track opening brackets 2. For each character: - If opening bracket: push to stack - If closing bracket: check if stack top matches, then pop 3. At the end, stack should be empty (all brackets matched)

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. **Explanation:** Since both lists are already sorted, we can merge them in a single pass by comparing the current nodes of both lists and choosing the smaller one. We use a dummy node to simplify edge cases. **Solution Approach:** 1. Create a dummy node to serve as the head of the result list 2. Use a pointer to track the current position in the result list 3. While both lists have nodes: - Compare current nodes, attach the smaller one to result - Move pointer in the list we took from 4. After one list is exhausted, attach the remaining list 5. Return dummy.next (the actual start of merged list)

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. **Approaches:** 1. **Brute Force**: Merge lists one by one - O(kN) 2. **Divide & Conquer**: Pair up lists and merge - O(N log k) 3. **Min Heap**: Always pick smallest head - O(N log k)

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. 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 in nums. You must write an algorithm with O(log n) runtime complexity. **Explanation:** Even though the array is rotated, one half is always sorted. We can determine which half is sorted and check if target lies within that sorted half. **Key Insight:** 1. Find mid, determine which half is sorted 2. Check if target is in the sorted half 3. Narrow search accordingly **Brute Force (O(n)):** Linear search through the array. **Optimized (O(log n)):** Modified binary search checking which half is sorted.

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees clockwise. Rotate in-place (don't allocate another 2D matrix). **Key Insight:** Rotate 90° clockwise = Transpose + Reverse each row **Alternative:** Rotate 90° counterclockwise = Transpose + Reverse each column

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

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

Given an m x n matrix, return all elements of the matrix in spiral order. **Explanation:** Maintain four boundaries (top, bottom, left, right) and traverse: 1. Left to right along top row 2. Top to bottom along right column 3. Right to left along bottom row 4. Bottom to top along left column Shrink boundaries after each direction.

You are given an integer array nums. You are initially positioned at the array's first index. Each element represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. **Explanation:** Track the farthest index you can reach. At each position, update the maximum reachable index. **Key Insight:** If current index > max reachable, you're stuck. If max reachable >= last index, you can make it.

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals.

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] sorted by starti. Insert newInterval into intervals such that intervals is still sorted and non-overlapping (merge if necessary). **Explanation:** Three phases: 1. Add all intervals that end before new interval starts 2. Merge all overlapping intervals with new interval 3. Add all intervals that start after new interval ends

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner. How many possible unique paths are there? **Explanation:** To reach any cell, you can only come from above or from the left. dp[i][j] = dp[i-1][j] + dp[i][j-1] **Math Approach:** Total moves = (m-1) + (n-1) = m+n-2 We need to choose which (m-1) are "down" moves. Result = C(m+n-2, m-1)

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?

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. Do it in-place. **Approaches:** 1. Extra space O(m+n): Store which rows/cols have zeros 2. O(1) space: Use first row and first column as markers

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. **Explanation:** 1. Expand window until all characters of t are included 2. Contract from left to find minimum 3. Continue expanding/contracting Use two maps: one for required characters, one for current window.

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). Each cell can only be used once. **Explanation:** Use DFS/backtracking from each cell. Mark cells as visited during exploration, unmark when backtracking.

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26" Given a string s containing only digits, return the number of ways to decode it. **Explanation:** At each position, we can decode: 1. Single digit (if valid: 1-9) 2. Two digits (if valid: 10-26) **Key Edge Cases:** - '0' cannot be decoded alone - Leading zeros in two-digit numbers are invalid

Given the root of a binary tree, determine if it is a valid binary search tree (BST). **Key:** Each node must be within a valid range based on ancestors.

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. **Explanation:** We can recursively check if two trees are identical by comparing: 1. Both nodes are null (base case - identical) 2. One is null and other isn't (different) 3. Values are different (different) 4. Recursively check left and right subtrees **Solution Approach:** 1. Base case: if both nodes are null, return true 2. If only one is null, return false 3. If values differ, return false 4. Recursively check both left subtrees AND both right subtrees

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). **Explanation:** Use BFS with a queue. Process nodes level by level.

Given the root of a binary tree, return its maximum depth.

Given two integer arrays preorder and inorder, construct and return the binary tree. **Key Insight:** - Preorder: first element is root - Inorder: elements left of root are left subtree, right are right subtree Recursively build left and right subtrees.

You are given an array prices where prices[i] is the price of a given stock on the ith 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. **Explanation:** The key insight is that we want to buy at the lowest price and sell at the highest price AFTER that lowest price. We can do this in one pass: - Track the minimum price seen so far - For each price, calculate profit if we sold today - Keep track of maximum profit **Solution Approach:** 1. Initialize minPrice to infinity and maxProfit to 0 2. For each price: - If current price is lower than minPrice, update minPrice - Otherwise, calculate profit (current price - minPrice) - Update maxProfit if this profit is higher 3. Return maxProfit This works because we're always considering selling at the current price after buying at the lowest price we've seen so far.

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. Return the maximum path sum of any non-empty path. **Key Insight:** At each node, we can either: 1. Use it as part of a path going up to parent 2. Use it as the "root" of a path (left + node + right) Track global max while returning max path going up.

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.

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time. **Explanation:** Use a HashSet for O(1) lookups. For each number, only start counting if it's the beginning of a sequence (num - 1 doesn't exist). **Key Insight:** Don't start counting from middle of sequence. Only start when num - 1 is NOT in the set.

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 (List[Node]) of its neighbors. **Explanation:** Use DFS/BFS with a hash map to track visited nodes and their clones. For each node: 1. If already cloned, return the clone 2. Otherwise, create clone and recursively clone neighbors

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. **Explanation:** For each position in the string, check if we can reach it by taking a valid word from a previous valid position. **Brute Force (Recursive):** Try breaking at every position - exponential time. **Optimized (DP):** dp[i] = true if s[0..i-1] can be segmented For each position, check all possible words ending at that position.

Given head, the head of a linked list, determine if the linked list has a cycle in it.

You are given the head of a singly linked-list. Reorder the list to be: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... Do not modify values, only change pointers. **Explanation:** Three steps: 1. Find the middle using slow/fast pointers 2. Reverse the second half 3. Merge the two halves alternately

Given an integer array nums, find a subarray that has the largest product, and return the product. **Explanation:** The tricky part is handling negative numbers. A negative number can turn the largest product into the smallest, and vice versa. So we need to track both the maximum and minimum products at each position. **Brute Force Approach (O(n²)):** Check every possible subarray and calculate their products. **Optimized Approach (O(n)):** Track both maxProduct and minProduct at each position because: - A negative number * minProduct could become maxProduct - A negative number * maxProduct could become minProduct **Solution Approach:** 1. Track currentMax and currentMin at each position 2. For each number, consider three options: - Start fresh with current number - Extend previous max (currentMax * num) - Extend previous min (currentMin * num) 3. Update global maximum

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time. **Explanation:** The array is sorted but rotated at some pivot. The minimum element is at the rotation point. We can use binary search because one half is always sorted. **Key Insight:** - If nums[mid] > nums[right], minimum is in right half - Otherwise, minimum is in left half (including mid) **Brute Force (O(n)):** Simply scan through array to find minimum. **Optimized (O(log n)):** Binary search to find the rotation point.

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 the element val onto the stack - void pop() removes the element on the top of the stack - int top() gets the top element of the stack - int getMin() retrieves the minimum element in the stack **Key Insight:** The challenge is getMin() in O(1). We can't just track a single min value because when we pop, the min might change. **Solution:** Use two stacks - one for values, one for tracking minimums at each state.

Reverse bits of a given 32 bits unsigned integer. **Explanation:** We need to reverse the bit order of a 32-bit integer. We can do this by iterating through all 32 bits, extracting each bit from the right side of the input, and adding it to the left side of the result. **Solution Approach:** 1. Initialize result to 0 2. For each of 32 bits: - Shift result left by 1 (make room for new bit) - Extract rightmost bit of n (n & 1) - Add it to result - Shift n right by 1 (move to next bit) 3. Use >>> for unsigned right shift

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight). **Explanation:** We need to count how many '1' bits are in the binary representation. We can use bit manipulation to check each bit or use Brian Kernighan's algorithm which repeatedly clears the rightmost set bit. **Solution Approach (Brian Kernighan's Algorithm):** 1. While n is not 0: - Increment count - Clear the rightmost set bit: n = n & (n - 1) 2. Return count Why this works: n & (n - 1) always clears the rightmost 1 bit Example: 12 (1100) & 11 (1011) = 8 (1000)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. Adjacent houses have security systems connected - if two adjacent houses are broken into on the same night, the police will be alerted. Given an integer array nums representing the amount of money at each house, return the maximum amount you can rob without alerting police. **Explanation:** At each house, you have two choices: 1. Rob it (can't rob previous house) 2. Skip it (can rob previous house) **Recurrence:** dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - Skip this house: dp[i-1] - Rob this house: dp[i-2] + nums[i]

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.

Given the head of a singly linked list, reverse the list, and return the reversed list.

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return true if you can finish all courses, otherwise return false. **Explanation:** This is cycle detection in a directed graph. If there's a cycle, you can't complete all courses. **Approaches:** 1. DFS with 3 states: unvisited, visiting (in current path), visited 2. BFS (Kahn's algorithm) with topological sort

Implement a trie with insert, search, and startsWith methods.

Design a data structure that supports adding words and searching with '.' wildcard.

Given a board and list of words, find all words that exist in the grid. **Key:** Build Trie from words, then DFS from each cell while traversing Trie.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. Adjacent houses have security systems connected - police will be alerted if two adjacent houses are broken into the same night. **Key Insight:** Since houses are in a circle, first and last houses are adjacent. So you can either: 1. Rob houses 0 to n-2 (exclude last) 2. Rob houses 1 to n-1 (exclude first) Take the maximum of these two scenarios.

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. **Explanation:** We need to detect if any number appears more than once. Using a Set is ideal because: - Sets only store unique values - Checking if a value exists in a Set is O(1) - We can iterate once through the array **Solution Approach:** 1. Create an empty Set to track seen numbers 2. For each number in the array: - If number is already in Set, return true (duplicate found) - Otherwise, add number to Set 3. If we finish the loop, return false (no duplicates) **Alternative approaches:** - Sort array and check adjacent elements: O(n log n) time, O(1) space - Use hash map to count frequencies: O(n) time, O(n) space

Given the root of a binary tree, invert the tree, and return its root.

Given the root of a BST and integer k, return the kth smallest value. **Key:** Inorder traversal of BST gives sorted order.

Find the lowest common ancestor (LCA) of two nodes in a BST. **Key Insight:** Use BST property - if both nodes are smaller, go left; if both larger, go right; otherwise current node is LCA.

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].

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. **Explanation:** A person can attend all meetings only if no two meetings overlap. To check for overlaps efficiently: 1. Sort meetings by start time 2. Check if any meeting starts before the previous one ends **Solution Approach:** 1. Sort intervals by start time 2. Iterate through sorted intervals 3. For each interval (except first): - If current start < previous end, meetings overlap → return false 4. If no overlaps found, return true **Example:** intervals = [[0,30],[5,10],[15,20]] After sorting by start: [[0,30],[5,10],[15,20]] - Meeting 2 starts at 5, but meeting 1 ends at 30 → overlap! - Return false

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required. **Explanation:** We need to find the maximum number of overlapping meetings at any point. **Approach 1 (Chronological Events):** Treat starts and ends as separate events. Sort them. When a meeting starts, add a room. When one ends, free a room. **Approach 2 (Min Heap):** Sort by start time. Use min-heap to track earliest ending meeting. If new meeting starts after earliest ends, reuse room.

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array. **Explanation:** There are several approaches: 1. **Math approach**: Sum of 0 to n is n*(n+1)/2. Subtract all array elements from this sum. 2. **XOR approach**: XOR of a number with itself is 0. XOR all numbers 0 to n with all array elements; duplicates cancel out, leaving the missing number. **Solution Approach (Math):** 1. Calculate expected sum: n * (n + 1) / 2 2. Calculate actual sum of array elements 3. Return expected - actual **Alternative (XOR):** XOR all indices 0 to n and all array values. The missing number remains.

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list. **Explanation:** Use length-prefix encoding: "length#string" Example: ["hello", "world"] → "5#hello5#world" This handles any characters including '#' and numbers in the original strings.

Design a data structure that supports adding integers and finding the median. **Key Insight:** Use two heaps: - Max heap for lower half (gives us largest of lower half) - Min heap for upper half (gives us smallest of upper half) Keep them balanced (differ by at most 1 in size). Median is either top of larger heap, or average of both tops.

Design an algorithm to serialize and deserialize a binary tree. **Explanation:** Use preorder traversal. Mark null nodes with a special character. Split by delimiter for deserialization.

Given an integer array nums, return the length of the longest strictly increasing subsequence. **Explanation:** A subsequence is derived by deleting some or no elements without changing the order of remaining elements. **Brute Force (O(n²) DP):** For each element, look at all previous elements and extend the longest subsequence that ends with a smaller value. **Optimized (O(n log n) with Binary Search):** Maintain a "tails" array where tails[i] = smallest ending element of all increasing subsequences of length i+1. Use binary search to find where each element fits.

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. **Explanation:** This is a classic unbounded knapsack problem. For each amount, we try using each coin and take the minimum. **Brute Force (Recursion):** Try all combinations recursively - exponential time. **Optimized (DP):** dp[i] = minimum coins needed to make amount i For each amount, try each coin: dp[i] = min(dp[i], dp[i-coin] + 1)

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i. **Explanation:** We could solve each number independently using problem 191, but there's a clever DP approach. Notice that: - For even numbers: countBits(i) = countBits(i / 2) - For odd numbers: countBits(i) = countBits(i / 2) + 1 This is because dividing by 2 (i >> 1) just removes the rightmost bit. **Solution Approach:** 1. Create result array of size n + 1 2. result[0] = 0 (zero has no 1 bits) 3. For each i from 1 to n: - result[i] = result[i >> 1] + (i & 1) - i >> 1 is i divided by 2 - i & 1 checks if i is odd (adds 1 if true)

Given two integers a and b, return the sum of the two integers without using the operators + and -. **Explanation:** We can add numbers using bit manipulation: 1. XOR (^) gives us the sum without carrying: 1^1=0, 1^0=1, 0^0=0 2. AND (&) gives us the carry bits: only 1&1=1 needs to carry 3. Shift carry left by 1 (carry goes to next position) 4. Repeat until no more carry **Example: 2 + 3** - 2 = 010, 3 = 011 - XOR: 010 ^ 011 = 001 (sum without carry) - AND: 010 & 011 = 010 (carry positions) - Shift carry: 010 << 1 = 100 - Now add 001 + 100: - XOR: 001 ^ 100 = 101 (5) - AND: 001 & 100 = 000 (no carry, we're done!) - Result: 5

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. Note: Different orderings of numbers count as different combinations. **Explanation:** This is similar to Coin Change but we count permutations (order matters), not combinations. **Key Difference from Coin Change:** - Coin Change: [1,2] and [2,1] are the same - This problem: [1,2] and [2,1] are different **Solution:** dp[i] = number of ways to make amount i For each target, try all nums as the last element.

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. Water can flow from a cell to an adjacent cell (up/down/left/right) if the adjacent cell's height is less than or equal to the current cell's height. Return a list of cells from which water can flow to both the Pacific and Atlantic oceans. **Explanation:** Instead of checking from each cell if it can reach both oceans (expensive), work backwards: 1. Find all cells that can reach Pacific (start from Pacific edges) 2. Find all cells that can reach Atlantic (start from Atlantic edges) 3. Return intersection

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter after performing the above operations. **Key Insight:** For a window to be valid: (window length) - (count of most frequent char) <= k This means we can replace all non-majority characters with at most k operations.

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest non-overlapping. **Explanation:** This is equivalent to finding maximum non-overlapping intervals (like activity selection). **Greedy Approach:** Sort by end time. For each interval, if it doesn't overlap with previous selected interval, keep it. Otherwise, remove it. **Key Insight:** Sorting by END time is crucial. We want intervals that end early to leave more room for future intervals.

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree is a tree that consists of a node in tree and all of this node's descendants. The tree could also be considered as a subtree of itself. **Explanation:** We need to check if subRoot matches any subtree in root. We can traverse root and at each node, check if the tree starting at that node is identical to subRoot (using the Same Tree logic). **Solution Approach:** 1. Helper function to check if two trees are identical (same as Problem 100) 2. For each node in root: - Check if subtree starting here matches subRoot - If not, recursively check left and right subtrees 3. Return true if any subtree matches

Given a string s, return the number of palindromic substrings in it. **Explanation:** Use expand around center technique. For each position, try both odd-length (single center) and even-length (two centers) palindromes.

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order. **Explanation:** Classic 2D DP problem. Compare characters at each position of both strings. **Recurrence:** - If chars match: dp[i][j] = dp[i-1][j-1] + 1 - If not: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) **Brute Force (Recursive):** Try all subsequences - exponential time. **Optimized (2D DP):** Build table bottom-up comparing all character pairs.