Given an unsorted integer array nums.

Return the smallest positive integer that is not present in

nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Brute Force
public class Solution {
public int firstMissingPositive(int[] nums) {
int missing = 1;
while (true) {
boolean flag = true;
for (int num : nums) {
if (missing == num) {
flag = false;
break;
}
}
if (flag) return missing;
missing++;
}
}
}

Time Complexity -- O(n2)

Space Complexity -- O(1)

Negative Marking
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;

for (int i = 0; i < n; i++) {

if (nums[i] < 0) {

1
 nums[i] = 0;
}
}

for (int i = 0; i < n; i++) {

int val = Math.abs(nums[i]);
if (val >= 1 && val <= n) {
if (nums[val - 1] > 0) {
nums[val - 1] *= -1;
} else if (nums[val - 1] == 0) {
nums[val - 1] = -1 * (n + 1);
}
}
}

for (int i = 1; i <= n; i++) {

if (nums[i - 1] >= 0) {
return i;
}
}

return n + 1;
}
}

Time complexity: O(n), Space complexity: O(1) extra space.

Key Observations:

1.​ We're only interested in numbers from 1 to n (inclusive), where n is the length of the
array.​

2.​ If every number from 1 to n is present, the missing number is n + 1.​

3.​ The idea is to put each number in its correct index position, i.e., number 1 at index 0,
2 at index 1, ..., n at index n-1.​

✅ Code with Step-by-Step Explanation:

2
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;

// Step 1: Place each number in its correct index if it's in

range [1, n]
for (int i = 0; i < n; ) {
int val = nums[i];
// Only swap if value is in range and not already in
correct place
if (val > 0 && val <= n && nums[val - 1] != val) {
// Swap nums[i] with nums[val - 1] to place the value
in correct position
int temp = nums[val - 1];
nums[val - 1] = val;
nums[i] = temp;
} else {
// If already in correct place or not in range, move
to next index
i++;
}
}

// Step 2: Scan through the array to find the first number out
of place
for (int i = 0; i < n; i++) {
// If nums[i] != i + 1, then i + 1 is the missing number
if (nums[i] != i + 1)
return i + 1;
}

// Step 3: If all numbers are in place, return n + 1

return n + 1;
}
}

🧠 Example:
Input: [3, 4, -1, 1]
After rearranging: [1, -1, 3, 4]
Scan through:

3
 ●​ Index 0 → 1 ✅​
●​ Index 1 → -1 ❌ → So answer is 2​

Output: 2

📈 Complexity:
●​ Time: O(n) → Each number is moved at most once.​

●​ Space: O(1) extra space → Everything is done in-place.

Merge Strings Alternately -

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order,
starting with word1. If a string is longer than the other, append the additional letters onto the end of
the merged string.

Return the merged string.

Example 1:
Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1: a b c
word2: p q r
merged: a p b q c r

Example 2:
Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1: a b
word2: p q r s
merged: a p b q r s

Example 3:
Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1: a b c d
word2: p q
merged: a p b q c d

4
Explanation

Two Pointers - I
public class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder res = new StringBuilder();
int i = 0, j = 0;
while (i < word1.length() && j < word2.length()) {
res.append(word1.charAt(i++));
res.append(word2.charAt(j++));
}
res.append(word1.substring(i));
res.append(word2.substring(j));
return res.toString();
}
}

Time complexity: O(n + m), Space complexity: O(n + m), where n and m are the lengths of
word1 and word2.

One Pointer

public class Solution {

public String mergeAlternately(String word1, String word2) {
int n = word1.length(), m = word2.length();
StringBuilder res = new StringBuilder();
for (int i = 0; i < n || i < m; i++) {
if (i < n) {
res.append(word1.charAt(i));
}
if (i < m) {
res.append(word2.charAt(i));
}
}
return res.toString();
}
}

5
11. Container With Most Water
You are given an integer array height of length n. There are n vertical lines drawn such that the two
endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the
most water.

Return the maximum amount of water a container can store.

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

6
1. Brute Force

public class Solution {

public int maxArea(int[] heights) {
int res = 0;
for (int i = 0; i < heights.length; i++) {
for (int j = i + 1; j < heights.length; j++) {
res = Math.max(res, Math.min(heights[i], heights[j]) * (j - i));
}
}
return res;
}
}

Two Pointers
public class Solution {
public int maxArea(int[] heights) {
int l = 0;
int r = heights.length - 1;
int res = 0;

while (l < r) {
int area = Math.min(heights[l], heights[r]) * (r - l);
res = Math.max(res, area);
if (heights[l] <= heights[r]) {
l++;
} else {
r--;
}
}
return res;
}
}

7
Boats to Save People -
Explanation
You are given an array people where people[i] is the weight of the ith person, and an infinite number
of boats where each boat can carry a maximum weight of limit. Each boat carries at most two
people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person

Example 1:

Input: people = [1,2], limit = 3

Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3

Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5

Output: 4
Explanation: 4 boats (3), (3), (4), (5)

1. Sorting + Two Pointers

public class Solution {

public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int res = 0, l = 0, r = people.length - 1;
while (l <= r) {
int remain = limit - people[r--];
res++;
if (l <= r && remain >= people[l]) {
l++;
}
}
return res;
}
}

8
Counting Sort
public class Solution {
public int numRescueBoats(int[] people, int limit) {
int m = Arrays.stream(people).max().getAsInt();
int[] count = new int[m + 1];
for (int p : people) {
count[p]++;
}

int idx = 0, i = 1;
while (idx < people.length) {
while (count[i] == 0) {
i++;
}
people[idx++] = i;
count[i]--;
}

int res = 0, l = 0, r = people.length - 1;

while (l <= r) {
int remain = limit - people[r--];
res++;
if (l <= r && remain >= people[l]) {
l++;
}
}
return res;
}
}

Time complexity: O(n), Space complexity: O(m), where n is the size of the input array and m is
the maximum value in the array.

Contains Duplicate II -
Explanation

1. Brute Force

9
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
for (int L = 0; L < nums.length; L++) {
for (int R = L + 1; R < Math.min(nums.length, L + k + 1); R++) {
if (nums[L] == nums[R]) {
return true;
}
}
}
return false;
}
}

Time complexity: O(n × min(n, k)), Space complexity: O(1)

Hash Map
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {

if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
return true;
}
map.put(nums[i], i);
}

return false;
}
}

Time complexity: O(n), Space complexity: O(n), where n is the size of the array nums and k is the
maximum distance between two equal numbers.

Minimum Size Subarray Sum

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.

Brute Force

10
public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int res = Integer.MAX_VALUE;

for (int i = 0; i < n; i++) {

int curSum = 0, j = i;
while (j < n) {
curSum += nums[j];
if (curSum >= target) {
res = Math.min(res, j - i + 1);
break;
}
j++;
}
}

return res == Integer.MAX_VALUE ? 0 : res;

}
}

Time complexity: O(n²), Space complexity: O(1) extra space.

Sliding Window
public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int l = 0, total = 0;
int res = Integer.MAX_VALUE;

for (int r = 0; r < nums.length; r++) {

total += nums[r];
while (total >= target) {
res = Math.min(r - l + 1, res);
total -= nums[l];
l++;
}
}

return res == Integer.MAX_VALUE ? 0 : res;

}
}

Time complexity: O(n), Space complexity: O(1) extra space.

11
 Find K Closest Elements
Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array.
The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

●​ |a - x| < |b - x|, or
●​ |a - x| == |b - x| and a < b
●​

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3

Output: [1,2,3,4]

Example 2:

Input: arr = [1,1,2,3,4,5], k = 4, x = -1

Output: [1,1,2,3]

Sorting (Custom Comparator)

public class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> list = new ArrayList<>();
for (int num : arr) {
list.add(num);
}

list.sort((a, b) -> {
int diff = Math.abs(a - x) - Math.abs(b - x);
return diff == 0 ? Integer.compare(a, b) : diff;
});

List<Integer> result = list.subList(0, k);

Collections.sort(result);
return result;
}
}

Time complexity: O(n log n + k log k)

12
Space complexity: O(1) or O(n) depending on the sorting algorithm, and O(k) for the
output array.

Two Pointers
public class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int l = 0, r = arr.length - 1;
while (r - l >= k) {
if (Math.abs(x - arr[l]) <= Math.abs(x - arr[r])) {
r--;
} else {
l++;
}
}
List<Integer> result = new ArrayList<>();
for (int i = l; i <= r; i++) {
result.add(arr[i]);
}
return result;
}
}

Time complexity: O(n − k), Space complexity: O(k) for the output array.

Binary Search
public class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int l = 0, r = arr.length - k;
while (l < r) {
int m = (l + r) / 2;
if (x - arr[m] > arr[m + k] - x) {
l = m + 1;
} else {
r = m;
}
}
List<Integer> result = new ArrayList<>();
for (int i = l; i < l + k; i++) {
result.add(arr[i]);

13
 }
return result;
}
}

Time complexity: O(log(n − k) + k), Space complexity: O(k) for the output array,
where n is the size of the input array and k is the number of closest elements to find.

Minimum Window Substring

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.

Sliding Window

public class Solution {

public String minWindow(String s, String t) {
if (t.isEmpty()) return "";

Map<Character, Integer> countT = new HashMap<>();

Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
countT.put(c, countT.getOrDefault(c, 0) + 1);
}

14
 int have = 0, need = countT.size();
int[] res = {-1, -1};
int resLen = Integer.MAX_VALUE;
int l = 0;

for (int r = 0; r < s.length(); r++) {

char c = s.charAt(r);
window.put(c, window.getOrDefault(c, 0) + 1);

if (countT.containsKey(c) && window.get(c).equals(countT.get(c))) {

have++;
}

while (have == need) {

if ((r - l + 1) < resLen) {
resLen = r - l + 1;
res[0] = l;
res[1] = r;
}

char leftChar = s.charAt(l);

window.put(leftChar, window.get(leftChar) - 1);
if (countT.containsKey(leftChar) && window.get(leftChar) <
countT.get(leftChar)) {
have--;
}
l++;
}
}

return resLen == Integer.MAX_VALUE ? "" : s.substring(res[0], res[1] + 1);

}
}

Time complexity: O(n), Space complexity: O(m), where n is the length of the string s
and m is the total number of unique characters in the strings t and s.

15
Time Based Key-Value Store
Design a time-based key-value data structure that can store multiple values for the same key at
different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

●​ TimeMap() Initializes the object of the data structure.

●​ void set(String key, String value, int timestamp) Stores the key key with the value value at
the given time timestamp.
●​ String get(String key, int timestamp) Returns a value such that set was called previously, with
timestamp_prev <= timestamp. If there are multiple such values, it returns the value
associated with the largest timestamp_prev. If there are no values, it returns "".

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

public class TimeMap {

private Map<String, Map<Integer, List<String>>> keyStore;

public TimeMap() {
keyStore = new HashMap<>();
}

public void set(String key, String value, int timestamp) {

if (!keyStore.containsKey(key)) {
keyStore.put(key, new HashMap<>());
}
if (!keyStore.get(key).containsKey(timestamp)) {
keyStore.get(key).put(timestamp, new ArrayList<>());
}
keyStore.get(key).get(timestamp).add(value);
}

public String get(String key, int timestamp) {

if (!keyStore.containsKey(key)) {
return "";
}
int seen = 0;

for (int time : keyStore.get(key).keySet()) {

if (time <= timestamp) {
seen = Math.max(seen, time);

16
 }
}
if (seen == 0) return "";
int back = keyStore.get(key).get(seen).size() - 1;
return keyStore.get(key).get(seen).get(back);
}
}

Time complexity: O(1) for set(), O(n) for get().

Space complexity: O(m * n).

Binary Search (Sorted Map)

public class TimeMap {
private Map<String, TreeMap<Integer, String>> m;

public TimeMap() {
m = new HashMap<>();
}

public void set(String key, String value, int timestamp) {

m.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
}

public String get(String key, int timestamp) {

if (!m.containsKey(key)) return "";
TreeMap<Integer, String> timestamps = m.get(key);
Map.Entry<Integer, String> entry = timestamps.floorEntry(timestamp);
return entry == null ? "" : entry.getValue();
}
}

Time complexity: O(1) for set(), O(log n) for get().​

Space complexity: O(m * n), where n is the total number of values associated with a
key and m is the total number of keys.

17
Find in Mountain Array
(This problem is an interactive problem.)

You may recall that an array arr is a mountain array if and only if:

●​ arr.length >= 3
●​ There exists some i with 0 < i < arr.length - 1 such that:
●​ arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
●​ arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) ==
target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array using a
MountainArray interface:

●​ MountainArray.get(k) returns the element of the array at index k (0-indexed).

●​ MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also,
any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

Input: mountainArr = [1,2,3,4,5,3,1], target = 3

Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
Example 2:

Input: mountainArr = [0,1,2,4,2,1], target = 3

Output: -1
Explanation: 3 does not exist in the array, so we return -1.

Brute Force

/**
* // This is MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* interface MountainArray {

18
* public int get(int index) {}
* public int length() {}
*}
*/

public class Solution {

public int findInMountainArray(int target, MountainArray mountainArr) {
int n = mountainArr.length();

for (int i = 0; i < n; i++) {

if (mountainArr.get(i) == target) {
return i;
}
}

return -1;
}
}

Binary Search
/**
* // This is MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* interface MountainArray {
* public int get(int index) {}
* public int length() {}
*}
*/

public class Solution {

public int findInMountainArray(int target, MountainArray mountainArr) {
int length = mountainArr.length();

// Find Peak
int l = 1, r = length - 2, peak = 0;
while (l <= r) {
int m = (l + r) / 2;
int left = mountainArr.get(m - 1);
int mid = mountainArr.get(m);
int right = mountainArr.get(m + 1);
if (left < mid && mid < right) {
l = m + 1;

19
 } else if (left > mid && mid > right) {
r = m - 1;
} else {
peak = m;
break;
}
}

// Search left portion

l = 0;
r = peak - 1;
while (l <= r) {
int m = (l + r) / 2;
int val = mountainArr.get(m);
if (val < target) {
l = m + 1;
} else if (val > target) {
r = m - 1;
} else {
return m;
}
}

// Search right portion

l = peak;
r = length - 1;
while (l <= r) {
int m = (l + r) / 2;
int val = mountainArr.get(m);
if (val > target) {
l = m + 1;
} else if (val < target) {
r = m - 1;
} else {
return m;
}
}

return -1;
}
}

Time complexity: O(log n)

Space complexity: O(1)

20
Count Good Nodes in Binary Tree
Medium

Within a binary tree, a node x is considered good if the path from the root of the

tree to the node x contains no nodes with a value greater than the value of node
x

Given the root of a binary tree root, return the number of good nodes within the

tree.

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

Output: 3

21
 ​

Example 2:

Input: root = [1,2,-1,3,4]

Output: 4

Depth First Search

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;

22
* this.left = left;
* this.right = right;
* }
*}
*/

class Solution {

public int goodNodes(TreeNode root) {

return dfs(root, root.val);
}

private int dfs(TreeNode node, int maxVal) {

if (node == null) {
return 0;
}

int res = (node.val >= maxVal) ? 1 : 0;

maxVal = Math.max(maxVal, node.val);
res += dfs(node.left, maxVal);
res += dfs(node.right, maxVal);
return res;
}
}

Time complexity: O(n)

Space complexity: O(n)

Breadth First Search

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;

23
* this.left = left;
* this.right = right;
* }
*}
*/

public class Solution {

public int goodNodes(TreeNode root) {
int res = 0;
Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
q.offer(new Pair<>(root, Integer.MIN_VALUE));

while (!q.isEmpty()) {
Pair<TreeNode, Integer> pair = q.poll();
TreeNode node = pair.getKey();
int maxval = pair.getValue();
if (node.val >= maxval) {
res++;
}
if (node.left != null) {
q.offer(new Pair<>(node.left, Math.max(maxval, node.val)));
}
if (node.right != null) {
q.offer(new Pair<>(node.right, Math.max(maxval, node.val)));
}
}
return res;
}
}

Time complexity: O(n)​

Space complexity: O(n)

337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this
area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief
realized that all houses in this place form a binary tree. It will automatically contact the police if two
directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without
alerting the police.

24
Example 1:

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

Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

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

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

25
1. Recursion

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
*}
*/
public class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
}

int res = root.val;

if (root.left != null) {
res += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
res += rob(root.right.left) + rob(root.right.right);
}

res = Math.max(res, rob(root.left) + rob(root.right));

return res;
}
}

Time complexity: O(2ⁿ)

Space complexity: O(n) for recursion stack.

26
Dynamic Programming (Memoization)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
*}
*/
public class Solution {
private Map<TreeNode, Integer> cache;

public int rob(TreeNode root) {

cache = new HashMap<>();
cache.put(null, 0);
return dfs(root);
}

private int dfs(TreeNode root) {

if (cache.containsKey(root)) {
return cache.get(root);
}

int res = root.val;

if (root.left != null) {
res += dfs(root.left.left) + dfs(root.left.right);
}
if (root.right != null) {
res += dfs(root.right.left) + dfs(root.right.right);
}

res = Math.max(res, dfs(root.left) + dfs(root.right));

cache.put(root, res);
return res;
}
}

27
Time complexity: O(n)
Space complexity: O(n)

Dynamic Programming (Optimal)

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
*}
*/
public class Solution {
public int rob(TreeNode root) {
int[] result = dfs(root);
return Math.max(result[0], result[1]);
}

private int[] dfs(TreeNode root) {

if (root == null) {
return new int[]{0, 0};
}

int[] leftPair = dfs(root.left);

int[] rightPair = dfs(root.right);

int withRoot = root.val + leftPair[1] + rightPair[1];

int withoutRoot = Math.max(leftPair[0], leftPair[1]) +
Math.max(rightPair[0], rightPair[1]);

return new int[]{withRoot, withoutRoot};

28
 }
}
Time complexity: O(n)
Space complexity: O(n) for recursion stack.

Delete Leaves With a Given Value

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and
has the value target, it should also be deleted (you need to continue doing that until you cannot).

Example 1:

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

Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left).
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

Example 2:

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

Output: [1,3,null,null,2]

Example 3:

29
Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

Recursion (Postorder Traversal)

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
*}
*/
public class Solution {
public TreeNode removeLeafNodes(TreeNode root, int target) {
if (root == null) {
return null;
}

root.left = removeLeafNodes(root.left, target);

root.right = removeLeafNodes(root.right, target);

if (root.left == null && root.right == null && root.val == target) {

30
 return null;
}

return root;
}
}
Time complexity: O(n)
Space complexity: O(n) for recursion stack.

Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and
smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result
of this smash is:

●​ If x == y, both stones are destroyed, and

●​ If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

1. Sorting
public class Solution {
public int lastStoneWeight(int[] stones) {
List<Integer> stoneList = new ArrayList<>();
for (int stone : stones) {
stoneList.add(stone);
}

while (stoneList.size() > 1) {

Collections.sort(stoneList);
int cur = stoneList.remove(stoneList.size() - 1) -
stoneList.remove(stoneList.size() - 1);
if (cur != 0) {
stoneList.add(cur);
}

31
 }

return stoneList.isEmpty() ? 0 : stoneList.get(0);

}
}

Time complexity: O(n² log n)​

Space complexity: O(1) or O(n) depending on the sorting algorithm.

4o mini

Binary Search
public class Solution {
public int lastStoneWeight(int[] stones) {
Arrays.sort(stones);
int n = stones.length;

while (n > 1) {
int cur = stones[n - 1] - stones[n - 2];
n -= 2;
if (cur > 0) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (stones[mid] < cur) {
l = mid + 1;
} else {
r = mid;
}
}
int pos = l;
n++;
stones = Arrays.copyOf(stones, n);
for (int i = n - 1; i > pos; i--) {
stones[i] = stones[i - 1];
}
stones[pos] = cur;
}
}
return n > 0 ? stones[0] : 0;

32
 }
}

Time complexity: O(n²)

Space complexity: O(1) or O(n) depending on the sorting algorithm.

Heap
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int s : stones) {
minHeap.offer(-s);
}

while (minHeap.size() > 1) {

int first = minHeap.poll();
int second = minHeap.poll();
if (second > first) {
minHeap.offer(first - second);
}
}

minHeap.offer(0);
return Math.abs(minHeap.peek());
}
}

Time complexity: O(n log n)

Space complexity: O(n)

K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer
k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 -
y2)2).

33
You may return the answer in any order. The answer is guaranteed to be unique (except for the
order that it is in).

Input: points = [[1,3],[-2,2]], k = 1

Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2

Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

1. Sorting

34
public class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, (a, b) -> (a[0] * a[0] + a[1] * a[1]) -
(b[0] * b[0] + b[1] * b[1]));
return Arrays.copyOfRange(points, 0, k);
}
}

Min-Heap
public class Solution {
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparing(a -> a[0]));
for (int[] point : points) {
int dist = point[0] * point[0] + point[1] * point[1];
minHeap.offer(new int[]{dist, point[0], point[1]});
}

int[][] result = new int[K][2];

for (int i = 0; i < K; ++i) {
int[] point = minHeap.poll();
result[i] = new int[]{point[1], point[2]};
}
return result;
}
}

Time complexity: O(k × log n)

Space complexity: O(n)

Task Scheduler
You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each
CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order,
but there's a constraint: there has to be a gap of at least n intervals between two tasks with the
same label.

Return the minimum number of CPU intervals required to complete all tasks.

35
Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two intervals before doing A again. The same applies to
task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can
do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This
leads to idling twice between repetitions of these tasks.

Brute Force
public class Solution {
public int leastInterval(char[] tasks, int n) {
int[] count = new int[26];
for (char task : tasks) {
count[task - 'A']++;

36
 }

List<int[]> arr = new ArrayList<>();

for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
arr.add(new int[]{count[i], i});
}
}

int time = 0;
List<Integer> processed = new ArrayList<>();
while (!arr.isEmpty()) {
int maxi = -1;
for (int i = 0; i < arr.size(); i++) {
boolean ok = true;
for (int j = Math.max(0, time - n); j < time; j++) {
if (j < processed.size() && processed.get(j) == arr.get(i)[1]) {
ok = false;
break;
}
}
if (!ok) continue;
if (maxi == -1 || arr.get(maxi)[0] < arr.get(i)[0]) {
maxi = i;
}
}

time++;
int cur = -1;
if (maxi != -1) {
cur = arr.get(maxi)[1];
arr.get(maxi)[0]--;
if (arr.get(maxi)[0] == 0) {
arr.remove(maxi);
}
}
processed.add(cur);
}
return time;
}
}

37
Max-Heap
public class Solution {
public int leastInterval(char[] tasks, int n) {
int[] count = new int[26];
for (char task : tasks) {
count[task - 'A']++;
}

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

for (int cnt : count) {
if (cnt > 0) {
maxHeap.add(cnt);
}
}

int time = 0;
Queue<int[]> q = new LinkedList<>();
while (!maxHeap.isEmpty() || !q.isEmpty()) {
time++;

if (maxHeap.isEmpty()) {
time = q.peek()[1];
} else {
int cnt = maxHeap.poll() - 1;
if (cnt > 0) {
q.add(new int[]{cnt, time + n});
}
}

if (!q.isEmpty() && q.peek()[1] == time) {

maxHeap.add(q.poll()[0]);
}
}

return time;
}
}

Time complexity: O(m)

Space complexity: O(1), since we have at most 26 different characters.

38
Greedy
public class Solution {
public int leastInterval(char[] tasks, int n) {
int[] count = new int[26];
for (char task : tasks) {
count[task - 'A']++;
}

Arrays.sort(count);
int maxf = count[25];
int idle = (maxf - 1) * n;

for (int i = 24; i >= 0; i--) {

idle -= Math.min(maxf - 1, count[i]);
}
return Math.max(0, idle) + tasks.length;
}
}
Time complexity: O(m)
Space complexity: O(1), since we have at most 26 different characters,
where m is the number of tasks.

1405. Longest Happy String

A string s is called happy if it satisfies the following conditions:

●​ s only contains the letters 'a', 'b', and 'c'.

●​ s does not contain any of "aaa", "bbb", or "ccc" as a substring.
●​ s contains at most a occurrences of the letter 'a'.
●​ s contains at most b occurrences of the letter 'b'.
●​ s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple
longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

39
Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Greedy
public class Solution {
public String longestDiverseString(int a, int b, int c) {
int[] count = {a, b, c};
StringBuilder res = new StringBuilder();

int repeated = -1;

while (true) {
int maxChar = getMax(count, repeated);
if (maxChar == -1) {
break;
}
res.append((char) (maxChar + 'a'));
count[maxChar]--;

40
 if (res.length() > 1 && res.charAt(res.length() - 1)
== res.charAt(res.length() - 2)) {
repeated = maxChar;
} else {
repeated = -1;
}
}

return res.toString();
}

private int getMax(int[] count, int repeated) {

int idx = -1, maxCnt = 0;
for (int i = 0; i < 3; i++) {
if (i == repeated || count[i] == 0) {
continue;
}
if (maxCnt < count[i]) {
maxCnt = count[i];
idx = i;
}
}
return idx;
}
}

41
Time complexity: O(n)​
Space complexity: O(1) extra space, O(n) for the output
string.
4o

Greedy (Max-Heap)
public class Solution {
public String longestDiverseString(int a, int b, int c) {
StringBuilder res = new StringBuilder();
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((x, y) -> y[0] - x[0]);

if (a > 0) maxHeap.offer(new int[]{a, 'a'});

if (b > 0) maxHeap.offer(new int[]{b, 'b'});
if (c > 0) maxHeap.offer(new int[]{c, 'c'});

while (!maxHeap.isEmpty()) {
int[] first = maxHeap.poll();
if (res.length() > 1 && res.charAt(res.length() - 1) == first[1] && res.charAt(res.length() -
2) == first[1]) {
if (maxHeap.isEmpty()) break;
int[] second = maxHeap.poll();
res.append((char) second[1]);
second[0]--;
if (second[0] > 0) maxHeap.offer(second);
maxHeap.offer(first);
} else {
res.append((char) first[1]);
first[0]--;
if (first[0] > 0) maxHeap.offer(first);
}
}

return res.toString();
}
}

42
Time complexity: O(n)​
Space complexity: O(1) extra space, O(n) for the output string.

Car Pooling

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and
drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi]
indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop
them off are fromi and toi respectively. The locations are given as the number of kilometers due east
from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false
otherwise.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4

Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5

Output: true

Brute Force

43
public class Solution {

public boolean carPooling(int[][] trips, int capacity) {

Arrays.sort(trips, (a, b) -> Integer.compare(a[1], b[1]));

for (int i = 0; i < trips.length; i++) {

int curPass = trips[i][0];

for (int j = 0; j < i; j++) {

if (trips[j][2] > trips[i][1]) {

curPass += trips[j][0];

if (curPass > capacity) {

return false;

return true;

Time complexity: O(n²)​

Space complexity: O(1) or O(n), depending on the sorting algorithm.

4o

44
Min-Heap
public class Solution {

public boolean carPooling(int[][] trips, int capacity) {

Arrays.sort(trips, Comparator.comparingInt(a -> a[1]));

PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

// [end, numPassengers]

int curPass = 0;

for (int[] trip : trips) {

int numPass = trip[0], start = trip[1], end = trip[2];

while (!minHeap.isEmpty() && minHeap.peek()[0] <= start) {

curPass -= minHeap.poll()[1];

curPass += numPass;

if (curPass > capacity) {

return false;

minHeap.offer(new int[]{end, numPass});

45
 return true;

Time complexity: O(n log n)

Space complexity: O(n)

IPO
uppose 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 ith 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.

Two Heaps (Optimal)

●​ Python
●​ Java
●​ C++
●​ JavaScript

public class Solution {

public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {

PriorityQueue<Integer> minCapital = new PriorityQueue<>((a, b) -> capital[a] - capital[b]);

PriorityQueue<Integer> maxProfit = new PriorityQueue<>((a, b) -> profits[b] - profits[a]);

46
 for (int i = 0; i < capital.length; i++) {

minCapital.offer(i);

for (int i = 0; i < k; i++) {

while (!minCapital.isEmpty() && capital[minCapital.peek()] <= w) {

maxProfit.offer(minCapital.poll());

if (maxProfit.isEmpty()) {

break;

w += profits[maxProfit.poll()];

return w;

Time complexity: O(n log n)

Space complexity: O(n)

Partition to K Equal Sum Subsets

Given an integer array nums and an integer k, return true if it is possible to divide this array into k
non-empty subsets whose sums are all equal.

47
Example 1:

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

Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3

Output: false

public class Solution {

private boolean[] used;
private int target;
private int n;

public boolean canPartitionKSubsets(int[] nums, int k) {

int sum = 0;
for (int num : nums) sum += num;
if (sum % k != 0) return false;

this.target = sum / k;
this.n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n / 2; i++) {
int tmp = nums[i];
nums[i] = nums[n - i - 1];
nums[n - i - 1] = tmp;
}
used = new boolean[n];
return backtrack(nums, k, 0, 0);
}

private boolean backtrack(int[] nums, int k, int currentSum, int start) {

if (k == 0) return true;
if (currentSum == target) return backtrack(nums, k - 1, 0, 0);

for (int i = start; i < n; i++) {

if (used[i] || currentSum + nums[i] > target) continue;
used[i] = true;
if (backtrack(nums, k, currentSum + nums[i], i + 1)) return true;
used[i] = false;

48
 }
return false;
}
}

Time complexity: O(k * 2ⁿ)

Space complexity: O(n)

49