Table of contents

Open Table of contents

Array / String

88. Merge Sorted Array

Difficulty: Easy · Tags: Array, Two Pointers, Sorting

Leetcode

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -10^9 <= nums1[i], nums2[j] <= 10^9

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Approach

Two pointers from the back. Fill nums1 from index m+n-1 downward, taking the larger of nums1[i] and nums2[j]. Works in-place in O(m+n).

class Solution:
    def merge(self, nums1, m, nums2, n):
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]; i -= 1
            else:
                nums1[k] = nums2[j]; j -= 1
            k -= 1

27. Remove Element

Difficulty: Easy · Tags: Array, Two Pointers

Leetcode

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
  • Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100
Approach

Two pointers. k tracks write position; iterate i, copying any value != val to nums[k].

class Solution:
    def removeElement(self, nums, val):
        k = 0
        for x in nums:
            if x != val:
                nums[k] = x; k += 1
        return k

26. Remove Duplicates from Sorted Array

Difficulty: Easy · Tags: Array, Two Pointers

Leetcode

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Consider the number of unique elements in nums to be k​​​​​​​​​​​​​​. After removing duplicates, return the number of unique elements k.

The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k - 1 can be ignored.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.
Approach

Slow/fast pointers. k=1; for each i, if nums[i] != nums[k-1] write it at nums[k] and advance.

class Solution:
    def removeDuplicates(self, nums):
        k = 0
        for x in nums:
            if k == 0 or x != nums[k-1]:
                nums[k] = x; k += 1
        return k

80. Remove Duplicates from Sorted Array II

Difficulty: Medium · Tags: Array, Two Pointers

Leetcode

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in non-decreasing order.
Approach

Same pattern; allow each value at most twice: compare with nums[k-2] instead of nums[k-1].

class Solution:
    def removeDuplicates(self, nums):
        k = 0
        for x in nums:
            if k < 2 or x != nums[k-2]:
                nums[k] = x; k += 1
        return k

169. Majority Element

Difficulty: Easy · Tags: Array, Hash Table, Divide and Conquer, Sorting, Counting

Leetcode

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • The input is generated such that a majority element will exist in the array.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Approach

Boyer–Moore voting: maintain a candidate and count; reset candidate when count hits 0. Majority element survives.

class Solution:
    def majorityElement(self, nums):
        cand = count = 0
        for x in nums:
            if count == 0: cand = x
            count += 1 if x == cand else -1
        return cand

189. Rotate Array

Difficulty: Medium · Tags: Array, Math, Two Pointers

Leetcode

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^5

Follow up:

  • Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?
Approach

Reverse the whole array, then reverse the first k and the last n-k. In-place O(n), O(1) space.

class Solution:
    def rotate(self, nums, k):
        n = len(nums); k %= n
        nums.reverse()
        nums[:k] = reversed(nums[:k])
        nums[k:] = reversed(nums[k:])

121. Best Time to Buy and Sell Stock

Difficulty: Easy · Tags: Array, Dynamic Programming

Leetcode

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.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4
Approach

Track the minimum price seen so far; max profit = current price − min so far.

class Solution:
    def maxProfit(self, prices):
        lo = float('inf'); best = 0
        for p in prices:
            lo = min(lo, p); best = max(best, p - lo)
        return best

122. Best Time to Buy and Sell Stock II

Difficulty: Medium · Tags: Array, Dynamic Programming, Greedy

Leetcode

You are given an integer array prices where prices[i] is the price of a given stock on the i^th day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

  • 1 <= prices.length <= 3 * 10^4
  • 0 <= prices[i] <= 10^4
Approach

Unlimited transactions: sum every positive day-to-day delta — equivalent to capturing every upswing.

class Solution:
    def maxProfit(self, prices):
        return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))

55. Jump Game

Difficulty: Medium · Tags: Array, Dynamic Programming, Greedy

Leetcode

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5
Approach

Greedy: track the furthest index reachable. If i ever exceeds it, return False. Otherwise update reach with i + nums[i].

class Solution:
    def canJump(self, nums):
        reach = 0
        for i, x in enumerate(nums):
            if i > reach: return False
            reach = max(reach, i + x)
        return True

45. Jump Game II

Difficulty: Medium · Tags: Array, Dynamic Programming, Greedy

Leetcode

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It’s guaranteed that you can reach nums[n - 1].
Approach

BFS-like greedy. Maintain end of current jump and farthest reachable in this layer. When i == end, take a jump and set end = farthest.

class Solution:
    def jump(self, nums):
        jumps = end = farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == end:
                jumps += 1; end = farthest
        return jumps

274. H-Index

Difficulty: Medium · Tags: Array, Sorting, Counting Sort

Leetcode

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i^th paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1

Constraints:

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000
Approach

Counting sort by citation count, capped at n. Sweep from high to low accumulating papers; first i with count >= i is the h-index.

class Solution:
    def hIndex(self, citations):
        n = len(citations); buckets = [0]*(n+1)
        for c in citations:
            buckets[min(c, n)] += 1
        total = 0
        for i in range(n, -1, -1):
            total += buckets[i]
            if total >= i: return i
        return 0

380. Insert Delete GetRandom O(1)

Difficulty: Medium · Tags: Array, Hash Table, Math, Design, Randomized

Leetcode

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * ``10^5 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.
Approach

Hashmap value→index + dynamic array. On remove, swap target with last element to keep array dense; update the map.

import random
class RandomizedSet:
    def __init__(self):
        self.a = []; self.idx = {}
    def insert(self, val):
        if val in self.idx: return False
        self.idx[val] = len(self.a); self.a.append(val); return True
    def remove(self, val):
        if val not in self.idx: return False
        i = self.idx.pop(val); last = self.a.pop()
        if i < len(self.a):
            self.a[i] = last; self.idx[last] = i
        return True
    def getRandom(self):
        return random.choice(self.a)

238. Product of Array Except Self

Difficulty: Medium · Tags: Array, Prefix Sum

Leetcode

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

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Approach

Two passes. First pass: ans[i] = product of everything left of i. Second pass (right→left): multiply by running product from the right.

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums); ans = [1]*n
        left = 1
        for i in range(n):
            ans[i] = left; left *= nums[i]
        right = 1
        for i in range(n-1, -1, -1):
            ans[i] *= right; right *= nums[i]
        return ans

134. Gas Station

Difficulty: Medium · Tags: Array, Greedy

Leetcode

There are n gas stations along a circular route, where the amount of gas at the i^th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th station to its next (i + 1)^th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

  • n == gas.length == cost.length
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
  • The input is generated such that the answer is unique.
Approach

If total gas ≥ total cost, a solution exists. Sweep once: when running tank goes negative, restart from the next station.

class Solution:
    def canCompleteCircuit(self, gas, cost):
        if sum(gas) < sum(cost): return -1
        tank = start = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:
                start = i + 1; tank = 0
        return start

135. Candy

Difficulty: Hard · Tags: Array, Greedy

Leetcode

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

  • n == ratings.length
  • 1 <= n <= 2 * 10^4
  • 0 <= ratings[i] <= 2 * 10^4
Approach

Two passes. Left→right: if ratings[i] > ratings[i-1], give one more. Right→left: enforce same rule from the other side via max.

class Solution:
    def candy(self, ratings):
        n = len(ratings); c = [1]*n
        for i in range(1, n):
            if ratings[i] > ratings[i-1]: c[i] = c[i-1] + 1
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]: c[i] = max(c[i], c[i+1] + 1)
        return sum(c)

42. Trapping Rain Water

Difficulty: Hard · Tags: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

Leetcode

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5
Approach

Two pointers with running leftMax, rightMax. The shorter side determines how much water sits above the current bar.

class Solution:
    def trap(self, height):
        l, r = 0, len(height)-1; lm = rm = ans = 0
        while l < r:
            if height[l] < height[r]:
                lm = max(lm, height[l]); ans += lm - height[l]; l += 1
            else:
                rm = max(rm, height[r]); ans += rm - height[r]; r -= 1
        return ans

13. Roman to Integer

Difficulty: Easy · Tags: Hash Table, Math, String

Leetcode

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

  • 1 <= s.length <= 15
  • s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].
Approach

Scan left to right. If the current symbol is smaller than the next, subtract it; otherwise add.

class Solution:
    def romanToInt(self, s):
        v = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        total = 0
        for i, ch in enumerate(s):
            if i+1 < len(s) and v[ch] < v[s[i+1]]:
                total -= v[ch]
            else:
                total += v[ch]
        return total

12. Integer to Roman

Difficulty: Medium · Tags: Hash Table, Math, String

Leetcode

Seven different symbols represent Roman numerals with the following values:

        Symbol
        Value




        I
        1


        V
        5


        X
        10


        L
        50


        C
        100


        D
        500


        M
        1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

  • If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
  • If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
  • Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 3749

Output: “MMMDCCXLIX”

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: “LVIII”

Explanation:

50 = L
 8 = VIII

Example 3:

Input: num = 1994

Output: “MCMXCIV”

Explanation:

1000 = M
 900 = CM
  90 = XC
   4 = IV

Constraints:

  • 1 <= num <= 3999
Approach

Greedy with a value/symbol table including the subtractive pairs (900, 400, 90, 40, 9, 4). Subtract repeatedly.

class Solution:
    def intToRoman(self, num):
        pairs = [(1000,'M'),(900,'CM'),(500,'D'),(400,'CD'),
                 (100,'C'),(90,'XC'),(50,'L'),(40,'XL'),
                 (10,'X'),(9,'IX'),(5,'V'),(4,'IV'),(1,'I')]
        out = []
        for v, sym in pairs:
            while num >= v: out.append(sym); num -= v
        return ''.join(out)

58. Length of Last Word

Difficulty: Easy · Tags: String

Leetcode

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of only English letters and spaces ' '.
  • There will be at least one word in s.
Approach

Walk from the end, skip trailing spaces, then count non-space chars.

class Solution:
    def lengthOfLastWord(self, s):
        i = len(s) - 1
        while i >= 0 and s[i] == ' ': i -= 1
        j = i
        while j >= 0 and s[j] != ' ': j -= 1
        return i - j

14. Longest Common Prefix

Difficulty: Easy · Tags: Array, String, Trie

Leetcode

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters if it is non-empty.
Approach

Compare characters column-by-column across all strings; stop at first mismatch or end of shortest.

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs: return ""
        for i, ch in enumerate(strs[0]):
            for s in strs[1:]:
                if i >= len(s) or s[i] != ch: return strs[0][:i]
        return strs[0]

151. Reverse Words in a String

Difficulty: Medium · Tags: Two Pointers, String

Leetcode

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

  • 1 <= s.length <= 10^4
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '.
  • There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1)` extra space?

Approach

split() already collapses whitespace; reverse the list and join with single spaces.

class Solution:
    def reverseWords(self, s):
        return ' '.join(reversed(s.split()))

6. Zigzag Conversion

Difficulty: Medium · Tags: String

Leetcode

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000
Approach

Maintain numRows buckets; walk chars while bouncing direction at top/bottom rows. Concatenate buckets.

class Solution:
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s): return s
        rows = [[] for _ in range(numRows)]
        r, step = 0, 1
        for ch in s:
            rows[r].append(ch)
            if r == 0: step = 1
            elif r == numRows - 1: step = -1
            r += step
        return ''.join(''.join(row) for row in rows)

28. Find the Index of the First Occurrence in a String

Difficulty: Easy · Tags: Two Pointers, String, String Matching

Leetcode

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

  • 1 <= haystack.length, needle.length <= 10^4
  • haystack and needle consist of only lowercase English characters.
Approach

Built-in str.find is acceptable. For the canonical approach use KMP; here we keep it simple.

class Solution:
    def strStr(self, haystack, needle):
        return haystack.find(needle)

68. Text Justification

Difficulty: Hard · Tags: Array, String, Simulation

Leetcode

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Note:

  • A word is defined as a character sequence consisting of non-space characters only.
  • Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
  • The input array words contains at least one word.

Example 1:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Example 2:

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Explanation: Note that the last line is "shall be    " instead of "shall     be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.

Example 3:

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

Constraints:

  • 1 <= words.length <= 300
  • 1 <= words[i].length <= 20
  • words[i] consists of only English letters and symbols.
  • 1 <= maxWidth <= 100
  • words[i].length <= maxWidth
Approach

Greedy line packing. For each line, distribute extra spaces as evenly as possible, with leftover going to leftmost gaps. Last line is left-justified.

class Solution:
    def fullJustify(self, words, maxWidth):
        res, i, n = [], 0, len(words)
        while i < n:
            j, length = i, 0
            while j < n and length + len(words[j]) + (j - i) <= maxWidth:
                length += len(words[j]); j += 1
            gaps = j - i - 1
            if j == n or gaps == 0:
                line = ' '.join(words[i:j])
                line += ' ' * (maxWidth - len(line))
            else:
                spaces = maxWidth - length
                base, extra = divmod(spaces, gaps)
                parts = []
                for k in range(i, j-1):
                    parts.append(words[k])
                    parts.append(' ' * (base + (1 if k - i < extra else 0)))
                parts.append(words[j-1])
                line = ''.join(parts)
            res.append(line); i = j
        return res

Two Pointers

125. Valid Palindrome

Difficulty: Easy · Tags: Two Pointers, String

Leetcode

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.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.
Approach

Two pointers from both ends; skip non-alphanumerics; compare lowercase.

class Solution:
    def isPalindrome(self, s):
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum(): l += 1
            while l < r and not s[r].isalnum(): r -= 1
            if s[l].lower() != s[r].lower(): return False
            l += 1; r -= 1
        return True

392. Is Subsequence

Difficulty: Easy · Tags: Two Pointers, String, Dynamic Programming

Leetcode

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s_1, s_2, ..., s_k where k >= 10^9, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Approach

Two pointers. Advance i over s only when characters match; advance j over t always.

class Solution:
    def isSubsequence(self, s, t):
        i = 0
        for ch in t:
            if i < len(s) and s[i] == ch: i += 1
        return i == len(s)

167. Two Sum II - Input Array Is Sorted

Difficulty: Medium · Tags: Array, Two Pointers, Binary Search

Leetcode

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index_1] and numbers[index_2] where 1 <= index_1 < index_2 <= numbers.length.

Return the indices of the two numbers index_1 and index_2, each incremented by one, as an integer array [index_1, index_2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index_1 = 1, index_2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index_1 = 1, index_2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index_1 = 1, index_2 = 2. We return [1, 2].

Constraints:

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.
Approach

Two pointers in a sorted array: shrink right if sum too big, advance left if too small.

class Solution:
    def twoSum(self, numbers, target):
        l, r = 0, len(numbers) - 1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target: return [l+1, r+1]
            if s < target: l += 1
            else: r -= 1

11. Container With Most Water

Difficulty: Medium · Tags: Array, Two Pointers, Greedy

Leetcode

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, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4
Approach

Two pointers; area = min(h[l], h[r]) * (r - l). Move the shorter side inward — only that can yield a taller min.

class Solution:
    def maxArea(self, height):
        l, r = 0, len(height) - 1; best = 0
        while l < r:
            best = max(best, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]: l += 1
            else: r -= 1
        return best

15. 3Sum

Difficulty: Medium · Tags: Array, Two Pointers, Sorting

Leetcode

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.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5
Approach

Sort, fix i, then two-pointer the rest looking for sum -nums[i]. Skip duplicates at each level.

class Solution:
    def threeSum(self, nums):
        nums.sort(); res = []
        for i in range(len(nums)-2):
            if nums[i] > 0: break
            if i and nums[i] == nums[i-1]: continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0: l += 1
                elif s > 0: r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
        return res

Sliding Window

209. Minimum Size Subarray Sum

Difficulty: Medium · Tags: Array, Binary Search, Sliding Window, Prefix Sum

Leetcode

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Approach

Expand right pointer, accumulating sum; while sum ≥ target, shrink left and record min length.

class Solution:
    def minSubArrayLen(self, target, nums):
        l = s = 0; best = float('inf')
        for r, x in enumerate(nums):
            s += x
            while s >= target:
                best = min(best, r - l + 1); s -= nums[l]; l += 1
        return 0 if best == float('inf') else best

3. Longest Substring Without Repeating Characters

Difficulty: Medium · Tags: Hash Table, String, Sliding Window

Leetcode

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that `"bca"` and `"cab"` are also correct answers.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces.
Approach

Sliding window with last-seen index map. When we revisit a char inside the window, jump l past its previous index.

class Solution:
    def lengthOfLongestSubstring(self, s):
        last = {}; l = best = 0
        for r, ch in enumerate(s):
            if ch in last and last[ch] >= l: l = last[ch] + 1
            last[ch] = r; best = max(best, r - l + 1)
        return best

30. Substring with Concatenation of All Words

Difficulty: Hard · Tags: Hash Table, String, Sliding Window

Leetcode

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

  • For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,“bar”]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.

The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Example 2:

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]

Output: []

Explanation:

There is no concatenated substring.

Example 3:

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]

Output: [6,9,12]

Explanation:

The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].

The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].

The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

Constraints:

  • 1 <= s.length <= 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s and words[i] consist of lowercase English letters.
Approach

All words are equal length w. For each offset 0..w-1, slide a window of len(words) words, maintaining a counter; record indices when counter matches the target multiset.

from collections import Counter
class Solution:
    def findSubstring(self, s, words):
        if not words: return []
        w, k = len(words[0]), len(words)
        need = Counter(words); span = w * k; res = []
        for off in range(w):
            l = off; have = Counter(); count = 0
            for r in range(off, len(s) - w + 1, w):
                word = s[r:r+w]
                if word not in need:
                    have.clear(); count = 0; l = r + w; continue
                have[word] += 1; count += 1
                while have[word] > need[word]:
                    have[s[l:l+w]] -= 1; count -= 1; l += w
                if count == k: res.append(l)
        return res

76. Minimum Window Substring

Difficulty: Hard · Tags: Hash Table, String, Sliding Window

Leetcode

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

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Approach

Sliding window with character need-count and a formed counter. Expand right; when all chars satisfied, shrink left and track best window.

from collections import Counter
class Solution:
    def minWindow(self, s, t):
        if not t or len(s) < len(t): return ""
        need = Counter(t); missing = len(t)
        l = 0; best = (float('inf'), 0, 0)
        for r, ch in enumerate(s):
            if need[ch] > 0: missing -= 1
            need[ch] -= 1
            while missing == 0:
                if r - l < best[0]: best = (r - l, l, r)
                need[s[l]] += 1
                if need[s[l]] > 0: missing += 1
                l += 1
        return "" if best[0] == float('inf') else s[best[1]:best[2]+1]

Matrix

36. Valid Sudoku

Difficulty: Medium · Tags: Array, Hash Table, Matrix

Leetcode

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  • Each row must contain the digits 1-9 without repetition.
  • Each column must contain the digits 1-9 without repetition.
  • Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'.
Approach

Track sets for each row, column, and 3×3 box. Reject on duplicate insertion.

class Solution:
    def isValidSudoku(self, board):
        rows=[set() for _ in range(9)]; cols=[set() for _ in range(9)]; boxes=[set() for _ in range(9)]
        for r in range(9):
            for c in range(9):
                v = board[r][c]
                if v == '.': continue
                b = (r//3)*3 + c//3
                if v in rows[r] or v in cols[c] or v in boxes[b]: return False
                rows[r].add(v); cols[c].add(v); boxes[b].add(v)
        return True

54. Spiral Matrix

Difficulty: Medium · Tags: Array, Matrix, Simulation

Leetcode

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100
Approach

Maintain four boundaries (top, bottom, left, right) and shrink them after each side is consumed.

class Solution:
    def spiralOrder(self, matrix):
        res = []; t, b = 0, len(matrix)-1; l, r = 0, len(matrix[0])-1
        while t <= b and l <= r:
            for c in range(l, r+1): res.append(matrix[t][c])
            t += 1
            for rr in range(t, b+1): res.append(matrix[rr][r])
            r -= 1
            if t <= b:
                for c in range(r, l-1, -1): res.append(matrix[b][c])
                b -= 1
            if l <= r:
                for rr in range(b, t-1, -1): res.append(matrix[rr][l])
                l += 1
        return res

48. Rotate Image

Difficulty: Medium · Tags: Array, Math, Matrix

Leetcode

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000
Approach

Transpose, then reverse each row. Yields a 90° clockwise rotation in-place.

class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for row in matrix:
            row.reverse()

73. Set Matrix Zeroes

Difficulty: Medium · Tags: Array, Hash Table, Matrix

Leetcode

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

Follow up:

  • A straightforward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?
Approach

Use the first row & column as markers. Track separately whether row 0 / col 0 themselves must be zeroed.

class Solution:
    def setZeroes(self, m):
        rows, cols = len(m), len(m[0])
        first_row = any(m[0][c] == 0 for c in range(cols))
        first_col = any(m[r][0] == 0 for r in range(rows))
        for r in range(1, rows):
            for c in range(1, cols):
                if m[r][c] == 0:
                    m[r][0] = 0; m[0][c] = 0
        for r in range(1, rows):
            for c in range(1, cols):
                if m[r][0] == 0 or m[0][c] == 0: m[r][c] = 0
        if first_row:
            for c in range(cols): m[0][c] = 0
        if first_col:
            for r in range(rows): m[r][0] = 0

289. Game of Life

Difficulty: Medium · Tags: Array, Matrix, Simulation

Leetcode

According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  • Any live cell with fewer than two live neighbors dies as if caused by under-population.
  • Any live cell with two or three live neighbors lives on to the next generation.
  • Any live cell with more than three live neighbors dies, as if by over-population.
  • Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously.

Given the current state of the board, update the board to reflect its next state.

Note that you do not need to return anything.

Example 1:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 25
  • board[i][j] is 0 or 1.

Follow up:

  • Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
  • In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?
Approach

Encode old+new state in two bits: bit 0 = old, bit 1 = new. Compute new state from neighbors’ old bits, then shift down.

class Solution:
    def gameOfLife(self, board):
        R, C = len(board), len(board[0])
        for r in range(R):
            for c in range(C):
                live = 0
                for dr in (-1,0,1):
                    for dc in (-1,0,1):
                        if dr==0 and dc==0: continue
                        nr, nc = r+dr, c+dc
                        if 0<=nr<R and 0<=nc<C and board[nr][nc] & 1:
                            live += 1
                if board[r][c] & 1:
                    if live == 2 or live == 3: board[r][c] |= 2
                else:
                    if live == 3: board[r][c] |= 2
        for r in range(R):
            for c in range(C):
                board[r][c] >>= 1

Hashmap

383. Ransom Note

Difficulty: Easy · Tags: Hash Table, String, Counting

Leetcode

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

Constraints:

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote and magazine consist of lowercase English letters.
Approach

Counter of magazine must dominate counter of ransom note.

from collections import Counter
class Solution:
    def canConstruct(self, ransomNote, magazine):
        return not (Counter(ransomNote) - Counter(magazine))

205. Isomorphic Strings

Difficulty: Easy · Tags: Hash Table, String

Leetcode

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = “egg”, t = “add”

Output: true

Explanation:

The strings s and t can be made identical by:

  • Mapping 'e' to 'a'.
  • Mapping 'g' to 'd'.

Example 2:

Input: s = “f11”, t = “b23”

Output: false

Explanation:

The strings s and t can not be made identical as '1' needs to be mapped to both '2' and '3'.

Example 3:

Input: s = “paper”, t = “title”

Output: true

Constraints:

  • 1 <= s.length <= 5 * 10^4
  • t.length == s.length
  • s and t consist of any valid ascii character.
Approach

Maintain two maps s→t and t→s; reject on any inconsistency.

class Solution:
    def isIsomorphic(self, s, t):
        st, ts = {}, {}
        for a, b in zip(s, t):
            if st.get(a, b) != b or ts.get(b, a) != a: return False
            st[a] = b; ts[b] = a
        return True

290. Word Pattern

Difficulty: Easy · Tags: Hash Table, String

Leetcode

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:

  • Each letter in pattern maps to exactly one unique word in s.
  • Each unique word in s maps to exactly one letter in pattern.
  • No two letters map to the same word, and no two words map to the same letter.

Example 1:

Input: pattern = “abba”, s = “dog cat cat dog”

Output: true

Explanation:

The bijection can be established as:

  • 'a' maps to "dog".
  • 'b' maps to "cat".

Example 2:

Input: pattern = “abba”, s = “dog cat cat fish”

Output: false

Example 3:

Input: pattern = “aaaa”, s = “dog cat cat dog”

Output: false

Constraints:

  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters.
  • 1 <= s.length <= 3000
  • s contains only lowercase English letters and spaces ' '.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.
Approach

Same idea as isomorphic strings but between pattern chars and words.

class Solution:
    def wordPattern(self, pattern, s):
        words = s.split()
        if len(words) != len(pattern): return False
        cw, wc = {}, {}
        for ch, w in zip(pattern, words):
            if cw.get(ch, w) != w or wc.get(w, ch) != ch: return False
            cw[ch] = w; wc[w] = ch
        return True

242. Valid Anagram

Difficulty: Easy · Tags: Hash Table, String, Sorting

Leetcode

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

Example 1:

Input: s = “anagram”, t = “nagaram”

Output: true

Example 2:

Input: s = “rat”, t = “car”

Output: false

Constraints:

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Approach

Counters equal — or sort both strings.

from collections import Counter
class Solution:
    def isAnagram(self, s, t):
        return Counter(s) == Counter(t)

49. Group Anagrams

Difficulty: Medium · Tags: Array, Hash Table, String, Sorting

Leetcode

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

Example 1:

Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]

Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

Explanation:

  • There is no string in strs that can be rearranged to form "bat".
  • The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
  • The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = [“a”]

Output: [[“a”]]

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.
Approach

Group by sorted-tuple key (or 26-letter count tuple).

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs):
        g = defaultdict(list)
        for s in strs: g[''.join(sorted(s))].append(s)
        return list(g.values())

1. Two Sum

Difficulty: Easy · Tags: Array, Hash Table

Leetcode

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

Approach

One pass with a hashmap of value→index; look up target − x.

class Solution:
    def twoSum(self, nums, target):
        seen = {}
        for i, x in enumerate(nums):
            if target - x in seen: return [seen[target-x], i]
            seen[x] = i

202. Happy Number

Difficulty: Easy · Tags: Hash Table, Math, Two Pointers

Leetcode

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.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

  • 1 <= n <= 2^31 - 1
Approach

Floyd cycle detection on the digit-square-sum function — either you hit 1 or you cycle.

class Solution:
    def isHappy(self, n):
        def step(x):
            s = 0
            while x: x, d = divmod(x, 10); s += d*d
            return s
        slow, fast = n, step(n)
        while fast != 1 and slow != fast:
            slow = step(slow); fast = step(step(fast))
        return fast == 1

219. Contains Duplicate II

Difficulty: Easy · Tags: Array, Hash Table, Sliding Window

Leetcode

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5
Approach

Last-index hashmap; on revisit, check if index gap ≤ k.

class Solution:
    def containsNearbyDuplicate(self, nums, k):
        last = {}
        for i, x in enumerate(nums):
            if x in last and i - last[x] <= k: return True
            last[x] = i
        return False

128. Longest Consecutive Sequence

Difficulty: Medium · Tags: Array, Hash Table, Union-Find

Leetcode

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.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
Approach

Put nums in a set. For each x with no x-1 in set, walk upward counting the run.

class Solution:
    def longestConsecutive(self, nums):
        s = set(nums); best = 0
        for x in s:
            if x - 1 in s: continue
            y = x
            while y + 1 in s: y += 1
            best = max(best, y - x + 1)
        return best

Intervals

228. Summary Ranges

Difficulty: Easy · Tags: Array

Leetcode

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

  • "a->b" if a != b
  • "a" if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

Constraints:

  • 0 <= nums.length <= 20
  • -2^31 <= nums[i] <= 2^31 - 1
  • All the values of nums are unique.
  • nums is sorted in ascending order.
Approach

Walk array; whenever nums[i] != nums[i-1] + 1, close current range and start a new one.

class Solution:
    def summaryRanges(self, nums):
        res = []; i = 0; n = len(nums)
        while i < n:
            j = i
            while j + 1 < n and nums[j+1] == nums[j] + 1: j += 1
            res.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
            i = j + 1
        return res

56. Merge Intervals

Difficulty: Medium · Tags: Array, Sorting

Leetcode

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

Constraints:

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4
Approach

Sort by start. Walk through; merge with last if overlapping, else append.

class Solution:
    def merge(self, intervals):
        intervals.sort()
        res = []
        for s, e in intervals:
            if res and s <= res[-1][1]: res[-1][1] = max(res[-1][1], e)
            else: res.append([s, e])
        return res

57. Insert Interval

Difficulty: Medium · Tags: Array

Leetcode

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i^th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don’t need to modify intervals in-place. You can make a new array and return it.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^5
  • intervals is sorted by start_i in ascending order.
  • newInterval.length == 2
  • 0 <= start <= end <= 10^5
Approach

Three phases: copy intervals ending before new; merge overlapping ones into new; copy the rest.

class Solution:
    def insert(self, intervals, newInterval):
        res = []; i = 0; n = len(intervals)
        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i]); i += 1
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval = [min(newInterval[0], intervals[i][0]),
                           max(newInterval[1], intervals[i][1])]
            i += 1
        res.append(newInterval)
        res.extend(intervals[i:])
        return res

452. Minimum Number of Arrows to Burst Balloons

Difficulty: Medium · Tags: Array, Greedy, Sorting

Leetcode

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= x_start < x_end <= 2^31 - 1
Approach

Sort by end. Greedy: shoot at current end; every subsequent balloon starting after that end needs a new arrow.

class Solution:
    def findMinArrowShots(self, points):
        points.sort(key=lambda p: p[1])
        arrows = 0; last = -float('inf')
        for s, e in points:
            if s > last:
                arrows += 1; last = e
        return arrows

Stack

20. Valid Parentheses

Difficulty: Easy · Tags: String, Stack

Leetcode

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.
  • Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = ”()”

Output: true

Example 2:

Input: s = ”()[]{}”

Output: true

Example 3:

Input: s = ”(]”

Output: false

Example 4:

Input: s = ”([])”

Output: true

Example 5:

Input: s = ”([)]”

Output: false

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.
Approach

Stack of expected closers; push when opener, check + pop when closer.

class Solution:
    def isValid(self, s):
        pair = {')':'(', ']':'[', '}':'{'}
        st = []
        for ch in s:
            if ch in pair:
                if not st or st.pop() != pair[ch]: return False
            else: st.append(ch)
        return not st

71. Simplify Path

Difficulty: Medium · Tags: String, Stack

Leetcode

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

  • A single period '.' represents the current directory.
  • A double period '..' represents the previous/parent directory.
  • Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.
  • Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.

The simplified canonical path should follow these rules:

  • The path must start with a single slash '/'.
  • Directories within the path must be separated by exactly one slash '/'.
  • The path must not end with a slash '/', unless it is the root directory.
  • The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.

Return the simplified canonical path.

Example 1:

Input: path = “/home/”

Output: “/home”

Explanation:

The trailing slash should be removed.

Example 2:

Input: path = “/home//foo/”

Output: “/home/foo”

Explanation:

Multiple consecutive slashes are replaced by a single one.

Example 3:

Input: path = “/home/user/Documents/../Pictures”

Output: “/home/user/Pictures”

Explanation:

A double period ".." refers to the directory up a level (the parent directory).

Example 4:

Input: path = ”/../”

Output: ”/”

Explanation:

Going one level up from the root directory is not possible.

Example 5:

Input: path = ”/…/a/../b/c/../d/./”

Output: ”/…/b/d”

Explanation:

"..." is a valid name for a directory in this problem.

Constraints:

  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period '.', slash '/' or '_'.
  • path is a valid absolute Unix path.
Approach

Split by /. Push real names on a stack; .. pops; ./empty skipped.

class Solution:
    def simplifyPath(self, path):
        st = []
        for part in path.split('/'):
            if part == '' or part == '.': continue
            if part == '..':
                if st: st.pop()
            else: st.append(part)
        return '/' + '/'.join(st)

155. Min Stack

Difficulty: Medium · Tags: Stack, Design

Leetcode

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.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
Approach

Auxiliary stack tracking the running minimum at each level.

class MinStack:
    def __init__(self):
        self.s = []; self.m = []
    def push(self, val):
        self.s.append(val)
        self.m.append(val if not self.m else min(val, self.m[-1]))
    def pop(self):
        self.s.pop(); self.m.pop()
    def top(self):
        return self.s[-1]
    def getMin(self):
        return self.m[-1]

150. Evaluate Reverse Polish Notation

Difficulty: Medium · Tags: Array, Math, Stack

Leetcode

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

  • 1 <= tokens.length <= 10^4
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Approach

Stack: push numbers; on operator, pop two and push result. Use integer truncation toward zero for division.

class Solution:
    def evalRPN(self, tokens):
        st = []; ops = set("+-*/")
        for t in tokens:
            if t in ops:
                b = st.pop(); a = st.pop()
                if t == '+': st.append(a+b)
                elif t == '-': st.append(a-b)
                elif t == '*': st.append(a*b)
                else: st.append(int(a/b))
            else: st.append(int(t))
        return st[0]

224. Basic Calculator

Difficulty: Hard · Tags: Math, String, Stack, Recursion

Leetcode

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

  • 1 <= s.length <= 3 * 10^5
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.
Approach

Single pass with a stack of signs. Parentheses push the current sign multiplier; numbers are accumulated digit-by-digit.

class Solution:
    def calculate(self, s):
        total, num, sign = 0, 0, 1
        st = []
        for ch in s + '+':
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch in '+-':
                total += sign * num
                num = 0
                sign = 1 if ch == '+' else -1
            elif ch == '(':
                st.append(total); st.append(sign)
                total = 0; sign = 1
            elif ch == ')':
                total += sign * num; num = 0
                total *= st.pop()
                total += st.pop()
        return total

Linked List

141. Linked List Cycle

Difficulty: Easy · Tags: Hash Table, Linked List, Two Pointers

Leetcode

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5
  • pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Approach

Floyd’s tortoise & hare. Slow advances 1, fast advances 2; they meet iff there’s a cycle.

class Solution:
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next; fast = fast.next.next
            if slow is fast: return True
        return False

2. Add Two Numbers

Difficulty: Medium · Tags: Linked List, Math, Recursion

Leetcode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.
Approach

Walk both lists with a carry. Build a new list digit by digit.

class Solution:
    def addTwoNumbers(self, l1, l2):
        from typing import Optional
        dummy = cur = type(l1)(0) if l1 else None
        # Use a generic node class compatible with LeetCode's ListNode.
        class _N:
            def __init__(self, v, n=None): self.val=v; self.next=n
        dummy = _N(0); cur = dummy; carry = 0
        while l1 or l2 or carry:
            s = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)
            carry, d = divmod(s, 10)
            cur.next = _N(d); cur = cur.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return dummy.next

21. Merge Two Sorted Lists

Difficulty: Easy · Tags: Linked List, Recursion

Leetcode

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.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.
Approach

Dummy head; splice the smaller node each step; attach remainder at end.

class Solution:
    def mergeTwoLists(self, l1, l2):
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        dummy = _N(); cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1; l1 = l1.next
            else:
                cur.next = l2; l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

138. Copy List with Random Pointer

Difficulty: Medium · Tags: Hash Table, Linked List

Leetcode

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random is null or is pointing to some node in the linked list.
Approach

Two passes with a hashmap old→new. First pass clones nodes; second pass wires next and random.

class Solution:
    def copyRandomList(self, head):
        if not head: return None
        m = {}
        cur = head
        while cur:
            m[cur] = type(cur)(cur.val); cur = cur.next
        cur = head
        while cur:
            m[cur].next = m.get(cur.next)
            m[cur].random = m.get(cur.random)
            cur = cur.next
        return m[head]

92. Reverse Linked List II

Difficulty: Medium · Tags: Linked List

Leetcode

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Follow up: Could you do it in one pass?

Approach

Walk to position left-1, then iteratively splice the next node to the front of the sub-list right-left times.

class Solution:
    def reverseBetween(self, head, left, right):
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        dummy = _N(0, head); prev = dummy
        for _ in range(left - 1): prev = prev.next
        cur = prev.next
        for _ in range(right - left):
            nxt = cur.next
            cur.next = nxt.next
            nxt.next = prev.next
            prev.next = nxt
        return dummy.next

25. Reverse Nodes in k-Group

Difficulty: Hard · Tags: Linked List, Recursion

Leetcode

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Approach

Walk in chunks of k (peek ahead to verify length); reverse each chunk in place and stitch.

class Solution:
    def reverseKGroup(self, head, k):
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        dummy = _N(0, head); group_prev = dummy
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth: return dummy.next
            group_next = kth.next
            prev, cur = group_next, group_prev.next
            while cur is not group_next:
                nxt = cur.next; cur.next = prev; prev = cur; cur = nxt
            tmp = group_prev.next
            group_prev.next = kth
            group_prev = tmp

19. Remove Nth Node From End of List

Difficulty: Medium · Tags: Linked List, Two Pointers

Leetcode

Given the head of a linked list, remove the n^th node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Follow up: Could you do this in one pass?

Approach

Two-pointer gap of n: advance fast n steps, then move both until fast hits end; slow is at the previous node.

class Solution:
    def removeNthFromEnd(self, head, n):
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        dummy = _N(0, head); fast = slow = dummy
        for _ in range(n): fast = fast.next
        while fast.next:
            fast = fast.next; slow = slow.next
        slow.next = slow.next.next
        return dummy.next

82. Remove Duplicates from Sorted List II

Difficulty: Medium · Tags: Linked List, Two Pointers

Leetcode

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.
Approach

Dummy head + previous-distinct pointer. If cur.val == cur.next.val, skip the entire run; else advance prev.

class Solution:
    def deleteDuplicates(self, head):
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        dummy = _N(0, head); prev = dummy
        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val: head = head.next
                prev.next = head.next
            else:
                prev = prev.next
            head = head.next
        return dummy.next

61. Rotate List

Difficulty: Medium · Tags: Linked List, Two Pointers

Leetcode

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

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

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

  • The number of nodes in the list is in the range [0, 500].
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9
Approach

Find length, connect tail→head to form a ring, then break the ring at length − k%length.

class Solution:
    def rotateRight(self, head, k):
        if not head or not head.next: return head
        n = 1; tail = head
        while tail.next: tail = tail.next; n += 1
        k %= n
        if k == 0: return head
        tail.next = head
        new_tail = head
        for _ in range(n - k - 1): new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None
        return new_head

86. Partition List

Difficulty: Medium · Tags: Linked List, Two Pointers

Leetcode

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

  • The number of nodes in the list is in the range [0, 200].
  • -100 <= Node.val <= 100
  • -200 <= x <= 200
Approach

Build two separate lists (less-than-x, ≥x) then concatenate them.

class Solution:
    def partition(self, head, x):
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        lo, hi = _N(), _N(); lt, ht = lo, hi
        while head:
            if head.val < x: lt.next = head; lt = lt.next
            else: ht.next = head; ht = ht.next
            head = head.next
        ht.next = None; lt.next = hi.next
        return lo.next

146. LRU Cache

Difficulty: Medium · Tags: Hash Table, Linked List, Design, Doubly-Linked List

Leetcode

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls will be made to get and put.
Approach

Hashmap + doubly linked list. Sentinel head/tail; hashmap maps key→node for O(1) move-to-front and eviction.

class LRUCache:
    class _N:
        __slots__ = ('k','v','p','n')
        def __init__(self, k=0, v=0):
            self.k=k; self.v=v; self.p=self.n=None
    def __init__(self, capacity):
        self.cap = capacity; self.m = {}
        self.h = self._N(); self.t = self._N()
        self.h.n = self.t; self.t.p = self.h
    def _remove(self, x):
        x.p.n = x.n; x.n.p = x.p
    def _add_front(self, x):
        x.n = self.h.n; x.p = self.h
        self.h.n.p = x; self.h.n = x
    def get(self, key):
        if key not in self.m: return -1
        x = self.m[key]; self._remove(x); self._add_front(x)
        return x.v
    def put(self, key, value):
        if key in self.m:
            x = self.m[key]; x.v = value; self._remove(x); self._add_front(x); return
        if len(self.m) == self.cap:
            old = self.t.p; self._remove(old); del self.m[old.k]
        x = self._N(key, value); self.m[key] = x; self._add_front(x)

Binary Tree General

104. Maximum Depth of Binary Tree

Difficulty: Easy · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

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.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [0, 10^4].
  • -100 <= Node.val <= 100
Approach

Recurse: depth = 1 + max(left depth, right depth); 0 for None.

class Solution:
    def maxDepth(self, root):
        if not root: return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

100. Same Tree

Difficulty: Easy · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

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.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4
Approach

Both null → equal; one null → not equal; otherwise val match and recurse on children.

class Solution:
    def isSameTree(self, p, q):
        if not p and not q: return True
        if not p or not q or p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

226. Invert Binary Tree

Difficulty: Easy · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

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

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Approach

Swap children and recurse.

class Solution:
    def invertTree(self, root):
        if not root: return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

101. Symmetric Tree

Difficulty: Easy · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

Approach

Helper compares mirror pairs: left.left vs right.right, left.right vs right.left.

class Solution:
    def isSymmetric(self, root):
        def mir(a, b):
            if not a and not b: return True
            if not a or not b or a.val != b.val: return False
            return mir(a.left, b.right) and mir(a.right, b.left)
        return mir(root, root)

105. Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium · Tags: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Leetcode

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.
  • Each value of inorder also appears in preorder.
  • preorder is guaranteed to be the preorder traversal of the tree.
  • inorder is guaranteed to be the inorder traversal of the tree.
Approach

Root = first of preorder; split inorder at that root to get left/right inorder sizes; recurse with the matching preorder slices. Index map gives O(n).

class Solution:
    def buildTree(self, preorder, inorder):
        class _N:
            def __init__(self, v): self.val=v; self.left=self.right=None
        idx = {v:i for i,v in enumerate(inorder)}
        it = iter(preorder)
        def build(l, r):
            if l > r: return None
            v = next(it); node = _N(v); m = idx[v]
            node.left = build(l, m-1); node.right = build(m+1, r)
            return node
        return build(0, len(inorder)-1)

106. Construct Binary Tree from Inorder and Postorder Traversal

Difficulty: Medium · Tags: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Leetcode

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.
Approach

Root = last of postorder; consume postorder from the right; recurse right then left.

class Solution:
    def buildTree(self, inorder, postorder):
        class _N:
            def __init__(self, v): self.val=v; self.left=self.right=None
        idx = {v:i for i,v in enumerate(inorder)}
        def build(l, r):
            if l > r: return None
            v = postorder.pop(); node = _N(v); m = idx[v]
            node.right = build(m+1, r); node.left = build(l, m-1)
            return node
        return build(0, len(inorder)-1)

117. Populating Next Right Pointers in Each Node II

Difficulty: Medium · Tags: Linked List, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 6000].
  • -100 <= Node.val <= 100

Follow-up:

  • You may only use constant extra space.
  • The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
Approach

Level-by-level traversal using the already-wired next pointers of the current level to build the next.

class Solution:
    def connect(self, root):
        if not root: return None
        cur = root
        while cur:
            dummy = type(cur)(0); tail = dummy
            p = cur
            while p:
                if p.left: tail.next = p.left; tail = tail.next
                if p.right: tail.next = p.right; tail = tail.next
                p = p.next
            cur = dummy.next
        return root

114. Flatten Binary Tree to Linked List

Difficulty: Medium · Tags: Linked List, Stack, Tree, Depth-First Search, Binary Tree

Leetcode

Given the root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Approach

Reverse-Morris: traverse right→left→root and chain each node into a running prev.

class Solution:
    def flatten(self, root):
        self.prev = None
        def rec(node):
            if not node: return
            rec(node.right); rec(node.left)
            node.right = self.prev; node.left = None
            self.prev = node
        rec(root)

112. Path Sum

Difficulty: Easy · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Approach

DFS subtracting node.val; at a leaf check whether remaining target is 0.

class Solution:
    def hasPathSum(self, root, targetSum):
        if not root: return False
        if not root.left and not root.right: return root.val == targetSum
        t = targetSum - root.val
        return self.hasPathSum(root.left, t) or self.hasPathSum(root.right, t)

129. Sum Root to Leaf Numbers

Difficulty: Medium · Tags: Tree, Depth-First Search, Binary Tree

Leetcode

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

  • For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path `1->2` represents the number `12`.
The root-to-leaf path `1->3` represents the number `13`.
Therefore, sum = 12 + 13 = `25`.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path `4->9->5` represents the number 495.
The root-to-leaf path `4->9->1` represents the number 491.
The root-to-leaf path `4->0` represents the number 40.
Therefore, sum = 495 + 491 + 40 = `1026`.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.
Approach

DFS carrying running number cur*10 + val; at leaves add to total.

class Solution:
    def sumNumbers(self, root):
        def dfs(node, cur):
            if not node: return 0
            cur = cur*10 + node.val
            if not node.left and not node.right: return cur
            return dfs(node.left, cur) + dfs(node.right, cur)
        return dfs(root, 0)

124. Binary Tree Maximum Path Sum

Difficulty: Hard · Tags: Dynamic Programming, Tree, Depth-First Search, Binary Tree

Leetcode

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.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

  • The number of nodes in the tree is in the range [1, 3 * 10^4].
  • -1000 <= Node.val <= 1000
Approach

Post-order recursion returning the best one-sided gain (≥0). At each node update global best with node.val + leftGain + rightGain.

class Solution:
    def maxPathSum(self, root):
        self.best = float('-inf')
        def gain(n):
            if not n: return 0
            l = max(0, gain(n.left)); r = max(0, gain(n.right))
            self.best = max(self.best, n.val + l + r)
            return n.val + max(l, r)
        gain(root); return self.best

173. Binary Search Tree Iterator

Difficulty: Medium · Tags: Stack, Tree, Design, Binary Search Tree, Binary Tree, Iterator

Leetcode

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

  • BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
  • boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
  • int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

Constraints:

  • The number of nodes in the tree is in the range [1, 10^5].
  • 0 <= Node.val <= 10^6
  • At most 10^5 calls will be made to hasNext, and next.

Follow up:

  • Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?
Approach

Stack-based controlled in-order. On init push left spine; next pops, then pushes left spine of popped node’s right child.

class BSTIterator:
    def __init__(self, root):
        self.st = []; self._push(root)
    def _push(self, n):
        while n: self.st.append(n); n = n.left
    def next(self):
        n = self.st.pop(); self._push(n.right); return n.val
    def hasNext(self):
        return bool(self.st)

222. Count Complete Tree Nodes

Difficulty: Easy · Tags: Binary Search, Bit Manipulation, Tree, Binary Tree

Leetcode

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n)` time complexity.

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 10^4].
  • 0 <= Node.val <= 5 * 10^4
  • The tree is guaranteed to be complete.
Approach

Compare left-spine and right-spine heights. Equal → perfect subtree of size 2^h−1; otherwise recurse on both sides.

class Solution:
    def countNodes(self, root):
        def h_left(n):
            d = 0
            while n: n = n.left; d += 1
            return d
        def h_right(n):
            d = 0
            while n: n = n.right; d += 1
            return d
        if not root: return 0
        l, r = h_left(root), h_right(root)
        if l == r: return (1 << l) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

236. Lowest Common Ancestor of a Binary Tree

Difficulty: Medium · Tags: Tree, Depth-First Search, Binary Tree

Leetcode

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.
Approach

Recursive search: if subtree contains either p or q return it; if both sides return non-null, current node is LCA.

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root is p or root is q: return root
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l and r: return root
        return l or r

Binary Tree BFS

199. Binary Tree Right Side View

Difficulty: Medium · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Explanation:

Example 2:

Input: root = [1,2,3,4,null,null,null,5]

Output: [1,3,4,5]

Explanation:

Example 3:

Input: root = [1,null,3]

Output: [1,3]

Example 4:

Input: root = []

Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Approach

BFS by level; last node of each level joins the answer.

from collections import deque
class Solution:
    def rightSideView(self, root):
        if not root: return []
        res = []; q = deque([root])
        while q:
            n = len(q); last = None
            for _ in range(n):
                x = q.popleft(); last = x.val
                if x.left: q.append(x.left)
                if x.right: q.append(x.right)
            res.append(last)
        return res

637. Average of Levels in Binary Tree

Difficulty: Easy · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Leetcode

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2:

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1
Approach

BFS; for each level compute sum / count.

from collections import deque
class Solution:
    def averageOfLevels(self, root):
        q = deque([root]); res = []
        while q:
            n = len(q); s = 0
            for _ in range(n):
                x = q.popleft(); s += x.val
                if x.left: q.append(x.left)
                if x.right: q.append(x.right)
            res.append(s / n)
        return res

102. Binary Tree Level Order Traversal

Difficulty: Medium · Tags: Tree, Breadth-First Search, Binary Tree

Leetcode

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
Approach

Standard BFS, collecting one list per level.

from collections import deque
class Solution:
    def levelOrder(self, root):
        if not root: return []
        res = []; q = deque([root])
        while q:
            level = []
            for _ in range(len(q)):
                x = q.popleft(); level.append(x.val)
                if x.left: q.append(x.left)
                if x.right: q.append(x.right)
            res.append(level)
        return res

103. Binary Tree Zigzag Level Order Traversal

Difficulty: Medium · Tags: Tree, Breadth-First Search, Binary Tree

Leetcode

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100
Approach

BFS with a flag flipped each level — reverse the level list when going right→left.

from collections import deque
class Solution:
    def zigzagLevelOrder(self, root):
        if not root: return []
        res = []; q = deque([root]); ltr = True
        while q:
            level = []
            for _ in range(len(q)):
                x = q.popleft(); level.append(x.val)
                if x.left: q.append(x.left)
                if x.right: q.append(x.right)
            res.append(level if ltr else level[::-1]); ltr = not ltr
        return res

Binary Search Tree

530. Minimum Absolute Difference in BST

Difficulty: Easy · Tags: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

Leetcode

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 10^4].
  • 0 <= Node.val <= 10^5

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Approach

In-order traversal yields sorted values; track previous and minimum gap.

class Solution:
    def getMinimumDifference(self, root):
        self.prev = None; self.best = float('inf')
        def inorder(n):
            if not n: return
            inorder(n.left)
            if self.prev is not None: self.best = min(self.best, n.val - self.prev)
            self.prev = n.val
            inorder(n.right)
        inorder(root); return self.best

230. Kth Smallest Element in a BST

Difficulty: Medium · Tags: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Leetcode

Given the root of a binary search tree, and an integer k, return the k^th smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

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

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Approach

Iterative in-order with a stack; stop after k pops.

class Solution:
    def kthSmallest(self, root, k):
        st = []; cur = root
        while True:
            while cur: st.append(cur); cur = cur.left
            cur = st.pop(); k -= 1
            if k == 0: return cur.val
            cur = cur.right

98. Validate Binary Search Tree

Difficulty: Medium · Tags: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Leetcode

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys strictly less than the node’s key.
  • The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1
Approach

DFS with (low, high) bounds inherited from ancestors; each node must lie strictly in (low, high).

class Solution:
    def isValidBST(self, root, lo=float('-inf'), hi=float('inf')):
        if not root: return True
        if not (lo < root.val < hi): return False
        return (self.isValidBST(root.left, lo, root.val)
            and self.isValidBST(root.right, root.val, hi))

Graph General

200. Number of Islands

Difficulty: Medium · Tags: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Leetcode

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 all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.
Approach

DFS or BFS from each unvisited ‘1’, sinking the whole island to ‘0’. Count starts.

class Solution:
    def numIslands(self, grid):
        R, C = len(grid), len(grid[0]); count = 0
        def dfs(r, c):
            if r<0 or r>=R or c<0 or c>=C or grid[r][c] != '1': return
            grid[r][c] = '0'
            dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
        for r in range(R):
            for c in range(C):
                if grid[r][c] == '1': count += 1; dfs(r, c)
        return count

130. Surrounded Regions

Difficulty: Medium · Tags: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Leetcode

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

  • Connect: A cell is connected to adjacent cells horizontally or vertically.
  • Region: To form a region connect every 'O' cell.
  • Surround: A region is surrounded if none of the 'O' cells in that region are on the edge of the board. Such regions are completely enclosed by 'X' cells.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

Example 1:

Input: board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]

Output: [[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]

Explanation:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [[“X”]]

Output: [[“X”]]

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'.
Approach

Mark all ‘O’ connected to a border as safe; flip remaining ‘O’ to ‘X’, restore safe to ‘O’.

class Solution:
    def solve(self, board):
        R, C = len(board), len(board[0])
        def dfs(r, c):
            if r<0 or r>=R or c<0 or c>=C or board[r][c] != 'O': return
            board[r][c] = '#'
            dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
        for r in range(R):
            dfs(r, 0); dfs(r, C-1)
        for c in range(C):
            dfs(0, c); dfs(R-1, c)
        for r in range(R):
            for c in range(C):
                board[r][c] = 'O' if board[r][c] == '#' else 'X'

133. Clone Graph

Difficulty: Medium · Tags: Hash Table, Depth-First Search, Breadth-First Search, Graph Theory

Leetcode

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.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Constraints:

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The Graph is connected and all nodes can be visited starting from the given node.
Approach

DFS with a node→clone hashmap; create clone before recursing on neighbors.

class Solution:
    def cloneGraph(self, node):
        if not node: return None
        m = {}
        def dfs(n):
            if n in m: return m[n]
            c = type(n)(n.val); m[n] = c
            c.neighbors = [dfs(nb) for nb in n.neighbors]
            return c
        return dfs(node)

399. Evaluate Division

Difficulty: Medium · Tags: Array, String, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Shortest Path

Leetcode

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable.

You are also given some queries, where queries[j] = [C_j, D_j] represents the j^th query where you must find the answer for C_j / D_j = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= A_i.length, B_i.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= C_j.length, D_j.length <= 5
  • A_i, B_i, C_j, D_j consist of lower case English letters and digits.
Approach

Build a weighted directed graph (a/b = w → edge a→b weight w, b→a weight 1/w). DFS product from source to target.

from collections import defaultdict
class Solution:
    def calcEquation(self, equations, values, queries):
        g = defaultdict(dict)
        for (a,b), v in zip(equations, values):
            g[a][b] = v; g[b][a] = 1.0/v
        def dfs(s, t, seen):
            if s not in g or t not in g: return -1.0
            if s == t: return 1.0
            seen.add(s)
            for nb, w in g[s].items():
                if nb in seen: continue
                r = dfs(nb, t, seen)
                if r != -1.0: return w * r
            return -1.0
        return [dfs(a, b, set()) for a, b in queries]

207. Course Schedule

Difficulty: Medium · Tags: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Leetcode

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_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < numCourses
  • All the pairs prerequisites[i] are unique.
Approach

Topological sort via Kahn’s algorithm: detect a cycle by whether we manage to process all nodes.

from collections import defaultdict, deque
class Solution:
    def canFinish(self, n, prerequisites):
        g = defaultdict(list); indeg = [0]*n
        for a, b in prerequisites:
            g[b].append(a); indeg[a] += 1
        q = deque(i for i in range(n) if indeg[i] == 0); done = 0
        while q:
            x = q.popleft(); done += 1
            for y in g[x]:
                indeg[y] -= 1
                if indeg[y] == 0: q.append(y)
        return done == n

210. Course Schedule II

Difficulty: Medium · Tags: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Leetcode

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_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < numCourses
  • a_i != b_i
  • All the pairs [a_i, b_i] are distinct.
Approach

Same Kahn’s algorithm but record processing order; empty if a cycle exists.

from collections import defaultdict, deque
class Solution:
    def findOrder(self, n, prerequisites):
        g = defaultdict(list); indeg = [0]*n
        for a, b in prerequisites:
            g[b].append(a); indeg[a] += 1
        q = deque(i for i in range(n) if indeg[i] == 0); order = []
        while q:
            x = q.popleft(); order.append(x)
            for y in g[x]:
                indeg[y] -= 1
                if indeg[y] == 0: q.append(y)
        return order if len(order) == n else []

Graph BFS

909. Snakes and Ladders

Difficulty: Medium · Tags: Array, Breadth-First Search, Matrix

Leetcode

You are given an n x n integer matrix board where the cells are labeled from 1 to n^2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

  • Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n^2)].
  • This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
  • If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
  • The game ends when you reach the square n^2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n^2 are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

  • For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of dice rolls required to reach the square n^2. If it is not possible to reach the square, return -1.

Example 1:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1

Constraints:

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is either -1 or in the range [1, n^2].
  • The squares labeled 1 and n^2 are not the starting points of any snake or ladder.
Approach

BFS over labels 1..n²; each state has up to 6 successors. Convert label to (row, col) accounting for boustrophedon order.

from collections import deque
class Solution:
    def snakesAndLadders(self, board):
        n = len(board)
        def cell(label):
            q, r = divmod(label - 1, n)
            row = n - 1 - q
            col = r if q % 2 == 0 else n - 1 - r
            return board[row][col]
        seen = {1}; q = deque([(1, 0)])
        while q:
            s, d = q.popleft()
            if s == n*n: return d
            for nxt in range(s+1, min(s+6, n*n) + 1):
                dest = cell(nxt)
                if dest != -1: nxt2 = dest
                else: nxt2 = nxt
                if nxt2 not in seen:
                    seen.add(nxt2); q.append((nxt2, d+1))
        return -1

433. Minimum Genetic Mutation

Difficulty: Medium · Tags: Hash Table, String, Breadth-First Search

Leetcode

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

  • For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Example 2:

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2

Constraints:

  • 0 <= bank.length <= 10
  • startGene.length == endGene.length == bank[i].length == 8
  • startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].
Approach

BFS treating each gene as a node; edges connect strings differing by one of A/C/G/T at any position. Only explore strings in bank.

from collections import deque
class Solution:
    def minMutation(self, start, end, bank):
        bank = set(bank)
        if end not in bank: return -1
        q = deque([(start, 0)]); seen = {start}
        while q:
            s, d = q.popleft()
            if s == end: return d
            for i in range(len(s)):
                for c in 'ACGT':
                    if c == s[i]: continue
                    nxt = s[:i] + c + s[i+1:]
                    if nxt in bank and nxt not in seen:
                        seen.add(nxt); q.append((nxt, d+1))
        return -1

127. Word Ladder

Difficulty: Hard · Tags: Hash Table, String, Breadth-First Search

Leetcode

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s_1 -> s_2 -> ... -> s_k such that:

  • Every adjacent pair of words differs by a single letter.
  • Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • s_k == 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.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.
Approach

BFS where neighbors are words differing by one letter. Use wildcard buckets (h*t etc.) to find neighbors in O(L) per word.

from collections import defaultdict, deque
class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        words = set(wordList)
        if endWord not in words: return 0
        L = len(beginWord)
        buckets = defaultdict(list)
        for w in words:
            for i in range(L):
                buckets[w[:i] + '*' + w[i+1:]].append(w)
        seen = {beginWord}; q = deque([(beginWord, 1)])
        while q:
            w, d = q.popleft()
            if w == endWord: return d
            for i in range(L):
                key = w[:i] + '*' + w[i+1:]
                for nb in buckets[key]:
                    if nb not in seen:
                        seen.add(nb); q.append((nb, d+1))
                buckets[key] = []
        return 0

Trie

208. Implement Trie (Prefix Tree)

Difficulty: Medium · Tags: Hash Table, String, Design, Trie

Leetcode

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.
Approach

Nested dict + an end-of-word flag. Insert/lookup walk the chars.

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        n = self.root
        for c in word:
            n = n.setdefault(c, {})
        n['$'] = True
    def _find(self, word):
        n = self.root
        for c in word:
            if c not in n: return None
            n = n[c]
        return n
    def search(self, word):
        n = self._find(word)
        return bool(n and n.get('$'))
    def startsWith(self, prefix):
        return self._find(prefix) is not None

211. Design Add and Search Words Data Structure

Difficulty: Medium · Tags: String, Depth-First Search, Design, Trie

Leetcode

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

  • 1 <= word.length <= 25
  • word in addWord consists of lowercase English letters.
  • word in search consist of '.' or lowercase English letters.
  • There will be at most 2 dots in word for search queries.
  • At most 10^4 calls will be made to addWord and search.
Approach

Trie plus DFS for ’.’ wildcards (try every child).

class WordDictionary:
    def __init__(self):
        self.root = {}
    def addWord(self, word):
        n = self.root
        for c in word: n = n.setdefault(c, {})
        n['$'] = True
    def search(self, word):
        def dfs(i, n):
            if i == len(word): return '$' in n
            c = word[i]
            if c == '.':
                return any(k != '$' and dfs(i+1, v) for k, v in n.items())
            return c in n and dfs(i+1, n[c])
        return dfs(0, self.root)

212. Word Search II

Difficulty: Hard · Tags: Array, String, Backtracking, Trie, Matrix

Leetcode

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 10^4
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.
Approach

Build a trie of words. DFS each cell, descending in both the grid and the trie. Prune by removing finished words from the trie.

class Solution:
    def findWords(self, board, words):
        root = {}
        for w in words:
            n = root
            for c in w: n = n.setdefault(c, {})
            n['$'] = w
        R, C = len(board), len(board[0]); res = []
        def dfs(r, c, node):
            ch = board[r][c]
            if ch not in node: return
            nxt = node[ch]
            if '$' in nxt:
                res.append(nxt.pop('$'))
            board[r][c] = '#'
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r+dr, c+dc
                if 0<=nr<R and 0<=nc<C and board[nr][nc] != '#':
                    dfs(nr, nc, nxt)
            board[r][c] = ch
            if not nxt: node.pop(ch, None)
        for r in range(R):
            for c in range(C): dfs(r, c, root)
        return res

Backtracking

17. Letter Combinations of a Phone Number

Difficulty: Medium · Tags: Hash Table, String, Backtracking

Leetcode

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

  • 1 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].
Approach

Iteratively expand the current set of partial strings by appending each letter for the next digit.

class Solution:
    def letterCombinations(self, digits):
        if not digits: return []
        m = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
        res = ['']
        for d in digits:
            res = [p + c for p in res for c in m[d]]
        return res

77. Combinations

Difficulty: Medium · Tags: Backtracking

Leetcode

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= n
Approach

Backtrack picking the next index ≥ last+1. Prune when remaining slots can’t be filled.

class Solution:
    def combine(self, n, k):
        res = []
        def back(start, path):
            if len(path) == k: res.append(path[:]); return
            need = k - len(path)
            for i in range(start, n - need + 2):
                path.append(i); back(i+1, path); path.pop()
        back(1, []); return res

46. Permutations

Difficulty: Medium · Tags: Array, Backtracking

Leetcode

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.
Approach

Backtrack swapping elements into the current position, or use a used mask.

class Solution:
    def permute(self, nums):
        res = []
        def back(i):
            if i == len(nums): res.append(nums[:]); return
            for j in range(i, len(nums)):
                nums[i], nums[j] = nums[j], nums[i]
                back(i+1)
                nums[i], nums[j] = nums[j], nums[i]
        back(0); return res

39. Combination Sum

Difficulty: Medium · Tags: Array, Backtracking

Leetcode

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40
Approach

Backtrack with reuse allowed: at each step try candidates from the current index forward, subtracting from remaining target.

class Solution:
    def combinationSum(self, candidates, target):
        candidates.sort(); res = []
        def back(start, rem, path):
            if rem == 0: res.append(path[:]); return
            for i in range(start, len(candidates)):
                c = candidates[i]
                if c > rem: break
                path.append(c); back(i, rem - c, path); path.pop()
        back(0, target, []); return res

52. N-Queens II

Difficulty: Hard · Tags: Backtracking

Leetcode

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 9
Approach

Backtrack row-by-row with three bitmask-style sets for columns and the two diagonals.

class Solution:
    def totalNQueens(self, n):
        cols, d1, d2 = set(), set(), set()
        def back(r):
            if r == n: return 1
            total = 0
            for c in range(n):
                if c in cols or r-c in d1 or r+c in d2: continue
                cols.add(c); d1.add(r-c); d2.add(r+c)
                total += back(r+1)
                cols.remove(c); d1.remove(r-c); d2.remove(r+c)
            return total
        return back(0)

22. Generate Parentheses

Difficulty: Medium · Tags: String, Dynamic Programming, Backtracking

Leetcode

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

  • 1 <= n <= 8
Approach

Backtrack tracking remaining ( and ) slots; can place ( if any left, can place ) if remaining ) > remaining (.

class Solution:
    def generateParenthesis(self, n):
        res = []
        def back(s, open_left, close_left):
            if open_left == 0 and close_left == 0: res.append(s); return
            if open_left: back(s + '(', open_left-1, close_left)
            if close_left > open_left: back(s + ')', open_left, close_left-1)
        back('', n, n); return res

Difficulty: Medium · Tags: Array, String, Backtracking, Depth-First Search, Matrix

Leetcode

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, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Approach

DFS from every cell. Temporarily mark visited by mutating the cell, restore on backtrack.

class Solution:
    def exist(self, board, word):
        R, C = len(board), len(board[0])
        def dfs(r, c, i):
            if i == len(word): return True
            if r<0 or r>=R or c<0 or c>=C or board[r][c] != word[i]: return False
            tmp = board[r][c]; board[r][c] = '#'
            ok = (dfs(r+1,c,i+1) or dfs(r-1,c,i+1)
                  or dfs(r,c+1,i+1) or dfs(r,c-1,i+1))
            board[r][c] = tmp
            return ok
        return any(dfs(r,c,0) for r in range(R) for c in range(C))

Divide & Conquer

108. Convert Sorted Array to Binary Search Tree

Difficulty: Easy · Tags: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

Leetcode

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in a strictly increasing order.
Approach

Pick middle of range as root and recurse on halves.

class Solution:
    def sortedArrayToBST(self, nums):
        class _N:
            def __init__(self, v): self.val=v; self.left=self.right=None
        def build(l, r):
            if l > r: return None
            m = (l + r) // 2
            n = _N(nums[m])
            n.left = build(l, m-1); n.right = build(m+1, r)
            return n
        return build(0, len(nums)-1)

148. Sort List

Difficulty: Medium · Tags: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort

Leetcode

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 10^4].
  • -10^5 <= Node.val <= 10^5

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Approach

Merge sort on linked list. Split via slow/fast, sort halves, merge.

class Solution:
    def sortList(self, head):
        if not head or not head.next: return head
        slow, fast, prev = head, head, None
        while fast and fast.next:
            prev = slow; slow = slow.next; fast = fast.next.next
        prev.next = None
        a = self.sortList(head); b = self.sortList(slow)
        # merge
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        dummy = _N(); cur = dummy
        while a and b:
            if a.val <= b.val: cur.next = a; a = a.next
            else: cur.next = b; b = b.next
            cur = cur.next
        cur.next = a or b
        return dummy.next

427. Construct Quad Tree

Difficulty: Medium · Tags: Array, Divide and Conquer, Tree, Matrix

Leetcode

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.

Return the root of the Quad-Tree representing grid.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

  • val: True if the node represents a grid of 1’s or False if the node represents a grid of 0’s. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
  • isLeaf: True if the node is a leaf node on the tree or False if the node has four children.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

  • If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
  • If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
  • Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

You don’t need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

Constraints:

  • n == grid.length == grid[i].length
  • n == 2^x where 0 <= x <= 6
Approach

Recurse on quadrants. If all four children are leaves with the same value, collapse into a single leaf.

class Solution:
    def construct(self, grid):
        from typing import Optional
        Node = type(grid[0][0]).__class__ if False else None
        # Use the LeetCode Node class implicitly available in env; emulate via duck typing.
        class _N:
            def __init__(self, val, isLeaf, tl=None, tr=None, bl=None, br=None):
                self.val=val; self.isLeaf=isLeaf
                self.topLeft=tl; self.topRight=tr
                self.bottomLeft=bl; self.bottomRight=br
        def build(r, c, n):
            if n == 1: return _N(bool(grid[r][c]), True)
            half = n // 2
            tl = build(r, c, half); tr = build(r, c+half, half)
            bl = build(r+half, c, half); br = build(r+half, c+half, half)
            if (tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf
                and tl.val == tr.val == bl.val == br.val):
                return _N(tl.val, True)
            return _N(False, False, tl, tr, bl, br)
        return build(0, 0, len(grid))

23. Merge k Sorted Lists

Difficulty: Hard · Tags: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort

Leetcode

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.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted linked list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 10^4.
Approach

Min-heap of (val, list-index, node). Pop smallest, push its successor.

import heapq
class Solution:
    def mergeKLists(self, lists):
        class _N:
            def __init__(self, v=0, n=None): self.val=v; self.next=n
        h = []
        for i, node in enumerate(lists):
            if node: heapq.heappush(h, (node.val, i, node))
        dummy = _N(); cur = dummy
        while h:
            v, i, n = heapq.heappop(h)
            cur.next = n; cur = n
            if n.next: heapq.heappush(h, (n.next.val, i, n.next))
        return dummy.next

Kadane’s Algorithm

53. Maximum Subarray

Difficulty: Medium · Tags: Array, Divide and Conquer, Dynamic Programming

Leetcode

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

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Approach

Kadane: running sum, reset to current if negative; track best seen.

class Solution:
    def maxSubArray(self, nums):
        cur = best = nums[0]
        for x in nums[1:]:
            cur = max(x, cur + x); best = max(best, cur)
        return best

918. Maximum Sum Circular Subarray

Difficulty: Medium · Tags: Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue

Leetcode

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example 1:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

Constraints:

  • n == nums.length
  • 1 <= n <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
Approach

Answer is max of standard Kadane and (total − min subarray). Edge case: all-negative array — return Kadane max.

class Solution:
    def maxSubarraySumCircular(self, nums):
        total = 0; cur_max = best_max = nums[0]; cur_min = best_min = nums[0]
        total = nums[0]
        for x in nums[1:]:
            total += x
            cur_max = max(x, cur_max + x); best_max = max(best_max, cur_max)
            cur_min = min(x, cur_min + x); best_min = min(best_min, cur_min)
        if best_max < 0: return best_max
        return max(best_max, total - best_min)

35. Search Insert Position

Difficulty: Easy · Tags: Array, Binary Search

Leetcode

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.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4
Approach

Binary search for the first index where nums[i] >= target.

class Solution:
    def searchInsert(self, nums, target):
        l, r = 0, len(nums)
        while l < r:
            m = (l + r) // 2
            if nums[m] < target: l = m + 1
            else: r = m
        return l

74. Search a 2D Matrix

Difficulty: Medium · Tags: Array, Binary Search, Matrix

Leetcode

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4
Approach

Treat the matrix as a flat sorted array; binary search using divmod for row/col.

class Solution:
    def searchMatrix(self, matrix, target):
        R, C = len(matrix), len(matrix[0])
        l, r = 0, R*C
        while l < r:
            m = (l + r) // 2; v = matrix[m // C][m % C]
            if v == target: return True
            if v < target: l = m + 1
            else: r = m
        return False

162. Find Peak Element

Difficulty: Medium · Tags: Array, Binary Search

Leetcode

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums[i] != nums[i + 1] for all valid i.
Approach

Binary search: if nums[m] < nums[m+1], a peak exists to the right; else to the left (including m).

class Solution:
    def findPeakElement(self, nums):
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] < nums[m+1]: l = m + 1
            else: r = m
        return l

33. Search in Rotated Sorted Array

Difficulty: Medium · Tags: Array, Binary Search

Leetcode

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

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.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -10^4 <= target <= 10^4
Approach

Binary search with rotation. The half containing nums[l]..nums[m] (or the other) is sorted — decide based on that.

class Solution:
    def search(self, nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target: return m
            if nums[l] <= nums[m]:
                if nums[l] <= target < nums[m]: r = m - 1
                else: l = m + 1
            else:
                if nums[m] < target <= nums[r]: l = m + 1
                else: r = m - 1
        return -1

34. Find First and Last Position of Element in Sorted Array

Difficulty: Medium · Tags: Array, Binary Search

Leetcode

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.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is a non-decreasing array.
  • -10^9 <= target <= 10^9
Approach

Two binary searches: leftmost ≥ target and leftmost > target. Difference (and validity) yields the range.

from bisect import bisect_left, bisect_right
class Solution:
    def searchRange(self, nums, target):
        l = bisect_left(nums, target); r = bisect_right(nums, target) - 1
        if l <= r: return [l, r]
        return [-1, -1]

153. Find Minimum in Rotated Sorted Array

Difficulty: Medium · Tags: Array, Binary Search

Leetcode

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] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-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.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.
Approach

Binary search: compare mid to nums[r] — if greater, the min is to the right, else to the left (including m).

class Solution:
    def findMin(self, nums):
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] > nums[r]: l = m + 1
            else: r = m
        return nums[l]

4. Median of Two Sorted Arrays

Difficulty: Hard · Tags: Array, Binary Search, Divide and Conquer

Leetcode

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

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6
Approach

Binary search on the smaller array’s partition; choose i so that i + j = (m + n + 1) // 2 with A[i-1] ≤ B[j] and B[j-1] ≤ A[i].

class Solution:
    def findMedianSortedArrays(self, A, B):
        if len(A) > len(B): A, B = B, A
        m, n = len(A), len(B); half = (m + n + 1) // 2
        l, r = 0, m
        while l <= r:
            i = (l + r) // 2; j = half - i
            Al = A[i-1] if i else float('-inf')
            Ar = A[i] if i < m else float('inf')
            Bl = B[j-1] if j else float('-inf')
            Br = B[j] if j < n else float('inf')
            if Al <= Br and Bl <= Ar:
                if (m + n) % 2: return max(Al, Bl)
                return (max(Al, Bl) + min(Ar, Br)) / 2
            elif Al > Br: r = i - 1
            else: l = i + 1

Heap

215. Kth Largest Element in an Array

Difficulty: Medium · Tags: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect

Leetcode

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?

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
Approach

Min-heap of size k.

import heapq
class Solution:
    def findKthLargest(self, nums, k):
        return heapq.nlargest(k, nums)[-1]

502. IPO

Difficulty: Hard · Tags: Array, Greedy, Sorting, Heap (Priority Queue)

Leetcode

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the i^th project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Example 2:

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6

Constraints:

  • 1 <= k <= 10^5
  • 0 <= w <= 10^9
  • n == profits.length
  • n == capital.length
  • 1 <= n <= 10^5
  • 0 <= profits[i] <= 10^4
  • 0 <= capital[i] <= 10^9
Approach

Sort projects by capital. Iterate k rounds: add affordable projects to a max-heap of profits; pick the top.

import heapq
class Solution:
    def findMaximizedCapital(self, k, w, profits, capital):
        proj = sorted(zip(capital, profits))
        i = 0; h = []
        for _ in range(k):
            while i < len(proj) and proj[i][0] <= w:
                heapq.heappush(h, -proj[i][1]); i += 1
            if not h: break
            w += -heapq.heappop(h)
        return w

373. Find K Pairs with Smallest Sums

Difficulty: Medium · Tags: Array, Heap (Priority Queue)

Leetcode

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u_1, v_1), (u_2, v_2), ..., (u_k, v_k) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Constraints:

  • 1 <= nums1.length, nums2.length <= 10^5
  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1 and nums2 both are sorted in non-decreasing order.
  • 1 <= k <= 10^4
  • k <= nums1.length * nums2.length
Approach

Min-heap seeded with (nums1[i] + nums2[0], i, 0). Pop k times; after popping (i, j), push (i, j+1).

import heapq
class Solution:
    def kSmallestPairs(self, nums1, nums2, k):
        if not nums1 or not nums2: return []
        h = []
        for i in range(min(k, len(nums1))):
            heapq.heappush(h, (nums1[i] + nums2[0], i, 0))
        res = []
        while h and len(res) < k:
            _, i, j = heapq.heappop(h)
            res.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(h, (nums1[i] + nums2[j+1], i, j+1))
        return res

295. Find Median from Data Stream

Difficulty: Hard · Tags: Two Pointers, Design, Sorting, Heap (Priority Queue), Data Stream

Leetcode

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

  • -10^5 <= num <= 10^5
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 10^4 calls will be made to addNum and findMedian.

Follow up:

  • If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
  • If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Approach

Two heaps: max-heap of lower half, min-heap of upper half. Rebalance so sizes differ by ≤1.

import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negated)
        self.hi = []
    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
    def findMedian(self):
        if len(self.lo) > len(self.hi): return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Bit Manipulation

67. Add Binary

Difficulty: Easy · Tags: Math, String, Bit Manipulation, Simulation

Leetcode

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

  • 1 <= a.length, b.length <= 10^4
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.
Approach

Reverse strings; add digit-by-digit with carry.

class Solution:
    def addBinary(self, a, b):
        return bin(int(a, 2) + int(b, 2))[2:]

190. Reverse Bits

Difficulty: Easy · Tags: Divide and Conquer, Bit Manipulation

Leetcode

Reverse bits of a given 32 bits signed integer.

Example 1:

Input: n = 43261596

Output: 964176192

Explanation:

        Integer
        Binary


        43261596
        00000010100101000001111010011100


        964176192
        00111001011110000010100101000000

Example 2:

Input: n = 2147483644

Output: 1073741822

Explanation:

        Integer
        Binary


        2147483644
        01111111111111111111111111111100


        1073741822
        00111111111111111111111111111110

Constraints:

  • 0 <= n <= 2^31 - 2
  • n is even.

Follow up: If this function is called many times, how would you optimize it?

Approach

Shift result left, OR in low bit of n, shift n right, 32 times.

class Solution:
    def reverseBits(self, n):
        res = 0
        for _ in range(32):
            res = (res << 1) | (n & 1); n >>= 1
        return res

191. Number of 1 Bits

Difficulty: Easy · Tags: Divide and Conquer, Bit Manipulation

Leetcode

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

  • 1 <= n <= 2^31 - 1

Follow up: If this function is called many times, how would you optimize it?

Approach

Repeatedly n &= n - 1 (clears lowest set bit) and count.

class Solution:
    def hammingWeight(self, n):
        c = 0
        while n: n &= n - 1; c += 1
        return c

136. Single Number

Difficulty: Easy · Tags: Array, Bit Manipulation

Leetcode

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.

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.
Approach

XOR everything — pairs cancel, leaving the unique number.

from functools import reduce
from operator import xor
class Solution:
    def singleNumber(self, nums):
        return reduce(xor, nums)

137. Single Number II

Difficulty: Medium · Tags: Array, Bit Manipulation

Leetcode

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each element in nums appears exactly three times except for one element which appears once.
Approach

Two-bit state machine: ones and twos track each bit’s count mod 3.

class Solution:
    def singleNumber(self, nums):
        ones = twos = 0
        for x in nums:
            ones = (ones ^ x) & ~twos
            twos = (twos ^ x) & ~ones
        return ones

201. Bitwise AND of Numbers Range

Difficulty: Medium · Tags: Bit Manipulation

Leetcode

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

  • 0 <= left <= right <= 2^31 - 1
Approach

Common prefix of left and right: shift both right until equal, then shift back.

class Solution:
    def rangeBitwiseAnd(self, left, right):
        shift = 0
        while left < right:
            left >>= 1; right >>= 1; shift += 1
        return left << shift

Math

9. Palindrome Number

Difficulty: Easy · Tags: Math

Leetcode

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

  • -2^31 <= x <= 2^31 - 1

Follow up: Could you solve it without converting the integer to a string?

Approach

Reverse half the digits and compare; negative numbers are not palindromes.

class Solution:
    def isPalindrome(self, x):
        if x < 0 or (x % 10 == 0 and x != 0): return False
        rev = 0
        while x > rev:
            rev = rev * 10 + x % 10; x //= 10
        return x == rev or x == rev // 10

66. Plus One

Difficulty: Easy · Tags: Array, Math

Leetcode

You are given a large integer represented as an integer array digits, where each digits[i] is the i^th digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits does not contain any leading 0’s.
Approach

Walk from end carrying; if all 9s, prepend 1.

class Solution:
    def plusOne(self, digits):
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1; return digits
            digits[i] = 0
        return [1] + digits

172. Factorial Trailing Zeroes

Difficulty: Medium · Tags: Math

Leetcode

Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:

Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 10^4

Follow up: Could you write a solution that works in logarithmic time complexity?

Approach

Count factors of 5 in n!: n//5 + n//25 + n//125 + …

class Solution:
    def trailingZeroes(self, n):
        c = 0
        while n: n //= 5; c += n
        return c

69. Sqrt(x)

Difficulty: Easy · Tags: Math, Binary Search

Leetcode

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

  • 0 <= x <= 2^31 - 1
Approach

Binary search for the largest m with m*m ≤ x.

class Solution:
    def mySqrt(self, x):
        l, r = 0, x; ans = 0
        while l <= r:
            m = (l + r) // 2
            if m*m <= x: ans = m; l = m + 1
            else: r = m - 1
        return ans

50. Pow(x, n)

Difficulty: Medium · Tags: Math, Recursion

Leetcode

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

Constraints:

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31-1
  • n is an integer.
  • Either x is not zero or n > 0.
  • -10^4 <= x^n <= 10^4
Approach

Fast exponentiation by squaring; handle negative n by inverting x.

class Solution:
    def myPow(self, x, n):
        if n < 0: x, n = 1/x, -n
        res = 1.0
        while n:
            if n & 1: res *= x
            x *= x; n >>= 1
        return res

149. Max Points on a Line

Difficulty: Hard · Tags: Array, Hash Table, Math, Geometry

Leetcode

Given an array of points where points[i] = [x_i, y_i] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -10^4 <= x_i, y_i <= 10^4
  • All the points are unique.
Approach

For each anchor, count slope frequencies of all other points (use a reduced fraction key). Answer = max over anchors of (best slope count + 1).

from math import gcd
from collections import defaultdict
class Solution:
    def maxPoints(self, points):
        n = len(points)
        if n <= 2: return n
        best = 0
        for i in range(n):
            slopes = defaultdict(int)
            for j in range(n):
                if i == j: continue
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                g = gcd(dx, dy)
                if g: dx //= g; dy //= g
                if dx < 0 or (dx == 0 and dy < 0): dx, dy = -dx, -dy
                slopes[(dx, dy)] += 1
            best = max(best, max(slopes.values()) + 1)
        return best

1D DP

70. Climbing Stairs

Difficulty: Easy · Tags: Math, Dynamic Programming, Memoization

Leetcode

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?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45
Approach

Fibonacci recurrence; two rolling variables.

class Solution:
    def climbStairs(self, n):
        a, b = 1, 1
        for _ in range(n): a, b = b, a + b
        return a

198. House Robber

Difficulty: Medium · Tags: Array, Dynamic Programming

Leetcode

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
Approach

dp[i] = max(dp[i-1], dp[i-2] + nums[i]); rolling.

class Solution:
    def rob(self, nums):
        prev = cur = 0
        for x in nums:
            prev, cur = cur, max(cur, prev + x)
        return cur

139. Word Break

Difficulty: Medium · Tags: Array, Hash Table, String, Dynamic Programming, Trie, Memoization

Leetcode

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.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.
Approach

dp[i] = True if some j < i with dp[j] and s[j:i] in dict.

class Solution:
    def wordBreak(self, s, wordDict):
        words = set(wordDict); n = len(s)
        dp = [True] + [False]*n
        for i in range(1, n+1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True; break
        return dp[n]

322. Coin Change

Difficulty: Medium · Tags: Array, Dynamic Programming, Breadth-First Search

Leetcode

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.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
Approach

Unbounded knapsack: dp[a] = min(dp[a − c] + 1) over coins c. Initialize with amount+1 as infinity.

class Solution:
    def coinChange(self, coins, amount):
        INF = amount + 1
        dp = [0] + [INF]*amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a: dp[a] = min(dp[a], dp[a-c] + 1)
        return dp[amount] if dp[amount] < INF else -1

300. Longest Increasing Subsequence

Difficulty: Medium · Tags: Array, Binary Search, Dynamic Programming

Leetcode

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Approach

Patience: maintain tails. For each x, replace the first tail ≥ x using binary search; length of tails is the answer.

from bisect import bisect_left
class Solution:
    def lengthOfLIS(self, nums):
        tails = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails): tails.append(x)
            else: tails[i] = x
        return len(tails)

Multidimensional DP

120. Triangle

Difficulty: Medium · Tags: Array, Dynamic Programming

Leetcode

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -10^4 <= triangle[i][j] <= 10^4

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Approach

Bottom-up: replace each row with row[i] + min(below[i], below[i+1]).

class Solution:
    def minimumTotal(self, triangle):
        dp = triangle[-1][:]
        for r in range(len(triangle) - 2, -1, -1):
            for c in range(r + 1):
                dp[c] = triangle[r][c] + min(dp[c], dp[c+1])
        return dp[0]

64. Minimum Path Sum

Difficulty: Medium · Tags: Array, Dynamic Programming, Matrix

Leetcode

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200
Approach

dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]); can be in-place.

class Solution:
    def minPathSum(self, grid):
        R, C = len(grid), len(grid[0])
        for r in range(R):
            for c in range(C):
                if r == 0 and c == 0: continue
                up = grid[r-1][c] if r else float('inf')
                lf = grid[r][c-1] if c else float('inf')
                grid[r][c] += min(up, lf)
        return grid[-1][-1]

63. Unique Paths II

Difficulty: Medium · Tags: Array, Dynamic Programming, Matrix

Leetcode

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] is 0 or 1.
Approach

dp[r][c] = 0 if obstacle else dp[r-1][c] + dp[r][c-1].

class Solution:
    def uniquePathsWithObstacles(self, grid):
        R, C = len(grid), len(grid[0])
        dp = [0]*C
        dp[0] = 1 - grid[0][0]
        for c in range(1, C):
            dp[c] = dp[c-1] if grid[0][c] == 0 else 0
        for r in range(1, R):
            dp[0] = 0 if grid[r][0] else dp[0]
            for c in range(1, C):
                dp[c] = 0 if grid[r][c] else dp[c] + dp[c-1]
        return dp[-1]

5. Longest Palindromic Substring

Difficulty: Medium · Tags: Two Pointers, String, Dynamic Programming

Leetcode

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

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.
Approach

Expand around each center (2n−1 centers); keep best span.

class Solution:
    def longestPalindrome(self, s):
        if not s: return ""
        start = end = 0
        for i in range(len(s)):
            for l, r in ((i, i), (i, i+1)):
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    l -= 1; r += 1
                if r - l - 1 > end - start:
                    start, end = l + 1, r
        return s[start:end]

97. Interleaving String

Difficulty: Medium · Tags: String, Dynamic Programming

Leetcode

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

  • s = s_1 + s_2 + ... + s_n
  • t = t_1 + t_2 + ... + t_m
  • |n - m| <= 1
  • The interleaving is s_1 + t_1 + s_2 + t_2 + s_3 + t_3 + ... or t_1 + s_1 + t_2 + s_2 + t_3 + s_3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

Approach

dp[i][j] = True if s3[:i+j] is interleave of s1[:i] and s2[:j]. Transition from above or left depending on char match.

class Solution:
    def isInterleave(self, s1, s2, s3):
        if len(s1) + len(s2) != len(s3): return False
        dp = [False] * (len(s2) + 1); dp[0] = True
        for j in range(1, len(s2)+1):
            dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
        for i in range(1, len(s1)+1):
            dp[0] = dp[0] and s1[i-1] == s3[i-1]
            for j in range(1, len(s2)+1):
                dp[j] = ((dp[j] and s1[i-1] == s3[i+j-1]) or
                         (dp[j-1] and s2[j-1] == s3[i+j-1]))
        return dp[-1]

72. Edit Distance

Difficulty: Medium · Tags: String, Dynamic Programming

Leetcode

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

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.
Approach

Classic Levenshtein DP. dp[i][j] = match → dp[i-1][j-1], else 1 + min of replace/insert/delete.

class Solution:
    def minDistance(self, w1, w2):
        m, n = len(w1), len(w2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m+1): dp[i][0] = i
        for j in range(n+1): dp[0][j] = j
        for i in range(1, m+1):
            for j in range(1, n+1):
                if w1[i-1] == w2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
        return dp[m][n]

123. Best Time to Buy and Sell Stock III

Difficulty: Hard · Tags: Array, Dynamic Programming

Leetcode

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5
Approach

At most 2 transactions. Track buy1/sell1/buy2/sell2 in a single pass.

class Solution:
    def maxProfit(self, prices):
        b1 = b2 = float('inf'); s1 = s2 = 0
        for p in prices:
            b1 = min(b1, p); s1 = max(s1, p - b1)
            b2 = min(b2, p - s1); s2 = max(s2, p - b2)
        return s2

188. Best Time to Buy and Sell Stock IV

Difficulty: Hard · Tags: Array, Dynamic Programming

Leetcode

You are given an integer array prices where prices[i] is the price of a given stock on the i^th day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
Approach

Generalization with up to k transactions. dp[j] tracks best profit with j sells; iterate prices updating buy/sell pairs.

class Solution:
    def maxProfit(self, k, prices):
        n = len(prices)
        if n == 0 or k == 0: return 0
        if k >= n // 2:
            return sum(max(0, b-a) for a,b in zip(prices, prices[1:]))
        buy = [float('inf')]*(k+1); sell = [0]*(k+1)
        for p in prices:
            for j in range(1, k+1):
                buy[j] = min(buy[j], p - sell[j-1])
                sell[j] = max(sell[j], p - buy[j])
        return sell[k]

221. Maximal Square

Difficulty: Medium · Tags: Array, Dynamic Programming, Matrix

Leetcode

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.
Approach

dp[r][c] = side of largest square ending at (r,c). If grid is ‘1’, dp = 1 + min of three neighbors. Track max.

class Solution:
    def maximalSquare(self, matrix):
        if not matrix: return 0
        R, C = len(matrix), len(matrix[0])
        dp = [0]*(C+1); best = 0; prev = 0
        for r in range(R):
            prev = 0
            for c in range(1, C+1):
                tmp = dp[c]
                if matrix[r][c-1] == '1':
                    dp[c] = 1 + min(dp[c], dp[c-1], prev)
                    best = max(best, dp[c])
                else:
                    dp[c] = 0
                prev = tmp
        return best * best