Leetcode

Question 1

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Answer 1

1. Use Map to save already seen elements
2. Iterate through nums
3. If target - nums[i] exists in Map –> return

O(n) time
O(n) space

Question 2

Valid Parentheses

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

Answer 2

1. Use Stack to push opened brackets
2. For closed – pop() (check isEmpty() first!)
3. Check if pair is valid
4. If Stack is not empty – return false else true

O(n) time
O(n) space

Question 3

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one sorted list.

Answer 3

1. Create an empty Node as head
2. while (list1 != null && list2 != null)
3. while (list1 != null)
4. while (list2 != null)
5. Return head.next

O(m + n) time
O(m + n) space

Question 4

Best Time to Buy and Sell Stock

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction.

Answer 4

1. Keep track of a min seen value
2. Compute profit for each price: price[i] - min
3. Update maxProfit

O(n) time
O(1) space

Question 5

Valid Palindrome

Given a string s, return true if it is a palindrome, or false otherwise.

Answer 5

1. while (left < right)
2. If != -> false
3. Return true

O(n) time
O(1) space

Question 6

Invert Binary Tree

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

Answer 6

1. Recursive swap(Node root)
2. If root == null return
3. Swap left and right
4. swap(root.left)
5. swap(root.right)

O(n) time
O(n) space

Question 7

Valid Anagram

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Answer 7

1. Create a char Map for each word
2. If maps are equal -> true

O(m + n) time
O(m + n) space

Question 8

Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Answer 8

1. while (left <= right)
   2 . mid = (left + right) / 2
2. Greater -> left = mid + 1
3. Less -> right = mid - 1
4. Equal -> return mid

O(log n) time
O(1) space

Question 9

Flood Fill

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Answer 9

1. Recursive recolor(int[][] image, int x, int y, int oldColor, int newColor)
2. If out of bounds or already recolored -> return
3. Change color
4. Call recolor() four times for all directions

O(n) time
O(n) space

Question 10

Lowest Common Ancestor of a Binary Search Tree

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

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

Answer 10

1. Recursive find(Node root, Node p, Node q)
2. If p and q are of different sides -> return root
3. If p == root or q == root -> return root
4. If both on the left – search left subtree
5. If both on the right – search right subtree

O(log n) time
O(lon n) space

Question 11

Balanced Binary Tree

Given a binary tree, determine if it is
height-balanced.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Answer 11

1. Recursive height(TreeNode root, int height)
2. If Math.abs(left - right) > 1 -> return -1
3. Return Math.max(left, right)

O(n) time
O(n) space

Question 12

Linked List Cycle

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

Answer 12

1. Use fast and slow pointers
2. while (fast != null && fast.next != null)
3. If fast == slow -> return true

O(n) time
O(1) space

Question 13

Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Answer 13

1. push() to first Stack
2. On pop() and peek() return from second Stack
3. If second Stack is empty – transfer elements from first to second

O(n) time for push and pop
O(n) space

Question 14

First Bad Version

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Answer 14

1. Binary search
2. int mid = left + (right - left) / 2 (not to overflow int!)
3. If mid is bad – search on the left
4. Return left

O(log n) time
O(1) space

Question 15

Ransom Note

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

Answer 15

1. Create char Map of a magazine
2. Iterate through ransomNote
3. If ransomNote[i] does not exist in Map -> false
4. Lower the counter in Map as the char was used
5. Return true

O(m + n) time
O(1) space

Question 16

Climbing Stairs

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?

Answer 16

1. Go from top to bottom
2. Recursive count(int n) with memoization
3. memo.put(1, 1); memo.put(2, 2)
4. count = count(n - 1) + count(n - 2)
5. If is in memo -> return
6. Else put in memo -> return count

O(n) time
O(n) space

Question 17

Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Answer 17

1. Create a char Map
2. If count % 2 == 0 -> maxLength += 2
3. If maxLength < s.length() -> maxLength += 1 (for cases like aca, abeba, etc.

O(n) time
O(1) space

Question 18

Reverse Linked List

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

Answer 18

Node prev = null
while (head != null) {
Node next = head.next
head.next = prev
prev = head
head = next
}

O(n) time
O(1) space

Question 19

Majority Element

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.

Answer 19

Sort and return mid

OR

1. Take first element as a candidate
2. Iterate through nums
3. If count == 0 -> candidate = nums[i]
4. If nums[i] == candidate -> count++
5. Else count--
6. Return candidate

O(n) time
O(1) space

Question 20

Add Binary

Given two binary strings a and b, return their sum as a binary string.

Answer 20

1. Two pointers from the end of each string
2. Init carry = 0
3. Iterate backwards while both pointers >= 0
4. result.append(sum % 2)
5. carry = sum / 2
6. Return result.reverse().toString()

O(n) time
O(1) space

Question 21

Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Answer 21

1. Recursive heightAndDiameter(Node root)
2. If root == null -> Pair(0, 0)
3. Call for left and right
4. maxHeight = max(left.height, right.height) + 1
5. maxDiameter = max(left.height + right.height, max(left.diameter, right.diameter)
6. Return Pair(maxHeight, maxDiameter)

O(n) time
O(n) space

Question 22

Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Answer 22

1. Fast and slow pointers
2. Return slow

O(n) time
O(1) space

Question 23

Maximum Depth of Binary Tree

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.

Answer 23

1. Recursive depth(Node root)
2. If root == null -> 0
3. Return max(left, right) + 1

O(n) time
O(n) space

Question 24

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Answer 24

1. Use Set of already seen elements
2. If seen.contains(nums[i]) -> false
3. Return true

O(n) time
O(n) space

Question 25

Maximum Subarray

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

Answer 25

1. Iterate nums: sum += nums[i]
2. If sum < nums[i] -> sum = nums[i]
3. max = max(max, sum)
4. Return max

O(n) time
O(1) space

Question 26

Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. 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 starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Answer 26

1. Use 3 while-loops with single pointer i
2. Left elements: newInterval[0] > intervals[i][1]
3. Merge: newInterval[1] >= intervals[i][0]
4. newInterval[0] = min(newInterval[0], interval[0]
5. newInterval[1] = max(newInterval[1], interval[1]
6. Rest elements: i < intervals.length

O(n) time
O(n) space

Question 27

Longest Substring Without Repeating Characters

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

Answer 27

1. Use char Map and two pointers
2. If Map contains char -> move max(get() + 1, left)
3. length = right - left + 1
4. Update max = max(length, max)
5. Move right += 1

O(n) time
O(1) space

Question 28

Evaluate Reverse Polish Notation

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.

Answer 28

1. Use Stack to push() numbers and ops results
2. pop() on ops
3. eval(int b, int a, String op)
4. Return pop()

O(n) time
O(n) space

Question 29

Three Sum

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.

Answer 29

1. Use Set to avoid duplicates
2. Sort nums
3. Iterate i = [0, N - 2]
4. Two pointers left = i + 1; right = N - 1
5. If sum == 0 -> add
6. If sum > 0 -> move right--
7. If sum < 0 -> move left++

O(n^2) time
O(n) space

Question 30

Binary Tree Level Order Traversal

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

Answer 30

1. Recursive traverse(Node root, int level, List<List<Integer>> result)
2. If root == null -> return
3. If (level >= result.size() -> add(new ArrayList<>())
4. result.get(level).add(root.val)
5. traverse(root.left, level + 1, result)
6. traverse(root.right, level + 1, result)

O(n) time
O(n) space

Question 31

01 Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Answer 31

1. Use modified BFS
2. Use int[][] array for possible movement directions
3. Keep track of visited[][] vertices
4. Add all 0 cells to Queue and mark them as visited
5. While Queue is not empty, move to all possible directions that are not visited
6. Mark them as visited and update the distance

O(m * n) time
O(m * n) space

Question 32

K Closest Point 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).

Answer 32

Sort by distance and return first k

OR

1. Use PriorityQueue as max heap
2. Add each point to PriorityQueue
3. If size > k -> poll()
4. Return all PriorityQueue elements

O(nlog k) time
O(k) space

Question 33

Clone graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Answer 33

1. Use modified DFS
2. Save cloned nodes to a Map
3. Create clone of a current Node
4. Create clones while iterating neighbors

O(n) time
O(n) space

Question 34

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

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

Answer 34

1. Use two stacks – for values and for mins
2. Init min with Integer.MAX_VALUE
3. On push() update min-stack if needed
4. If pop() == min -> pop() min-stack and update min

O(1) time
O(n) space

Question 35

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

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

Answer 35

1. Find cycles using DFS for each course
2. If neighbor vertex was already visited == 1 -> has cycle
3. If has cycle -> return false
4. Return true

O(n) time
O(n) space

Question 36

Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

0 - representing an empty cell,
1 - representing a fresh orange, or
2 - representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Answer 36

1. Use modified BFS
2. Count fresh oranges and add all rotten to a Queue
3. Traverse Queue level by level, while it is not empty and fresh > 0
4. Return time if fresh == 0 and -1 otherwise

O(m * n) time
O(m * n) space

Question 37

Number of Islands

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.

Answer 37

1. Use DFS for each 1 to color the islands
2. Return the number of used colors

O(m * n) time
O(m * n) space

Question 38

Validate Binary Search Tree

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

Answer 38

1. Recursive isBST(root, min, max)
2. If root == null -> true
3. If root.val >= max -> false
4. If root.val <= min -> false
5. Return isBST(root.left, min, root) && isBST(root.right, root, max)

O(n) time
O(n) space

Question 39

Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

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

Answer 39

1. Fill result with products of left elements of i: result[i] = left; left *= nums[i]
2. Fill result with products of right elements of i, multiplied on products of left elements: result[i] *= right; right *= nums[i];

O(n) time
O(1) space

Question 40

Coin Change

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.

Answer 40

1. Use bottom-up DP
2. Iterate from 0 to amount
3. On each step find min of all possible previous steps: Math.min(memo.get(currentAmount - coin) + 1, count)
4. Return memo.getOrDefault(amount, -1)

O(n * m) time
O(m) space

Question 41

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Answer 41

1. Use 2D-DP
2. If charAt(i) == charAt(j) -> memo[i][j] = memo[i - 1][j - 1] + 1
3. Else -> memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])
4. Return memo[N - 1, M - 1]

O(n * m) time
O(n * m) space

Question 42

Coin Change II

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

Answer 42

1. Use bottom-up DP, memo[0] = 1
2. Iterate coins
3. Iterate amount -> memo[i] += memo[i - coin]`
4. Return memo[amount]

O(n * m) time
O(m) space

Question 43

Merge Intervals

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

Answer 43

1. Sort intervals by starti
2. start = intervals[0][0]; end = intervals[0][1]
3. if end < current[0] -> add new int[] {start, end}
4. else end = max(end, current[1])
5. add new int[] {start, end}

O(nlog n) time
O(n) space

Question 44

Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 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.

Answer 44

1. Find pivot using BS
2. if nums[mid] > nums[right] -> left = mid + 1
3. Else right = mid
4. Find target in [0; pivot) or [pivot, N]

O(log n) time
O(1) space

Question 45

Lowest Common Ancestor of a Binary Tree

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

Answer 45

1. Recursive lca(root, q, p)
2. If root == null || root == q || root == p -> root
3. Go left and right
4. If both left and right exist -> root
5. Else -> either left of right

O(n) time
O(n) space

Question 46

Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order

Answer 46

1. Recursive backtrack b(nums, permutation, result)
2. If permutation.size() == nums.length -> result.add()
3. iterate nums
4. If !permutation.contains(num) -> b()

O(n * n!) time
O(n) space

Question 47

Combination Sum

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.

Answer 47

1. Recursive backtrack b(nums, permutation, remains, start, result)
2. if remains == 0 -> result.add()
3. If remains < 0 -> return
4. Iterate nums from start
5. b(nums, newPermutation, remains - nums[i], i, result)

O(2^n) time
O(2^n) space

Question 48

Accounts Merge

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Answer 48

1. Create adjList
2. Create namesMap for each email
3. Perform DFS to mark graph components
4. Each component is a separate account

O(nlog n) time
O(n) space

Question 49

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:

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

Answer 49

1. Create class Node(String value, int timestamp)
2. Create inner Map<String, List<Node>>
3. Use BS to find Node in List

O(log n) time
O(n) space

Question 50

In-place Quick Sort

Given an array nums sort it in-place.

Answer 50

1. Use recursive quickSort(int[] nums, int left, int right)
2. If left >= right -> return
3. l = left; r = right; pivot = (l + r) / 2
4. If nums[l] < pivot -> l++
5. If nums[r] > pivot -> r--
6. Else swap(), l++, r--
7. quickSort(left, r)
8. quickSort(l, right)

O(n logn) time
O(log n) space

Question 51

Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

Answer 51

Use Counting Sort

OR

1. Use Dutch Flag Algo
2. red = 0; white = 0; blue = N -1
3. while (white <= blue)
4. If nums[white] == WHITE -> white++
5. If nums[white] == RED -> swap(); white++; red++
6. If nums[white] == BLUE -> swap(); blue--

O(n) time
O(1) space

Question 52

Word Search

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.

Answer 52

1. Use modified DFS for each board[i][j] = charAt(0)
2. If pointer == word.length() -> return true
3. If charAt(pointer) != board[x][y] -> continue
4. Else add neighbors and pointer++
5. If visited[x][y] == 1 -> visited[x][y] = 0; pointer--
6. Return false

O(3^word.length()) time
O(m * n) space

Question 53

Roman to Integer

Given a roman numeral, convert it to an integer.

Answer 53

1. Create Map of roman to integer conversions
2. Iterate roman
3. If prev < current -> result -= prev
4. Else -> result +=prev
5. Update prev = current
6. Return result + prev

O(n) time
O(1) space

Question 54

Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Answer 54

Use stack for each string and compare stacks

OR

1. Run two pointers from the end of the strings
2. while (i >= 0 || j >= 0)
3. Use i = skip(String s, int i) to skip characters
4. If charAt(i) != charAt(j) -> return false
5. If (i >= 0 && j < 0) || (j >= 0 && i < 0) -> return false
6. Return true

O(n + m) time
O(1) space

Question 55

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Answer 55

1. Use recursive isSame(p, q)
2. If both null -> return true
3. If one null -> return false
4. If not equal -> return false
5. Return isSame(p.left, q.left) && isSame(p.right, q.right)

O(n) time
O(n) space

Question 56

Palindrom Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Answer 56

Find mid, while pushing slow to Stack. Compare second half with Stack

OR

1. Find mid
2. Reverse from mid, new secondHalfHead = prev
3. Compare while (secondHalfHead != null)

O(n) time
O(1) space

Question 57

Move Zeroes

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Answer 57

1. Use two pointers zero = 0; nonZero = 0
2. Move them in a Dutch Flag fashion and swap()

O(n) time
O(1) space

Question 58

Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

Answer 58

1. Use two recursive functions: isSubtree(root, subRoot) and isEqual
2. If root == null -> return false
3. If isEqual(root, subRoot) -> return true
4. Return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)

O(m * n) time
O(h2) space

Question 59

Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Answer 59

1. Use DP
2. dp[i] = dp[i / 2] + (i % 2)
3. For even numbers number of 1 in N and N/2 is the same
4. For odd numbers add one more 1

O(n) time
O(n) space

Question 60

Symmetric Tree

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

Answer 60

1. Use recursive isMirror(left, right)
2. Return isMirror(left.left, right.right) && isMirror(left.right, right.left)

O(n) time
O(log n) space

Question 61

Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Answer 61

1. Use two pointers left = 0; right = N -1
2. Fill new array squares from the end

O(n) time
O(n) space

Question 62

Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Answer 62

1. Use recursive toBST(nums, left, right)
2. If left > right -> return
3. root = nums[mid]
4. root.left = toBST(nums, left, mid - 1)
5. root.right = toBST(nums, mid + 1, right)

O(n) time
O(log n) space

Question 63

Longest Common Prefix

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

Answer 63

Sort array and compare first and last string

OR
1. Get first string
2. Compare i‘th letter for all the strings
3. If != -> return prefix
4. Return prefix

O(m * n) time
O(m) space

Question 64

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Answer 64

1. Use recursive backtrack(String prefix, int opened, int closed, int max, List<String> result)
2. If prefix.length() == max * 2 -> add() and return
3. If opened < max -> backtrack(prefix + "(", opened + 1, ...)
4. If opened > closed -> backtrack(prefix + ")", opened, closed + 1, ...)

O(2^2n) time
O(n) space

Question 65

Binary Tree Right Side View

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.

Answer 65

1. Use level-by-level BST
2. On each level take last Queue element

O(n) time
O(n) space

Question 66

Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Answer 66

1. Use two pointers
2. while (left < right) -> swap()

O(n) time
O(1) space

Question 67

One Edit Distance

Given two strings first and second, determine if they are both one edit distance apart.

Answer 67

1. Let first to be the shortest
2. If second.length - first.length > 1 -> return false
3. Use two pointers
4. If f.charAt(i) == s.charAt(j) -> move pointers
5. Else -> if hasEdit -> return false else hasEdit = true
6. If f.length() == s.length() -> move pointers
7. Else move only j
8. Return true

O(n) time
O(1) space

Question 68

Letter Combinations of a Phone Number

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.

Answer 68

1. Use recursive backtrack(String digits, String prefix, int current, List<String> result)
2. If prefix.length() == digits.length() -> add()` and return
3. Run backtrack(digits, prefix + letter, current + 1, result) for each letter on a current button

O(4^n) time
O(4^n) space

Question 69

Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets.

Answer 69

1. Use recursive backtrack(int[] nums, int start, List<Integer> subset, List<List<Integer>> result)
2. add()
3. For each nums[i] starting from start -> backtrack(i + 1)

O(2^n) time
O(2^n) space

Question 70

Spiral Matrix

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

Answer 70

1. while (rowStart <= rowEnd && colStart <= colEnd)
2. switch (direction)
3. direction = (direction + 1) % 4

O(m * n) time
O(m * n) space

Question 71

Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid.

Answer 71

1. Use Set to store seen positions
2. If board[i][j] == '.' -> skip
3. If !seen.add(cell + " in row " + i) -> return false
4. If !seen.add(cell + " in col " + j) -> return false
5. If !seen.add(cell + " in square " + i/3 + ":" + j/3) -> return false
6. Return true

O(m * n) time
O(m * n) space

Question 72

Add Two Numbers

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.

Answer 72

1. Create empty head and current = head
2. while (first != null || second != null)
3. sum += carry + first.val + second.val
4. current.next = Node(sum % 10)
5. carry = sum / 10
6. If carry != 0 -> current.next = Node(1)
7. Return head

O(n) time
O(n) space

Question 73

Remove Nth Node From End of List

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

Answer 73

1. Use fast and slow pointers
2. Move fast n times
3. If fast == null -> return head.next (head deletion)
4. while (fast.next != null) -> move both pointers
5. slow.next = slow.next.next
6. Return head

O(n) time
O(1) space

Question 74

Implement Trie

• void insert(String word)
• boolean search(String word)
• boolean startsWith(String prefix)

Answer 74

1. Create internal Node(Map<Character, Integer> children, boolean isTerminal)
2. Insert each word character as a Node
3. While searching if next == null -> return false
4. Else return current.isTerminalfor search() or just true for startsWith()

O(n) time
O(n) space

Question 75

Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• void addWord(word)
• boolean search(word) – word may contain dots '.' where dots can be matched with any letter

Answer 75

1. Use recursive search(String word, int start, Node current)
2. If start == word.length() -> return current.isTerminal
3. If word[c] == '.' -> for each current.childen run search(i + 1)

O(n) time for add() and O(alphabet^n) for search()
O(n) space

Question 76

Group Anagrams

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

Answer 76

1. Either sortHash() or countHash() each str
2. For countHash() use int[26] and int[c - 'a]++
3. Use hashes as keys for a Map
4. Return new ArrayList<>(map.values())

O(n * klog k) time
O(n) space

Question 77

Longest Palindromic Substring

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

Answer 77

1. Use 2D-DP with left = [N-1; 0] and right = [left; N - 1]
2. If charAt(left) != charAt(right) -> continue
3. currentLength = right - left + 1
4. If currentLength <= 2 (“a”, “aa”) or dp[left + 1][right - 1] == 1 -> dp[left][right] = 1
5. Update maxLength if needed -> from = left; to = right
6. Return substring(from, to + 1)

O(n^2) time
O(n^2) space

Question 78

Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...], determine if a person could attend all meetings.

Answer 78

1. Sort intervals by meeting start time
2. Iterate. If intervals[i].start < intervals[i - 1].end -> return false
3. Return true

O(nlog n) time
O(1) space

Question 79

Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Answer 79

1. Use recursive backtrack(int[] nums, int[] used, List<Integer> tmp, List<List<Integer>> result)
2. If tmp.size() == nums.length -> add() and return
3. If used[i] or i > 0 && nums[i] = nums[i - 1] && !used[i - 1] -> continue
4. tmp.add(nums[i]); used[i] = 1; backtrack(); tmp.remove(N - 1); used[i] = 0

O(n!) time
O(n!) space

Question 80

Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

Answer 80

1. Use recursive backtrack(int[] nums, List<Integer> tmp, int start, List<List<Integer>> result)
2. add()
3. If i > start && nums[i] == nums[i - 1] -> continue
4. tmp.add(nums[i]); backtrack(i + 1); tmp.remove(N - 1)

O(2^n) time
O(2^n) space

Question 81

Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Answer 81

1. Use recursive backtrack(int[] candidates, int start, List<Integer> tmp, int remains, List<List<Integer> result)
2. If remains < 0 -> return
3. If remains == 0 -> add() and return
4. if i > start && candidates[i] == candidates[i - 1] -> continue
5. tmp.add(nums[i]); backtrack(i + 1); tmp.remove(N - 1)

O(2^n) time
O(2^n) space

Question 82

Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p’s anagrams in s.

Answer 82

1. If anagram.length() > input.length() -> return
2. Use two pointers to mark window
3. Move right up to anagram.length(), filling two freq maps
4. If equal -> positions.add(0)
5. Move left and right up to input.length()
6. windowMap[leftChar -'a]–`
7. windowMap[rightChar - 'a[]++
8. If equal -> positions.add(left)
9. Return positions

O(n) time
O(1) space

Question 83

Maximum Width of Binary Tree

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

Answer 83

1. Use level-by-level BFS
2. Save Pair(index, node) in Deque
3. leftIndex = 2 * parent.index
4. rightIndex = 2 * parent.index + 1
5. On each level compute width = deque.peekLast().index - deque.peekFirst().index + 1
6. Update maxWidth if needed

O(n) time
O(n) space

Question 84

Word Break

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.

Answer 84

1. Use recursive backtrack(String s, List<String> wordDict, Set<String> failedChecks)
2. If s.isEmpty() -> return true`
3. If failedChecks.contains(s) -> return false
4. For each word -> canBeSegmented = s.startsWith(word) && backtrack(s.substring(word.length), wordDict, failedChecks)
5. Return false

O(n^3) time
O(n) space

Question 85

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

Answer 85

1. Use maxHeap = new PriorityQueue(compare(s2, s1))
2. Add all stones to maxHeap
3. while (maxHead.size() > 1)
4. if first != second -> maxHeap.offer(first - second)
5. Return maxHeap.isEmpty() ? 0 : maxHeap.poll()

O(n logn) time
O(n) space

Question 86

Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Answer 86

1. Use minHeap = new PriorityQueue(compare(n1, n2))
2. minHeap.offer(val)
3. If minHeap.size() > k -> minHeap.poll()
4. Return minHeap.peek()

O(n logk) time
O(k) space

Question 87

Path Sum

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.

Answer 87

1. Use recursive hasPath(root, remains)
2. If root == null -> return false
3. remains -= root.val
4. If root.left == null && root.right == null -> return remains == 0
5. Return hasPath(left, remains) || hasPath(right, remains)

O(n) time
O(h) space

Question 88

Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum.

Answer 88

1. Use recursive backtrack(Node root, List<Integer> currentPath, int remains, List<List<Integer>> result)
2. If root == null -> return false
3. currentPath.add(root.val)
4. If root.right == null && root.left == null && remains == root.val -> add()
5. Else backtrack(left, remains - root.val); backtrack(right, remains - root.val)
6. currentPath.remove(N - 1)

O(n) time
O(n) space

Question 89

Path Sum III

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Answer 89

1. Use recursive pathSum(Node root, long currentSum, int targetSum, Map<Long, Integer> memo)
2. If root == null -> return 0
3. currentSum += root.val
4. currentPath = currentSum == targetSum ? 1 : 0
5. prevPaths = memo.getOrDefault(currentSum - targetSum, 0)
6. memo.merge(currentSum, 1, Integer::sum)
7. result = currentPath + prevPaths + pathSum(left) + pathSum(right)
8. memo.merge(currentSum, -1, Integer::sum)
9. Return result

O(n) time
O(n) space

Question 90

Subarray Sum Equals K

Given an array of integers nums and an integer targetSum, return the total number of subarrays whose sum equals to targetSum.

Answer 90

1. Use Map to store prefix sum frequencies
2. Iterate nums
3. currentSubarray = currentSum == targetSum ? 1 : 0
4. prevSubarrays = map.getOrDefault(currentSum - targetSum, 0)
5. count += currentSubarray + prevSubarrays
6. map.merge(currentSum, 1, Integer::sum)
7. Return count

O(n) time
O(n) space

Question 91

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Answer 91

Use minHeap

OR

1. Create a freqMap
2. Put keys in List<Integer>[] frequencyBuckets with i = value
3. Iterate frequencyBuckets from the end to get the most frequent elements

O(n) time
O(n) space

Question 92

Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Answer 92

1. Use minHeap of maxHeap
2. Create a freqMap and put its entries in the heap
3. If using minHeap -> result.add(0, poll()) because it should be sorted from highest to lowest frequency

O(n logk) time
O(n + k) space

Question 93

Longest Consecutive Sequence

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.

Answer 93

1. Add nums to a Set to get O(1) element search time
2. Iterate numsSet
3. If contains(num - 1) -> continue
4. while (contains(num + 1)) count++
5. Update max if needed
6. Return max

O(n) time
O(n) space

Question 94

Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Answer 94

1. Use Stack to store previous indicies
2. Iterate temperatures
3. while (!stack.isEmpty() && t[stack.peek()] < t[current]
4. prev = stack.pop()
5. result[prev] = current - prev
6. stack.push(current)
7. Return result

O(n) time
O(n) space

Question 95

Reorder List

You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Answer 95

1. Find mid and remove it from the first list: prev.next = null
2. Reverse second list
3. Merge two lists together

O(n) time
O(1) space

Question 96

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.

Answer 96

1. Use two pointers
2. space = Math.min(height[left], height[right]) * (right - left)
3. If height[left] < height[right] -> move left++
4. Else -> move right--
5. Return maxSpace

O(n) time
O(1) space

Question 97

Search a 2D Matrix

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.

Answer 97

Use binary search twice: to find a row and to find a target in a row

O(log n + log m) time
O(1) space

Question 98

Max Area of Island

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Answer 98

Use DFS to find graph components

O(n) time
O(n) space

Question 99

Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Answer 99

1. Create frequencyMap and put all frequencies to maxHeap
2. Create cooldownsMap
3. while (!maxHeap.isEmpty() || cooldownsMap.isEmpty)
4. If cooldownsMap.contains(currentTime - n - 1) -> remove() and put back to maxHeap
5. If !maxHeap.isEmpty() -> poll()
6. execLeft = currentTask - 1
7. If execLeft > 0 -> cooldownsMap.put(currentTime, currentTask)
8. currentTIme++
9. Return currentTime

O(nlog n) time
O(n) space

Question 100

Reorganize String

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Answer 100

1. Create frequencyMap and put all entries to maxHeap
2. while (maxHeap.size() > 1)
3. poll() two characters and append to sb
4. If freq > 1 -> offer(freq - 1)
5. If !maxHeap.isEmpty() -> if freq > 1 -> return ""
6. Else -> append to sb
7. Return sb.toString()

O(n) time
O(1) space

Question 101

Odd Even Linked List

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Answer 101

1. odd = head; even = head.next; evenHead = even
2. while (even != null && even.next != null)
3. odd.next = odd.next.next
4. even.next = even.next.next
5. odd = odd.next
6. even = even.next
7. In the end odd.next = evenHead
8. Return head

O(n) time
O(1) space

Question 102

Pacific Atlantic Water Flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Answer 102

1. Run DFS with pacific[][] for all cells on top and left borders
2. Run DFS with atlantic[][] for all cells on bottom and right borders
3. Visit cells with heights[nextRow][nextCol] >= heights[curCol][curRow]
4. If cell marked as visited in both pacific and atlantic -> add()
5. Return result

O(m * n) time
O(m * n) space

Question 103

Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n 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.

Answer 103

1. Use modified BS
2. If nums[mid] > nums[right] -> left = mid + 1
3. Else -> right = mid
4. Return nums[left]

O(log n) time
O(1) space

Question 104

Rotate Image

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.

Answer 104

1. Transpose matrix: for [0; N) - for [0; i)
2. Flip columns: for [0; N) - for [0; M / 2)

O(n * m) time
O(1) space

Question 105

Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Answer 105

1. Use two pointers left = 0; right = 0
2. Add s[right] to frequencyMap
3. Update mostFrequentCharFrequency
4. If right - left + 1 - mostFrequentCharFrequency > k -> decrement s[left] frequency and move left++
5. Update maxLength
6. Move right

O(n) time
O(1) space

Question 106

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Answer 106

1. Build two frequencyMaps, while forming a window of size s1.length()
2. If Arrays.equals() -> return true
3. Move window, increasing windowFreq[s2[right]]++ and decreasing windowFreq[s2[left]]--
4. If Arrays.equals() -> return true
5. Return false

O(n) time
O(1) space

Question 107

Rotate List

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

Answer 107

1. Use slow and fast runners
2. Compute length with fast runner – old tail
3. rotations = rotations % length
4. If rotations == 0 -> return head
5. Move slow up to i < length - 1 - rotations – new tail
6. newHead = slow.next
7. slow.next = null
8. fast.next = head
9. Return newHead

O(n) time
O(1) space

Question 108

Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Answer 108

1. Use BS from 1 to either Integer.MAX_VALUE or max(piles)
2. Use canEatAll() for each mid
3. Iterate piles: time += pile / speed + (pile % speed == 0) ? 0 : 1
4. If time > h -> return false

O(n log(Integer.MAX_VALUE)) time
O(1) space

Question 109

Maximum Candies Allocated to K Children

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Answer 109

1. Use BS from 0 to either Integer.MAX_VALUE or max(candies)
2. Use canAllocateToEverybody() for each mid
3. Iterate candies: total += pile / candiesPerChild
4. If total >= k -> return true

O(n log(Integer.MAX_VALUE)) time
O(1) space

Question 110

Surrounded Regions

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Answer 110

1. Use DFS to find graph components, starting from O
2. Save component as surrounded if it has no border connections
3. Iterate visited again and flip surrounded components to X

O(m * n) time
O(m * n) space

Question 111

Course Schedule II

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

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

Answer 111

1. Build adjacency list
2. Run DFS to find cycles
3. Push vertices to path stack if visited[current] == 1
4. Return reversed stack

O(n) time
O(n) space

Question 112

Copy List with Random Pointer

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. Return the head of the copied linked list.

Answer 112

1. Iterate original list, create a copy of each node and add it to the Map
2. Create a new list with copied nodes

O(n) time
O(n) space

Question 113

Rotate array

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

Answer 113

Use tmp[(i + k) % tmp.length] = nums[i]

OR

1. k = k % nums.length
2. Reverse [0; nums.length - 1]
3. Reverse [0; k - 1]
4. Reverse [k; nums.length - 1]

O(n) time
O(1) space

Question 114

Binary Tree Inorder Traversal

Answer 114

t(left); add(); t(right);

OR

1. while (!stack.isEmpty() || root != null)
2. If root != null -> push(); root = root.left
3. Else -> root = poll(); add(); root = root.right

O(n) time
O(h) space

Question 115

Binary Tree Preorder Traversal

Answer 115

add(); t(left); t(right);

OR

1. while (!stack.isEmpty() || root != null)
2. If root != null -> add(); push(); root = root.left
3. Else -> root = poll(); root = root.right

O(n) time
O(h) space

Question 116

Binary Tree Postorder Traversal

Answer 116

t(left); t(right); add();

OR

1. Use two Stack
2. push(root)
3. while (!stack.isEmpty())
4. out.push();
5. If root.left != null -> push(root.left)
6. If root.right != null -> push(root.right)
7. Reverse out

O(n) time
O(h) space

Question 117

Kth Smallest Element in a BST

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

Answer 117

1. Use iterative inorder traversal
2. If --k == 0 -> return root.val

O(h + k) time
O(h) space

Question 118

Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (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

Answer 118

1. hasNext() -> return !stack.isEmpty() || current != null
2. next() -> iterative inorder traversal with while (current != null) loop

O(1) on average time
O(h) space

Question 119

Construct Binary Tree from Preorder and Inorder Traversal

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.

Answer 119

1. Convert inorder to value-to-index Map
2. Init preorderRootIdx = 0
3. Use recursive toTree(preorder, left, right)
4. If left > right -> return null
5. Node root = new Node(preorder[preorderRootIdx++])
6. root.left = toTree(preorder, left, map.get(root.val) -1)
7. root.right = toTree(preorder, map.get(root.val) + 1, right)
8. Return root

O(n) time
O(n) space

Question 120

Set Matrix Zeroes

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

Answer 120

Use two Set to store zeroed rows and cols

OR

1. Init two flags isFirstRowZeroed and isFirstColZeroed
2. Iterate matrix from i = 1; j = 1 and use first col and row cells to mark zeroed ones
3. Iterate matrix again to set zeroes
4. If flags from (1) are true -> set zeroes in first row and/or col

O(m * n) time
O(1) space

Question 121

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Answer 121

1. Create dummy node
2. Start from the current = head and prev = dummy
3. while (current != null && current.next != null)
4. Relink, updating current and prev
5. Return dummy.next

O(n) time
O(1) space

Question 122

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Answer 122

1. Use recursive quickSelect(nums, left, right, k)
2. If partition == k - 1 -> return nums[partition]`
3. If partition > k - 1 -> return quickSelect(nums, left, partition - 1, k)
4. Else -> return quickSelect(nums, partition + 1, right, k)
5. Use partition(nums, left, right)
6. pivot = nums[right]; pivotPointer = left
7. Iterate [left; right)
8. If nums[i] > pivot -> swap(i, pivotPointer); pivotPointer++
9. swap(right, pivotPointer)
10. Return pivotPointer

O(n) time on average // n/2 + n/4 + ...
O(n) space

Question 123

3Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

Answer 123

1. Use three pointers
2. i = [0; N - 2); left = i + 1; right = N - 1
3. If abs(sum - target) < minDiff -> update minDiff and closestSum
4. Return closestSum

O(n) time
O(1) space

Question 124

Decode String

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

Answer 124

1. Use two stacks: numsStack and valuesStack
2. Init currentNum = 0 and valuesStack.push(new StringBuilder())
3. If digit -> currentNum = currentNum * 10 + digit
4. If [ -> valuesStack.push(new StringBuilder); numsStack.push(currentNum); currentNum = 0
5. If ] -> valuesStack.peek().append(newValue)
6. Else -> valuesStack.peek().append(c)
7. Return valuesStack.pop().toString()

O(n) time
O(n) space

Question 125

Minimum Height Trees

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs’ root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Answer 125

1. Build adjList
2. Find all leaves: adjList.get(i).size() == 1
3. while (N > 2)
4. Remove all leaves
5. If adjList.get(i).size() == 1 -> newLeaves.add(i)
6. N -= leaves
7. leaves = newLeaves
8. Return leaves

O(n) time
O(n) space

Question 126

Contiguous Array

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Answer 126

1. Use Map<Integer, Integer> prefixSum
2. sum += nums[i] == 0 ? -1 : 1
3. If sum ==0 -> maxLength = i + 1
4. If prefixSum.containsKey(sum) -> maxLength = max(maxLength, i - prefixSum.get(sum)
5. Else -> prefixSum.put(sum, i)
6. Return maxLength

O(n) time
O(n) space

Question 127

Maximum Size Subarray Sum Equals K

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Answer 127

1. Use Map<Integer, Integer> prefixSum
2. sum += nums[i]
3. If sum == k -> maxLength = i + 1
4. If prefixSum.containsKey(sum - k) -> maxLength = max(maxLength, i - prefixSum(sum - k)
5. Else -> prefixSum.put(sum, i)
6. Return maxLength

O(n) time
O(n) space

Question 128

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

Answer 128

Use maxHeap

OR

1. Use BS for [0; N - k]
2. If x > (arr[mid] + arr[mid + k]) / 2.0 -> left = mid + 1
3. Else -> right = mid
4. Return [left; left + k)

O(log n) time
O(k) space

Question 129

Asteroid Collision

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Answer 129

1. Use Stack
2. If asteroid > 0 -> push()
3. Else
4. While !isEmpty && peek() > 0 && peek() < -asteroid -> pop()
5. If isEmpty || peek() < 0 -> push()
6. If peek() == -asteroid -> pop()
7. Return reversed Stack

O(n) time
O(n) space

Question 130

Merge k Sorted Lists

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.

Answer 130

1. Use minHeap of roots
2. Init Node dummy; Node current = dummy
3. current.next = minHeap.poll()
4. current = current.next
5. If current.next != null -> minHeap.offer()
6. Return dummy.next

O(nlog k) time
O(k) space

Question 131

LRU Cache

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

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

Answer 131

1. Use Map<Integer, Node> keyToNode
2. Implement doubly-linked list, using dummyHead and dummyTail
3. On each “touch” remove() node and addToHead()
4. If capacity == size() -> removeTail()

O(1) time
O(n) space

Question 132

Binary Tree Zigzag Level Order Traversal

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

Answer 132

1. Use BST for level traversal
2. On each level switch isLeft = !isLeft to change direction
3. If isLeft -> add(val)
4. Else -> add(0, val)

O(n) time
O(n) space

Question 133

All Nodes Distance K in Binary Tree

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

Answer 133

1. Build Map<Node, Node> nodeToParent to be able to treat the tree as a graph
2. Use BFS for level traversal (don’t forget Set<Node> visited)
3. If level == k -> return Queue with all the nodes from this level
4. level++
5. If visited.add() -> offer left, right and parent
6. Return List.of()

O(n) time
O(n) space

Question 134

All Paths From Source to Target

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Answer 134

1. Use recursive dfs(graph, start, currentPath, result)
2. If start == graph.length - 1 -> add() and return
3. Run dfs for all children

O(2^n) time
O(2^n) space

Question 135

Palindrome Partitioning

Given a string s, partition s such that every
substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Answer 135

1. Use recursive backtrack(s, start, currentPartition, result)
2. If start == s.length -> add() and return
3. For end = [start; length)
4. If !isPalindrome -> continue
5. backtrack(s, end + 1, currentPartition.add(s.substring(start, end + 1)))

O(2^n) time
O(2^n) space

Question 136

Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

Answer 136

1. Use recursive backtrack(nums, start, currentCombination, k, result)
2. If size() == k -> add() and return
3. backtrack(nums, start + 1)

O(2^n) time
O(k) space

Question 137

Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Answer 137

1. Use recursive backtrack(nums, start, currentCombination, remains, k, result)
2. If remains < 0 -> return
3. If size() == k && remains ==0 -> add() and return
4. backtrack(nums, start + 1)

O(2^9) time
O(k) space

Question 138

Target Sum

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Answer 138

1. Use recursive count(nums, start, currentSum, targetSum, memo)
2. If start == length() && current == target -> return 1 else 0
3. Check and add to memo: start + ":" + current, because with negative numbers we can have the same sum on different steps
4. Return count(+) + count(-)

O(target * n) time
O(target * n) space

Question 139

Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

Answer 139

1. Use recursive count(nums, remains, memo)
2. If remains < 0 -> return 0
3. If remains == 0 -> return 1
4. Check and add to memo: remains
5. For each nums -> count(remains - num)
6. Return count

O(target * n) time
O(target * n) space

If negative numbers are allowed, we should limit the max length because of possible loops. We also should use length + remains as a key, because we can have the same sum on different steps.

Question 140

Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Answer 140

1. Sort by start
2. nonOverlappingIntervalscount = 1
3. If current.start >= end -> end = current.end; count++
4. Else -> end = min(end, current.end)`
5. Return length() - count

O(nlog n) time
O(1) space

Question 141

Count Good Nodes in Binary Tree

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Answer 141

1. Use recursive count(root, max)
2. If root == null -> return 0
3. Update max
4. current = root.val >= max ? 1 : 0
5. Return current + left + right

O(n) time
O(h) space

Question 142

Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Answer 142

1. Create starts and ends array and sort them
2. Use two pointers startPointer and endPointer
3. while (startPointer < starts.length())
4. If starts[s] < ends[e] -> busyCount++; s++
5. Else -> busyCount--; e++
6. Update maxCount
7. Return maxCount

O(nlog n) time
O(n) space

Question 143

Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Answer 143

1. Use two pointers
2. while (f < first.length() && s < second.length())
3. If firstInterval.start <= secondInterval.end && secondInterval.start <= firstInterval.end -> add(max, min)
4. If firstInterval.end <= secondInterval.end -> f++
5. Else -> s++
6. Return intersections

O(n) time
O(n) space

Question 144

Sum Root to Leaf Numbers

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.

Answer 144

1. Use recursive sum(root, sum)
2. If root == null -> return 0
3. sum = sum * 10 + root.val
4. If left == null && right == null -> return sum
5. Return sum(left) + sum(right)

O(n) time
O(h) space

Question 145

Remove Duplicates from Sorted Array

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.

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.

Answer 145

1. Iterate [1; N)
2. If nums[i] != nums[i - 1] -> nums[pointer++] = nums[i]
3. Return pointer

O(n) time
O(1) space

Question 146

Merge Sorted Array

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.

Answer 146

1. Use three pointers, iterating backwards: first, second and result
2. while (second >= 0)
3. If first >= 0 && nums1[first] >= nums2[second] -> nums1[result--] = nums1[first--]
4. Else -> nums1[result--] = nums2[second--]

O(n) time
O(1) space

Question 147

Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Answer 147

1. Use Merge Sort
2. Recursive sort(root)
3. mid = findMid(root)
4. left = sort(root)
5. right = sort(mid)
6. Return merge(left, right)

O(nlog n) time
O(log n) space

Question 148

Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value:

• +
• -
• *
• /

Answer 148

1. Use Stack
2. prevOperator = '+'
3. If isDigit() -> currentVal = currentVal * 10 + currentChar
4. Else -> eval(); currentVal = 0; prevOperator = currentChar
5. eval() the last integer in the expression
6. eval(): + -> push(currentValue); - -> push(-currentValue); * -> push(pop() * currentValue)
7. Sum up elements in the Stack

O(n) time
O(n) space

Question 149

Basic Calculator

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

• +
• -
• (
• )

Answer 149

1. Use Stack
2. sign = 1
3. If isDigit() -> currentVal = currentVal * 10 + currentChar
4. Else -> result += currentVal * sign
5. If + -> sign = 1
6. If - -> sign = 0
7. If ( -> push(result); push(sign); result = 0; sign = 1
8. If ) -> result = result * pop() + pop()
9. Return result

O(n) time
O(n) space

Question 150

String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

Answer 150

1. Check if s is empty
2. Trim whitespaces
3. Check if s is empty
4. Check +/- sign
5. Iterate result = result * 10 + currentChar
6. Check for overflow
7. Return (int) result * sign

O(n) time
O(1) space

Question 151

Largest Number

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Answer 151

1. Convert to String[] arr
2. Sort (a + b).compareTo(b + a)
3. Return String.join("", arr)
4. Prove transtransitivity property: if AB > BA and BC > CB than AC > CA

O(nlog n) time
O(n) space

Question 152

Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

Answer 152

1. Compute length for both lists
2. while (lenthA > lengthB) -> a = a.next; lengthA--
3. while (lenthB > lengthA) -> b = b.next; lengthB--
4. while (a != b) -> a = a.next; b = b.next
5. Return a

O(n) time
O(1) space

Question 153

Search a 2D Matrix II

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Answer 153

1. Iterate from top-right corner
2. If target > cell -> row++
3. If target < cell -> col--
4. Else -> return true
5. Return false

O(m + n) time
O(1) space

Question 154

Find the Index of the First Occurrence in a String

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

Answer 154

1. Use two pointers
2. Iterate windowStart = [0; original.length - pattern.length + 1)
3. Iterate shift = [0; pattern.length)
4. If shift == pattern.length - 1 -> return windowStart
5. Return -1

OR

Knuth-Morris-Pratt prefix-function algo

O(m * n) time
O(1) space

Question 155

Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. 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.

Answer 155

Use level-order BFS

OR

1. while (levelStart != null)
2. current = levelStart
3. while (current != null)
4. current.left.next = current.right
5. current.right.next = current.next.left

O(n) time
O(1) space

Question 156

Gas Station

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

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith 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.

Answer 156

1. Compute totalCost and totalGas
2. If totalCost > totalGas -> return -1
3. If remainingGas += gas[i] - cost[i] < 0 -> start = i + 1
4. Return start

O(n) time
O(1) space

Question 157

Largest Rectangle in Histogram

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Answer 157

1. Use increasing Stack and helper class Rectangle(start, height)
2. while peek().height >= heights[i] -> prevRect = pop(); width = i - prevRect.start; area = prevRect.height * width;
3. start = prevRect.start
   4.push(new Rectangle(start, heights[i]))
4. Run one more loop for values left in the Stack

O(n) time
O(n) space

Question 158

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Answer 158

1. Use Stack, that always contains invalid sequence
2. If c == ')' && !isEmpty() && charAt(peek()) == '( -> pop(); length = i - peek()
3. Else -> push()

O(n) time
O(n) space

Question 159

Trapping Rain Water

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.

Answer 159

1. Use decreasing Stack and helper class Rectangle(start, height)
   2.while (peek() <= heights[i]) -> prevRect = pop(); width = i - prev.start; boundaryHeight = min(peek().height, heights[i])
2. totalAmount += width * (boundaryHeight - heights[i])
3. start = prev.start
4. push(new Rectangle(start, heights[i]))

O(n) time
O(n) space

Question 160

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

Answer 160

1. Use two pointers
2. Expand window to the right, until all chars are found
3. Squeeze window from the left, while charsToFind == 0
4. Update minWindow; from; to
5. Return s.substring(from, to + 1)

O(m + n) time
O(1) space

Question 161

Car Fleet

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

Answer 161

1. Create helper class Car(position, speed)
2. Sort car array by position
3. nextCar = cars[N - 1]
4. Iterate [N - 2; 0]
5. If for currentCar time to reach the target is greater, than for the next one -> carFleetsNumber++; nextCar = currentCar
6. Return fleetsNumber

O(n) time
O(n) space

Question 162

Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Answer 162

1. Use monotonic Deque to store indicies
2. If !isEmpty && peekFirst() == i - k -> pollFirst()
3. while !isEmpty && nums[peekLast()] <= nums[i] -> pollLast()
4. offerLast(i)
5. If i >= k - 1 -> result.add(nums[peekFirst()])
6. Return result.stream().mapToInt(v -> v).toArray()

O(n) time
O(k) space

Question 163

Transpose Matrix

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

Answer 163

1. For non-square matrix create transposed[matrix[0].length][matrix.length]
2. For i = [0; matrix.length) and j = [0; matrix[0].length] ->
   transposed[j][i] = matrix[i][j]

OR

1. For square matrix run swaps in-place
2. For i = [0; matrix.length) and j = [i + 1; matrix[0].length] -> swap()`

O(m * n) time
O(n) or O(1) space

Question 164

Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == 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.

Answer 164

1. Add beginWord to wordList and build adjList
2. For each word generate patterns: word.substring(0, i) + "*" + word.substring(i + 1)
3. Run BFS to find distance between beginWord and endWord

O(n * w^2) time
O(n * w^2) space

Question 165

Find Median from Data Stream

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.

Implement the MedianFinder class:

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

Answer 165

1. Use lowerHalfMaxHeap and upperHalfMinHeap
2. Add new num to upperHalfMinHeap
3. lowerHeap.offer(upperHead.poll())
4. If lowerHeap.size() > upperHeap.size() -> upperHeap.offer(lowerHeap.poll())
5. To find median return upperHeap.peek() if heaps have different size
6. Else -> return (upperHeap.peek() + lowerHeap.peek()) / 2.0

O(log n) time for add() and O(1) for find()
O(n) space

Question 166

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Answer 166

1. Treat nums as a linked list and find a start of a cycle using Floyd Algo
2. slow = nums[slow]; fast = nums[nums[fast]] -> return slow as intersection
3. slow = 0; slow = nums[slow]; intersection = nums[intersection] -> return slow as the cycle start

O(n) time
O(1) space

Question 167

Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Answer 167

1. Use Union Find by rank
2. ranks = [1, 1, 1...]; parents = [1, 2, 3, ...]
3. To find parent: while (parents[node] != node) -> node = parents[node]; parents[node] = parents[parents[node]]
4. If two nodes in union() have same parent -> return false and edge
5. parents[parent1] = parent2; ranks[parent2] += ranks[parent1]

O(n) time
O(n) space

Question 168

Remove All Adjacent Duplicates In String

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Answer 168

1. Use Stack
2. If !isEmpty() && peek() == c -> pop()
3. Else -> push()

O(n) time
O(n) space

Question 169

Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Answer 169

1. Use recursive rangeSum(root, low, high)
2. If root.val > low -> sum += rangeSum(root.left)
3. If root.val < high -> sum += rangeSum(root.right)
4. If root.val >= low && root.val <= high -> sum += root.val
5. Return sum

O(n) time
O(h) space

Question 170

Contains Duplicate II

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.

Answer 170

1. If i > k -> seen.remove(nums[i - k - 1])
2. If !seen.add(nums[i]) -> return true
3. Return false

O(n) time
O(k) space

Question 171

Rank Transform of an Array

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

• Rank is an integer starting from 1.
• The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
• Rank should be as small as possible.

Answer 171

1. Add value to indices to TreeMap
2. For indices : map.values() -> for i : indices -> ranks[i] = rank

OR

1. Sort copy of arr
2. rankMap.putIfAbsent(num, rankMap.size() + 1)
3. ranks[i] = rankMap.get(arr[i])`

O(n logn) time
O(n) space

Question 172

Reverse Linked List II

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.

Answer 172

1. prevToReversed = dummy
2. For (0; left - 1) -> prevToReversed = prevToReversed.next`
3. prevToReversed = reverseNextN(prevToReversed.next, right - left + 1)
4. For (0; n) -> reverse
5. Return dummy.next

O(n) time
O(1) space

Question 173

Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Answer 173

1. If charAt(left) != charAt(right) -> return isPalindrome(left + 1, right) || isPalindrome(left, right - 1)
2. Return true

O(n) time
O(1) space

Question 174

Serialize and Deserialize Binary Tree

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Answer 174

1. Use preorder or BFS to serialize
2. To deserialize create Queue from input string
3. current = poll()
4. If current.equals("null") -> return null
5. Node root = new Node(Integer.parseInt(current))
6. root.left = deserialize(); root.right = deserialize()
7. Return root

O(n) time
O(h) space

Question 175

Reverse Nodes in k-Group

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.

Answer 175

1. Compute length
2. For (0; length / k] -> reverseNextN(prevToReversed.next, k)
3. prevToReversed.next = result.head
4. prevToReversed = result.tail
5. Return dummy.next

O(n) time
O(1) space

Question 176

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Answer 176

1. nums1 = small, nums2 = large
2. Use BS for [0; small.length]
3. smallCut = (left + right) / 2; largeCut = half - smallCut
4. smallLeft = small[smallCut - 1]; smallRight = small[smallCut]
5. If largeLeft > smallRight -> left = smallCut + 1
6. If smallLeft > largeRight -> right = smallCut - 1
7. Else if total % 2 == 0 -> return max(smallLeft, largeLeft) + min(smallRight, largeRight) / 2.0
8. Else -> return min(smallRight, largeRight)

O(log min(m, n)) time
O(1) space

Question 177

Single Number

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.

Answer 177

1. Iterate nums
2. result = result ^ num

O(n) time
O(1) space

Question 178

Number of 1 Bits

Write a function that takes the binary representation of an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Answer 178

1. While n != 0
2. ones += n & 1
3. n >>> 1

O(n) time
O(1) space

Question 179

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Answer 179

1. For [0; 32)
2. reversed << 1
3. reversed = reversed | (n & 1)
4. n >>> 1

O(1) time
O(1) space

Question 180

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Answer 180

Use arithmetic progression sum: `((a1 + an) / 2) * n)

OR

1. missing = nums.length
2. missing = missing ^ i ^ nums[i]

O(n) time
O(1) space

Question 181

Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Answer 181

1. carry = 0
2. While b != 0
3. carry = (a & b) << 1
4. a = a ^ b
5. b = carry
6. Return a

O(n) time
O(1) space

Question 182

Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Answer 182

1. While x != 0
2. signedDigit = x % 10
3. x = x / 10
4. If reversed > MAX_INT / 10|| (reversed == MAX_INT / 10 && signedDigit > MAX_INT % 10) -> return 0
5. If reversed < MIN_INT / 10|| (reversed == MIN_INT / 10 && signedDigit < MIN_INT % 10) -> return 0
6. reversed = reversed * 10 + signedDigit

O(n) time
O(1) space

Question 183

Happy Number

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.

Answer 183

If seen.contains(n) -> return false

OR

1. Detect cycle in a linked list
2. slow = sumOfSquares(n)
3. fast = sumOfSquares(sumOfSquares(n))
4. If fast == 1 -> return true
5. If slow == fast -> return false

O(n) time
O(1) space

Question 184

Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith 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.

Answer 184

1. If digit <9 -> digit++; return digits
2. Else -> digit = 0
3. result = new int[digits.length + 1]; result[0] = 1
4. Return result

O(n) time
O(1) space

Question 185

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n.

Answer 185

1. If x == 0 || x == 1 -> return x
2. Return n >= 0 ? pow(x, n) : 1 / pow(x, -n)
3. Use recursive pow(x, n)
4. If n == 0 -> return 1
5. Return n % 2 == 0 ? pow(x * x, n / 2) : x * pow(x * x, n / 2)

O(log n) time
O(log n) space

Question 186

Multiply Strings

Given two non-negative integers a and b represented as strings, return the product of a and b, also represented as a string.

Answer 186

1. Reverse both strings
2. Create int[] result = new int[a.length + b.length]
3. position = i + j
4. mult = aDigit * bDigit + result[position]
5. result[position] = mult % 10
6. result[position + 1] += mult / 10
7. Return result, converted to string with no trailing zeroes

O(m * n) time
O(m + n) space

Question 187

Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Answer 187

1. twoStepsBefore = cost[0]; oneStepBefore = cost[1]
2. currentCost = min(twoSteps, oneStep) + cost[i]
3. twoSteps = oneStep; oneStep = currentCost
4. Return min(oneStep, twoSteps)

O(n) time
O(1) space

Question 188

Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Answer 188

1. Compute sum. If sum % 2 != 0 -> return false
2. target = sum / 2
3. Use Set<Integer> seen
4. For [N - 1; 0]-> tmpSet = new HashSet<>()
5. newSum = nums[i] + prev
6. If newSum == target -> return true
7. seen.addAll(tmpSet)
8. Return false

O(n * target) time
O(n * target) space

Question 189

Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot 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.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Answer 189

1. Use 2D-DP, dp[0][0] = 1
2. If i == 0 && j == 0 -> continue
3. fromTop = i > 0 ? dp[i - 1][j] : 0
4. fromLeft = i > 0 ? dp[i][j - 1] : 0
5. dp[i] = fromTop + fromLeft
6. Return dp[m - 1][n - 1]

O(m * n) time
O(m * n) space

Question 190

House Robber

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 houses representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Answer 190

1. Use 1D-DP
2. Either rob adjHouse OR rob prevPossible + current
3. dp[i] = max(dp[i - 1], dp[i - 2] + houses[i])
4. Return dp[N - 1]
5. We use only dp[i - 2] and dp[i - 1], so we can optimize space complexity using two vars instead of an array

O(n) time
O(1) space

If houses are arranged in a circle, run function twice and return
max(rob(houses, 0, N - 1), rob(houses, 1, N))

Question 191

Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

Answer 191

1. Use 1D-DP: dp[0] = 1
2. If currentDigit != 0 -> count += dp[n - 1], because current combination is valid
3. If prevDigit != 0 && prevDigit * 10 + currentDigit < 26 -> count += dp[n - 2]
4. dp[i] = count
5. Return dp[N - 1]
6. We use only dp[i - 2] and dp[i - 1], so we can optimize space complexity using two vars instead of an array

O(n) time
O(1) space

Question 192

Palindromic Substrings

Given a string s, return the number of palindromic substrings in it.

Answer 192

Use 2D-DP: dp[i][j] = length <=3 || dp[i + 1][j - 1]

OR

1. Extend palindrome from center = [0; N)
2. count += extendAndCount(center, center) – for odd length palindromes
3. count += extendAndCount(center - 1, center) – for even length palindromes
4. Return count

O(n^2) time
O(1) space

Question 193

Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

Answer 193

1. max = nums[0]; min = nums[0]; result = nums[0]
2. If num < 0 -> swap(min, max)
3. max = max(max * num, num)
4. min = min(min * num, num)
5. result = max(result, max)
6. Return result

O(n) time
O(1) space

Question 194

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Answer 194

1. Use 1D-DP
2. If left == right -> dp[left] = 1; continue
3. If nums[left] < nums[right] -> dp[left] = max(dp[left], dp[right] + 1)
4. Update longest = max(longest, dp[left])
5. Return longest

O(n^2) time
O(n) space

Question 195

Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Answer 195

1. Use Floyd Algo
2. Find intersection with slow and fast pointers. If intersection == null -> return null
3. Find cycle start with slow and intersection pointers
4. Return slow

O(n) time
O(1) space

Question 196

Palindrome Number

Given an integer x, return true if x is a palindrome, and false otherwise.

Answer 196

1. If x < 0 -> return false
2. int tmp = x; int reversedX = 0
3. while (tmp != 0) -> reversed = reversed * 10 + tmp % 10
4. Return x == reversedX

O(n) time
O(1) space

Question 197

Best Time to Buy and Sell Stock with Cooldown

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

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Answer 197

1. Use State Machine: sold = 0; bought = -prices[0]; rested = 0
2. rested = max(prevRested, prevSold)
3. sold = prevBought + prices[i]
4. bought = max(prevRested, prevRested - prices[i])
5. Return max(sold, rested)

O(n) time
O(1) space

Question 198

Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith 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 buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Answer 198

1. Use State Machine: sold = 0; bought = -prices[0]
2. sold = max(prevSold, prevBought + prices[i])
3. bought = max(prevBought, prevSold - prices[i])
4. Return sold

O(n) time
O(1) space

Question 199

Best Time to Buy and Sell Stock with Transaction Fee

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Answer 199

1. Use State Machine: sold = 0; bought = -prices[0]
2. sold = max(prevSold, prevBought + prices[i] - fee)
3. bought = max(prevBought, prevSold - prices[i])
4. Return sold

O(n) time
O(1) space

Question 200

Best Time to Buy and Sell Stock III

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

Find the maximum profit you can achieve. You may complete at most two transactions.

Answer 200

1. Use State Machine: sold1, sold2 = 0; bought1, bought2 = -prices[0]
2. sold1 = max(sold1, bought1 + prices[i])
3. bought1 = max(bought1, -prices[i])
4. sold2 = max(sold2, bought2 + prices[i])
5. bought2 = max(bought2, sold1 - prices[i])
6. Return sold2

O(n) time
O(1) space

Question 201

Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Answer 201

1. Use State Machine: sold[k + 1] = 0; bought[k + 1] = -prices[0]
2. for trans = [1; k]
3. sold[trans] = max(sold[trans], bought[trans] + prices[i])
4. bought[trans] = max(bought[trans], sold[trans-1] - prices[i])
5. Return sold[k]

O(n) time
O(1) space

Question 202

N-Queens

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 all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Answer 202

1. Use backtrack(board, n, row, Set, Set, Set, result)
2. If board.size() == n -> add(); return
3. If cols.contains(col) || posDiags.contains(row + col) || negDiags.contains(row - col) -> continue
4. Run backtrack(row + 1) for col = [0; N)
5. Return result

O(n!) time
O(n) space

Question 203

Convert Sorted List to Binary Search Tree

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a
height-balanced binary search tree.

Answer 203

1. If head == null -> return null
2. If head.next == null -> return new TreeNode(head.val)
3. mid = findMid()
4. root = new TreeNode(mid.val)
5. root.left = convert(head)
6. root.right = convert(mid.next)
7. Return root

O(nlog n) time
O(log n) space

Question 204

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Answer 204

1. Use recursive solve(board)
2. If !isValid(board, row, col, num) -> continue
3. If solve(board)-> return true
4. isValid = board[row][i] != num && board[i][col] != num && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != num

O(9^(nn)) time**
**O(9^(nn)) space

Question 205

Jump Game

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.

Answer 205

1. If i > reachable -> return false
2. reachable = max(reachable, i + num[i])
3. Return true

O(n) time
O(1) space

Question 206

Jump Game II

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 the minimum number of jumps to reach nums[n - 1].

Answer 206

1. reachable = max(reachable, i + num[i])
2. If prevFarthestJump == i -> jumps++; prevFarthestJump = reachable
   3.

Question 207

Jump Game II

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 the minimum number of jumps to reach nums[n - 1].

Answer 207

1. reachable = max(reachable, i + num[i])
2. If prevFarthestJump == i -> jumps++; prevFarthestJump = reachable
3. Return jumps

O(n) time
O(1) space

Question 208

Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Answer 208

1. while (current.next != null)
2. If current.val == current.next.val -> current.next = current.next.next
3. Else -> current = current.next
4. Return head

O(n) time
O(1) space

Question 209

Walls and Gates

You are given an m x n grid rooms initialized with these three possible values.

• -1 A wall or an obstacle.
• 0 A gate.
• INF Infinity means an empty room.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Answer 209

1. Use BFS for each gate: planned.offer(); visited = 1
2. Compute distance: rooms[x][y] = rooms[current[0]][current[1]] + 1

O(n) time
O(1) space

Question 210

Number of Connected Components in an Undirected Graph

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Answer 210

1. Use Union Find: parent[i] = i; rank[i] = 1
2. findParent(): while (node != parents[node]) -> parents[node] = parents[parents[node]]; node = parents[node]
3. uniteAndCount() -> return 0 if parents are equal, 1 otherwise
4. components = n - uniteAndCount()
5. Return components

O(n) time
O(n) space

Question 211

Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Answer 211

1. Use Union Find: parent[i] = i; rank[i] = 1
2. findParent(): while (node != parents[node]) -> parents[node] = parents[parents[node]]; node = parents[node]
3. uniteAndCount() -> return 0 if parents are equal, 1 otherwise
4. provinces = n - uniteAndCount()
5. Return components

O(n) time
O(n) space

Question 212

Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Answer 212

1. Use Union Find: parent[i] = i; rank[i] = 1
2. findParent(): while (node != parents[node]) -> parents[node] = parents[parents[node]]; node = parents[node]
3. uniteAndCount() -> return 0 if parents are equal, 1 otherwise
4. union = uniteAndCount()
5. If union == 0 -> return false (cycle found)
6. Return components == 1 (fully connected)

O(n) time
O(n) space

Question 213

Find First and Last Position of Element in Sorted Array

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.

Answer 213

1. Use BS two times to find left and right bounds
2. bound = -1
3. If nums[mid] == target -> bound = mid
4. If isLeft -> right = mid - 1
5. Else -> left = mid + 1

O(log n) time
O(1) space

Question 214

Word Search II

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.

Answer 214

1. Build Trie for words
2. Use recursive dfs(board, x, y, parent, result)
3. If parent.children.get(board[x][y]) == null -> return
4. If child.word != null -> result.add(word); child.word = null
5. dfs() for all children
6. Optionally, if child.children.isEmpty() -> parent.remove(board[x][y])`
7. Return result

O(m * n * 3^word.length) time
O(m * n) space

Question 215

Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Answer 215

1. Encode: 5#Hello5#World
2. Decode: while (pointer < s.length())
3. length = 0; while (s.charAt(pointer) != '#') -> length = 10 * length + (s.charAt(pointer) - '0')
4. str = s.substring(pointer + 1, pointer + 1 + length)
5. pointer = end

O(n) time
O(n) space

Question 216

Binary Tree Maximum Path Sum

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.

Answer 216

1. Use global variable max
2. Use recursive findMaxPathWithNoSplit(root)
3. If root == null -> return 0
4. left = max(0, find(root.left))
5. right = max(0, find(root.right))
6. max = max(max, root.val + left + right)
7. Return root.val + max(left, right)

O(n) time
O(h) space

Question 217

Check Completeness of a Binary Tree

Given the root of a binary tree, determine if it is a complete binary tree.

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

Answer 217

1. Use BFS traversal
2. If current != null -> offer(left); offer(right)
3. If prev == null -> return false
4. prev = current
5. Return true

O(n) time
O(n) space

Question 218

Valid Parenthesis String

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

Answer 218

1. Count minOpen and maxOpen
2. If c == '(' -> minOpen++; maxOpen++
3. If c == ')' -> minOpen--; maxOpen--
4. Else -> minOpen--; maxOpen++
5. If maxOpen < 0 -> return false
6. minOpen = max(0, minOpen)
7. Return minOpen == 0

O(n) time
O(1) space

Question 219

Check if a Parentheses String Can Be Valid

A parentheses string is a non-empty string consisting only of '(' and ')'.

You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's.

Return true if you can make s a valid parentheses string. Otherwise, return false.

Answer 219

1. Count minOpen and maxOpen
2. If locked[i] == 0 -> minOpen--; maxOpen++
3. If c == '(' -> minOpen++; maxOpen++
4. If c == ')' -> minOpen--; maxOpen--
5. If maxOpen < 0 -> return false
6. minOpen = max(0, minOpen)
7. Return minOpen == 0

O(n) time
O(1) space

Question 220

Minimum Remove to Make Valid Parentheses

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Answer 220

1. Use Stack to find Set<Integer> indicies to remove
2. In the end, while (!stack.isEmpty()) -> indicies.add(pop())
3. Construct result string: if !indicies.contains(i) -> append()
4. Return result.toString()

O(n) time
O(n) space

Question 221

Isomorphic Strings

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.

Answer 221

1. if !secondToFirst.containsKey(second) && !firstToSecond.containsKey(first) -> put()
2. Else if secondToFirst.get(second) != first || firstToSecond.get(first) != second -> return false
3. Return true

O(n) time
O(1) space

Question 222

Find Pivot Index

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Answer 222

1. Count totalSum
2. If leftSum == totalSum - leftSum - nums[i] -> return i
3. leftSum += nums[i]
4. Return -1

O(n) time
O(1) space

Question 223

Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

Answer 223

Return n > 0 && (n & n - 1) == 0
(4 = 100; 3 = 11; 100 & 11 = 0)

O(1) time
O(1) space

Question 224

Construct Binary Tree from Inorder and Postorder Traversal

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.

Answer 224

1. Build valueToIndex from inorder
2. Init postOrderRootIndex = postorder.length - 1
3. Use recursive toTree(postorder, left, right)
4. If left > right -> return null
5. root = new TreeNode(postorder[postOrderRootIndex--])
6. inorderRootIndex = root.val
7. root.right = toTree(inorderRootIndex + 1, right)
8. root.left = toTree(left, inorderRootIndex -1)
9. Return root

O(n) time
O(n) space

Question 225

Number of Closed Islands

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Answer 225

Use DFS from each 1 to determine, if island is closed

O(m * n) time
O(m * n) space

Question 226

Count Sub Islands

You are given two m x n binary matrices grid1 and grid2 containing only 0’s (representing water) and 1’s (representing land). An island is a group of 1’s connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

Answer 226

Use DFS for each 1 is grid2: if grid1[x][y] != 1 -> return false

O(m * n) time
O(m * n) space

Question 227

Number of Enclaves

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

Answer 227

Use DFS from each border-cell. Afterwards, if cell is 1 and was not visited -> count++

O(m * n) time
O(m * n) space

Question 228

As Far from Land as Possible

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

Answer 228

1. Use multy-ended BFS: add all 1 to planned
2. If planned.isEmpty() || planned.size() == m * n -> return -1
3. Run BFS level-by-level and return distance - 1

O(m * n) time
O(m * n) space

Question 229

Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Answer 229

1. Use level-by-level BFS: planned.add(new int[] {0, 0})
2. If current[0] == m - 1 && current[1] == n - 1 -> return distance
3. Return -1

O(m * n) time
O(m * n) space

Question 230

Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Answer 230

1. Build freqMap of small
2. Iterate large
3. If small.get(num) > 0 -> add() and small.merge(-1)
4. Return result

O(m + n) time
O(min(m, n)) space

OR

1. If arrays are sorted, use two pointers
2. If nums1[first] > nums2[second]-> second++
3. If nums2[second] > nums1[first] -> first++
4. Else -> add(); first++; second++;

Question 231

Reshape the Matrix

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Answer 231

1. If r * c != m * n -> return mat
2. Iterate original mat
3. reshaped[row][col] = mat[i][j]; col++
4. If col == reshaped[0].length -> row++; col = 0
5. Return reshaped

O(m * n) time
O(m * n) space

Question 232

Design Browser History

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Answer 232

1. Use two Stack: past and future
2. visit(): past.push(current); current = url; future.clear()

OR

1. Use Double Linked List
2. visit(): current.next = added; added.prev = current

OR

1. Use ArrayList
2. visit(): current++; add()/set(); last = current
3. back(): return urls.get(max(0, current - steps))
4. forward(): return urls.get(min(last, current + steps))

O(1) time
O(n) space

Question 233

Inorder Successor in BST

Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

The successor of a node p is the node with the smallest key greater than p.val.

Answer 233

1. Use recursive find(current, parent, p)
2. If current == null -> return parent
3. If p.val >= current.val -> return find(current.right, parent, p)
4. If p.val < current.val -> return find(current.left, current, p)

OR

1. Go iterative: succesor = null
2. If p.val >= root.val -> root = root.right
3. Else -> successor = root; root = root.left
4. Return successor

O(h) time
O(1) space

Question 234

Nearest Exit from Entrance in Maze

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Answer 234

Use level-by-level BFS.

O(m * n) time
O(m * n) space

Question 235

Shortest Bridge

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1’s not connected to any other 1’s. There are exactly two islands in grid.

You may change 0’s to 1’s to connect the two islands to form one island.

Return the smallest number of 0’s you must flip to connect the two islands.

Answer 235

1. Use DFS to find the first island and add all its cells to planned
2. Use level-by-level BFS to expand the first island, until we meet the second one

O(m * n) time
O(m * n) space

Question 236

Keys and Rooms

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Answer 236

1. Use DFS
2. If visited.size() == rooms.size() -> return true
3. Else -> false

O(n) time
O(n) space

Question 237

Number of Operations to Make Network Connected

There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.

Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.

Answer 237

1. Use Union Find: parent[i] = i; rank[i] = 1
2. findParent(): while (node != parents[node]) -> parents[node] = parents[parents[node]]; node = parents[node]
3. uniteAndCount() -> return 0 if parents are equal, 1 otherwise
4. components = n - uniteAndCount()
5. Return components - 1

O(n) time
O(n) space

Question 238

N-ary Tree Preorder Traversal

Given the root of an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Answer 238

Use recursive traverse(root, result)

OR

1. Use iterative DFS
2. For each node iterate children in reverse order because of the stack

O(n) time
O(n) space

Question 239

Can Place Flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0’s and 1’s, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Answer 239

1. For each 0 check if prev and next spots are available
2. If so -> pointer += 2; n--
3. Else -> pointer += 1
4. Return n == 0

O(n) time
O(1) space

Question 240

Number of Zero-Filled Subarrays

Given an integer array nums, return the number of subarrays filled with 0.

Answer 240

1. If num == 0 -> subarraysCount++
2. Else -> subarraysCount = 0
3. total += subarraysCount
4. Return total

O(n) time
O(1) space

Question 241

Pour Water

You are given an elevation map represents as an integer array heights where heights[i] representing the height of the terrain at index i. The width at each index is 1. You are also given two integers volume and k. volume units of water will fall at index k.

Water first drops at the index k and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

• If the droplet would eventually fall by moving left, then move left.
• Otherwise, if the droplet would eventually fall by moving right, then move right.
• Otherwise, rise to its current position.

Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, level means the height of the terrain plus any water in that column.

We can assume there is infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than one grid block, and each unit of water has to be in exactly one block.

Answer 241

1. current = k
2. for i = [0; volume)
3. while current > 0 && heights[current] >= heights[current - 1] -> current--, move left
4. while current < heights.length - 1 && heights[current] >= heights[current + 1] -> current++, move right
5. while current > k && heights[current] == heights[current - 1] -> current--, move left in case of a flat terrain on the right
6. heights[current] += 1

O(volume * n) time
O(1) space

Question 242

Shortest Path with Alternating Colors

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges.

Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

Answer 242

1. Build adjList, using Node(idx, color)
2. Init distances -> fill(-1); distances[0] = 0
3. Init visited[n][2] -> visited[0][RED] = 1; visited[0][BLUE] = 1
4. Use level-by-level BFS to calculate distances
5. If visited[child.idx][child.edgeColor] == 0 && current.edgeColor != child.edgeColor`
6. If distances[child] == -1 -> distances[child] = distance
7. Mark visited and continue

O(n) time
O(n) space

Question 243

Number of Smooth Descent Periods of a Stock

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the ith day.

A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule.

Return the number of smooth descent periods.

Answer 243

1. If prev - price == 1 -> smoothCount++
2. Else -> smoothCount = 1
3. total += smoothCount
4. prev = num
5. Return total

O(n) time
O(1) space

Question 244

Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

• void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
• int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

Answer 244

1. Use Ring Buffer with size 300
2. On each method call: move(timestamp)
3. move(): gap = max(LIMIT, timestamp - last)`
4. hits[(last + 1 + i) % LIMIT] = 0
5. last = timestamp

O(1) time
O(1) space

Question 245

Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Answer 245

1. Compute the lastIndices for each char
2. last = 0; start = 0
3. last = max(last, lastIndices[chars[end] - 'a'])
4. If last == end -> add(end - start + 1); start = end + 1
5. Return result

O(n) time
O(1) space

Question 246

Time Needed to Inform All Employees

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Answer 246

1. Build subordinatesMap
2. Use recursive dfs(current, subordinatesMap, informTime)
3. time = 0
4. For each subordinate -> time = max(time, dfs(subordinate))
5. Return time + informTime[current]

O(n) time
O(n) space

Question 247

Divide Array in Sets of K Consecutive Numbers

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

Answer 247

1. Build freqMap (use TreeMap or sort nums)
2. Iterate keySet()
3. while (freqMap.get(num) > 0) -> for shift = [0; k)
4. count = merge(num + shift, -1)
5. If count < 0 -> return false
6. Return true

O(n logn) time
O(n) space

Question 248

Jump Game III

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Answer 248

1. Use recursive dfs(arr, start, visited)
2. If start < 0 || start >= arr.length || visited[start] == 1 -> return false
3. If arr[start] == 0 -> return true
4. visited[start] = 1
5. Return dfs(arr, start + arr[start]) || dfs(arr, start - arr[start])

O(n) time
O(n) space

Question 249

Game of Life

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 is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

Answer 249

1. For each cell count alive neighbors with state >= 1
2. Mark dying cells with -1 and reproducing with 2
3. Iterate board one more time and assign final states to dying and reproducing cells

O(m * n) time
O(1) space

Question 250

Find Eventual Safe States

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Answer 250

1. Find hasCycle using white-grey-black DFS for each node
2. If visited[start] != 0 -> return visited[start] == 1

O(n) time
O(n) space

Question 251

Letter Case Permutation

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Answer 251

1. Use recursive backtrack(s, index, current, result)
2. If index == s.length() -> add(); return
3. If isDigit() -> backtrack()
4. Else -> twice backtrack() with upper and with lower cases

O(2^n) time
O(2^n) space

Question 252

Successful Pairs of Spells and Potions

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Answer 252

1. Sort potions
2. Use BS to find number of pairs for each spell

O(nlog n) time
O(log n) space

Question 253

Triangle

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.

Answer 253

1. Use DP. We only need prevRow
2. minPath = min(pathFromLeft, pathFromRight) + current
3. currRow.add(minPath)
4. prevRow = currRow
5. Return Collections.min(prevRow)

O(n^2) time
O(n) space

Question 254

Minimum Falling Path Sum

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Answer 254

1. Use DP. We only need prevRow
2. minPath = min(pathFromCenter, min(pathFromLeft, pathFromRight)) + current
3. currRow[col] = minPath
4. prevRow = currRow
5. Return min(prevRow)

O(n^2) time
O(n) space

Question 255

Boats to Save People

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.

Answer 255

1. Sort people
2. Run two pointers: light = 0; heavy = people.length - 1
3. while (light <= heavy)
4. boats++
5. If people[light] + people[heavy] <= limit -> light++
6. heavy--
7. Return boats

O(nlog n) time
O(log n) space

Question 256

Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Answer 256

1. while (root != null && root.val != val
2. root = root.val > val ? root.left : root.right
3. Return root

O(h) time
O(1) space

Question 257

Two Sum IV - Input is a BST

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Answer 257

Use two pointers on inoreder traversal

OR

Use Set to store seen values

O(n) time
O(n) space

Question 258

Insert into a Binary Search Tree

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Answer 258

1. current = root
2. while (current != null)
3. If current.val > root -> insert left or traverse left
4. Else -> insert right or traverse right
5. Return new TreeNode(val)

O(h) time
O(1) space

Question 259

Bulls and Cows

You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

• The number of “bulls”, which are digits in the guess that are in the correct position.
• The number of “cows”, which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number secret and your friend’s guess guess, return the hint for your friend’s guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Answer 259

1. If secretChar == guessChar -> bulls++
2. Else -> freqMap[guessChar]--; freqMap[secretChar]++
3. If freqMap[guessChar] >= 0 -> cows++
4. If freqMap[secretChar] <= 0 -> cows++

O(n) time
O(1) space

Question 260

Maximum Profit in Job Scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Answer 260

1. Build jobs sorted by start time
2. Use recursive findMax(jobs, current, memo)
3. Use memo to cache results based on current
4. takeCurrent = profit[current] + findMax(next)`
5. skipCurrent = findMax(current + 1)
6. To find next use BS -> if jobs[mid].start >= prevJobEnd
7. Return max(takeCurrent, skipCurrent)

O(nlog n) time
O(n) space

Question 261

Optimal Partition of String

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

Return the minimum number of substrings in such a partition.

Answer 261

1. Use Set<Character> seen
2. If seen.contains(c) -> count++; seen.clear()
3. seen.add(c)
4. Return count

O(n) time
O(1) space

Question 262

Meeting Scheduler

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.

If there is no common time slot that satisfies the requirements, return an empty array.

Answer 262

1. Sort both arrays by start time
2. leftBound = min(first.start, second.start)
3. rightBound = max(first.end, second.end)
4. If rightBound - leftBound >= duration -> return
5. If first.start < second.start -> i++
6. Else -> j++
7. Return List.of()

O(nlog n + mlog m) time
O(log n + log m) space

Question 263

Height Checker

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.

You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

Answer 263

1. Use Counting Sort: int[101] freqMap
2. while (freqMap[currentHeight] == 0 -> currentHeight++
3. If height != currentHeight -> mismatch++
4. freqMap[currentHeight]--
5. Return mismatch

O(n) time
O(1) space

Question 264

Long Pressed Name

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Answer 264

1. Use two pointers
2. If namePointer < length && nameChar == typedChar -> namePointer++
3. Else if typedPointer > 0 || typedChar != prevTypedChar -> return false
4. Return namePointer == length

O(n) time
O(1) space

Question 265

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Answer 265

Use level-by-level BFS

O(n) time
O(n) space

Question 266

Largest Time for Given Digits

Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

Return the latest 24-hour time in "HH:MM" format. If no valid time can be made, return an empty string.

Answer 266

1. Use three loops: i, j, k, l = 6 - i - j - k
2. hour = arr[i] * 10 + arr[j]
3. minute = arr[k] * 10 + arr[l]
4. If hour < 24 && minute < 60 -> update max = max(max, hour * 60 + minute)
5. Return String.format("%02d:%02d", max / 60, max % 60)

O(4 * 4 * 4) time
O(1) space

Question 267

Sum of Root To Leaf Binary Numbers

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

Answer 267

1. Use recursive sum(root, 0)
2. If root == null -> return 0
3. current = current * 2 + root.val
4. If root.left == null && root.right == null -> return current
5. Return sum(root.left) + sum(root.right)

O(n) time
O(h) space

Question 268

Intersection of Three Sorted Arrays

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

Answer 268

1. Use three pointers
2. minVal = min(arr1[p1], arr2[p2], arr3[p3])
3. If p123 == minVal -> p123++

O(n) time
O(1) space

Question 269

Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Answer 269

1. Use mono decreasing Stack
2. for i = [0, nums2.length)
3. while (!s.isEmpty && num > s.peek()) -> map[pop()] = num
4. s.push(num)
5. result[i] = map.getOrDefault(num, -1)
6. Return result

O(n + m) time
O(m) space

Question 270

Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Answer 270

1. Use mono decreasing Stack for indices
2. Arrays.fill(result, -1)
3. for i = [0, nums.length * 2)
4. j = i % nums.length
5. while (!s.isEmpty && nums[j] > nums[s.peek()]) -> result[pop()] = nums[j]
6. If i < nums.length -> s.push(j)
7. Return result

O(n) time
O(n) space

Question 271

Synonymous Sentences

You are given a list of equivalent string pairs synonyms where synonyms[i] = [si, ti] indicates that si and ti are equivalent strings. You are also given a sentence text.

Return all possible synonymous sentences sorted lexicographically.

Answer 271

1. Use Union Find on synonyms
2. Build synonymGroups, checking for connections between text.split(" ") and set of unique synonyms
3. Use recursive backtrack(text, synonymGroups, current, currentSentence, result)

O(?) time
O(?) space

Question 272

Letter Tile Possibilities

You have n tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

Answer 272

1. Use recursive backtrack(chars, used, length) with global count
2. Arrays.sort(chars)
3. If length == chars.length -> return
4. If used[i] == 1 -> continue
5. If i > 0 && chars[i] == chars[i - 1] && used[i - 1] == 0 -> continue
6. count++
7. used[i] = 1; backtrack(); used[i] = 0

O(n!) time
O(n!) space

Question 273

Flower Planting With No Adjacent

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Answer 273

1. Build adjList
2. Use BFS
3. If colors[neighbor] == 0 -> colors[neighbor] = colors[current] % 4 + 1; offer()
4. If colors[neighbor] == colors[current] -> colors[neighbor] = colors[current] % 4 + 1

O(n) time
O(n) space

Question 274

Number of Equivalent Domino Pairs

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a == c and b == d), or (a == d and b == c) - that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Answer 274

1. Use freqMap
2. val = min(domino[0], domino[1]) * 10 + max(domino[0], domino[1])
3. pairs += freqMap.getOrDefault(val, 0)
4. freqMap.merge(val, 1, Integer::sum)
5. Return pairs

O(n) time
O(1) space

Question 275

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

• double next(int val) Returns the moving average of the last size values of the stream.

Answer 275

Use double-ended Deque OR Ring Buffer

Return (double) windowSum / window.size()

O(1) time
O(m) space

Question 276

Shortest Path Visiting All Nodes

You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Answer 276

1. Use multy-end level-by-level BFS with bit masks
2. allVisitedMask = (1 << n) - 1
3. For each node -> offer(new Node(i, 1 << i)); visited[i][1 << i] = 1
4. nextMask = current.mask | (1 << neighbor)
5. If nextMask == allVisitedMask -> return path
6. Return -1

O(2^n * n * n) time
O(2^n * n) space

Question 277

Simplify Path

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

Return the simplified canonical path.

Answer 277

1. Use Stack
2. If dir.equals('..') -> if !isEmpty() -> pop()
3. Else if !dir.isEmpty() && !dir.equals('.') -> push(dir)
4. Return reverted Stack

O(n) time
O(n) space

Question 278

Validate Stack Sequences

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Answer 278

1. Use Stack
2. s.push(pushed[i])
3. while (!isEmpty() && popped[i] == s.peek()) -> pop(); i++
4. Return s.isEmpty()

O(n) time
O(n) space

Question 279

Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s.

Answer 279

1. Use 2D-DP
2. for right = [0; N) and left = [right; 0]
3. If left == right -> dp[left][right] = 1`
4. If charAt(left) == charAt(right) -> dp[left][right] = dp[left + 1][right - 1] + 2
5. Else -> dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
6. Return dp[0][N -1]

O(n^2) time
O(n^2) space

Question 280

Find the Town Judge

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

• The town judge trusts nobody.
• Everybody (except for the town judge) trusts the town judge.

There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Answer 280

1. Use two arrays: trusts and trustedBy
2. Iterate people
3. If trusts[man] == 0 && trustedBy[man] == N - 1 -> return man
4. Return -1

O(n) time
O(n) space

Question 281

Find the Celebrity

Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. You are only allowed to ask questions like: “Hi, A. Do you know B?” to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) that tells you whether a knows b. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party.

Return the celebrity’s label if there is a celebrity at the party. If there is no celebrity, return -1.

Answer 281

1. First check: candidate = 0
2. If knows(candidate, i) -> candidate = i
3. Second check: if knows(candidate, i) || !knows(i, candidate) -> return -1
4. Return candidate
5. Use cache for knows() calls if needed

O(n) time
O(1) space

Question 282

Minimum Number of Vertices to Reach All Nodes

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.

Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Answer 282

Find and return unreachable nodes

O(n) time
O(n) space

Question 283

Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Answer 283

1. Use BFS to color nodes in RED and BLUE
2. If colors[current] == colors[neighbor] -> return false
3. Return true

O(n) time
O(n) space

Question 284

Possible Bipartition

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Answer 284

1. Use BFS to color nodes inRED and BLUE
2. If colors[current] == colors[neighbor] -> return false
3. Return true

O(n) time
O(n) space

Question 285

Maximal Network Rank

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.

The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Answer 285

1. Use ranks[] and adjMatrix[][]
2. Iterate i = [0; N) and j = [i + 1; N)
3. maxRank = max(maxRank, ranks[i] + ranks[j] - adjMatrix[i][j])
4. Return maxRank

O(n^2) time
O(n^2) space

Question 286

Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends deadends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Answer 286

1. Use level-by-level BFS
2. Mutate current to get neighbors
3. nextDial = (current.charAt(dial) - '0' + dir + 10) % 10

O(10^n * n^2 + d) time
O(10^n + d) space

Question 287

Minimum Genetic Mutation

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.

Answer 287

1. Use level-by-level BFS
2. Mutate current to get neighbors

O(4^n * n^2 + b) time
O(4^n + b) space

Question 288

Water and Jug Problem

You are given two jugs with capacities jug1Capacity and jug2Capacity liters. There is an infinite amount of water supply available. Determine whether it is possible to measure exactly targetCapacity liters using these two jugs.

If targetCapacity liters of water are measurable, you must have targetCapacity liters of water contained within one or both buckets by the end.

Operations allowed:

• Fill any of the jugs with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full, or the first jug itself is empty.

Answer 288

1. Use level-by-level BFS storing State(firstJug, secondJug)
2. Possible neighbors: (first, c.second), (c.first, second), (0, c.second), (c.first, 0), (c.first - min(first, second - c.second), c.second + min()), (c.first + min(), c.second - min())`

O(x * y) time
O(x * y) space

Question 289

Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Answer 289

1. small = MAX_INTEGER; mid = MAX_INTEGER
2. if num <= small -> small = num
3. Else if nums <= mid -> min = num
4. Else -> return true
5. Return false

O(n) time
O(1) space

Question 290

Longest Palindrome by Concatenating Two Letter Words

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

Answer 290

1. Use 2D-array freqMap[26][26]
2. If freqMap[b][a] > 0 -> result += 4; freqMap[b][a]--
3. Else -> freqMap[a][b]++
4. Second pass -> if freqMap[i][i] > 0 -> result += 2
5. Return result

O(n) time
O(1) space

Question 291

Minimize Product Sum of Two Arrays

Given two arrays nums1 and nums2 of length n, return the minimum product sum if you are allowed to rearrange the order of the elements in nums1.

Answer 291

Sort arrays

OR

1. Use counting sort
2. Iterate counter1++ and counter2--
3. Skip zeroes
4. occurrences = min(counter1[p1], counter2[p2])
5. product += occurrences * p1 * p2
6. counter1[p1] -= occurrences
7. counter2[p2] -= occurences
8. Return product

O(n) time
O(1) space

Question 292

Majority Element II

Given an integer array of size n, find all elements that appear more than n/3 times.

Answer 292

1. Use Moore Algo
2. candidate1 = nums[0]; candidate2 = nums[0]
3. If candidate1 == num -> count1++
4. If candidate2 == num -> count2++
5. If count1 == 0 -> candidate1 = num; count1++
6. If count2 == 0 -> candidate2 = num; count2++
7. Else -> count1--; count2--
8. Second pass -> if num == candidateN -> countN++
9. If countN > n / 3 -> result.add(candidateN)
10. Return result

O(n) time
O(1) space

Question 293

Bus Routes

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.

You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

Answer 293

1. Map stops to buses
2. Use level-by-level BFS
3. For each possible bus for current stop add all `stops

O(n) time
O(n) space

Question 294

Leftmost Column with at Least a One

A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return the index (0-indexed) of the leftmost column with a 1 in it. If such an index does not exist, return -1.

You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

Answer 294

Use BS for each row

OR

Run search from top left corner

O(n + m) time
O(1) space

Question 295

Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Answer 295

1. Locate node by going left or right
2. Find successor: one step to the right and all the way to the left
3. Replace deleted node with successor

O(h) time
O(h) space

Question 296

Most Stones Removed with Same Row or Column

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

Answer 296

Use Union Find for every pair in the same row or col

O(n^2) time
O(n) space

Question 297

Number of Subsequences That Satisfy the Given Sum Condition

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target.

Answer 297

1. Use two pointers on sorted array
2. If sum > target -> right--
3. Else -> result += pow(right - left, 2); left++

O(nlog n) time
O(n) space

Question 298

Pancake Sorting

Given an array of integers arr, sort the array by performing a series of pancake flips.

Answer 298

1. Iterate from the end
2. Find index of element, that should be on current position
3. Flip it to the head
4. Flip it to the tail

O(n^2) time
O(n) space

Question 299

Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

Answer 299

1. Sort copy
2. If sorted[i] != nums[i] -> left = min(left, i); right = max(right, i)

OR

Use two monotonic Stack

O(n) time
O(n) space

Question 300

Two Sum BSTs

Given the roots of two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Answer 300

Use DFS on root1 and BS for root2

OR

1. Use two inorder traversals
2. Use two pointers to find target: p1 = 0; p2 = inorder2.size() - 1

O(m + n) time
O(m + n) space

Question 301

Prison Cells After N Days

There are 8 prison cells in a row and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• Otherwise, it becomes vacant.

Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.

You are given an integer array cells where cells[i] == 1 if the ith cell is occupied and cells[i] == 0 if the ith cell is vacant, and you are given an integer n.

Return the state of the prison after n days (i.e., n such changes described above).

Answer 301

1. Run simulation
2. Find pattern using cache with bitmasks
3. Fast forward days = days % (cache.get(mask) - days)

O(cells * min(days, 2^cells)) time
O(min(days, 2^cells)) space

Question 302

Find Peak Element

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 must write an algorithm that runs in O(log n) time.

Answer 302

1. Use BS to find peak
2. If nums[mid] < nums[mid + 1] -> rising slope, left = mid + 1
3. If nums[mid] < nums[mid - 1] -> falling slope, right = mid - 1

O(log n) time
O(1) space

Question 303

Fruit Into Baskets

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Answer 303

1. Use sliding window
2. basket.merge(fruits[right], 1, Integer::sum)
3. while (basket.size() > 2) -> basket.merge(fruits[left], -1, Integer::sum)
4. max = max(max, right - left + 1)
5. Return max

O(n) time
O(1) space

Question 304

Min Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Answer 304

1. Build all possible edges and sort them by length
2. Use Union Find until usedEdges == points.length - 1

O(n^2 * log n^2) time
O(n^2) space

Question 305

Longest Absolute File Path

Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Answer 305

Use Stack to go back to the parent dir

O(n) time
O(n) space

Question 306

Remove K Digits

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Answer 306

1. Use monotonic Stack (or StringBuilder)
2. Skip trailing zeroes
3. If still k > 0 remove digits from the tail

O(n) time
O(n) space

Question 307

LFU Cache

Answer 307

1. Use two Map: one for nodes, one for frequencies
2. Store frequency in each Node

O(1) time
O(n) space

Question 308

Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Answer 308

Use Bellman-Ford (two loops dp)

OR

Use Djikstra (BFS with heap)

Question 309

Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Answer 309

Use Bellman-Ford (two loops dp)

OR

Use Djikstra (BFS with heap)

Question 310

Sum of Subarray Minimums

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr.

Answer 310

1. Use mono Stack: arr[s.peek()] >= arr[i]
2. min = s.pop(); left = s.peek() : -1; right = i
3. length = (min - left) * (right - min)

O(n) time
O(n) space

Question 311

Sum of Subarray Ranges

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

Answer 311

1. Use mono Stack twice
2. Find sum of all max and all min
3. Return max - min

O(n) time
O(n) space

Question 312

Count Submatrices With All Ones

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

Answer 312

1. Treat each row as histogram
2. heights[col] = mat[row][col] == 0 ? 0 : heights[col] + 1
3. minHeight = heights[col]
4. for (bar = col; bar >=0; bar--) -> minHeight = min(heights[bar]); count += minHeight
5. Return count

O(n^3) time
O(n) space

Question 313

Maximal Square

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.

Answer 313

1. Use 2D-DP
2. dp[i][j] = min(left, right, diag) + 1` – side of largest square with the bottom right corner here
3. Return largest * largest

O(m * n) time
O(m * n) space

Question 314

Evaluate Division

Answer 314

Use BFS

Question 315

Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

Given an integer array nums, return the number of arithmetic subarrays of nums.

Answer 315

1. subarrays = nums[i - 2] - nums[i - 1] == nums[i - 1] - nums[i] ? subarrays + 1 : 0
2. count += subarrays
3. Return count

O(n) time
O(1) space

Question 316

Minimum Domino Rotations For Equal Row

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.

Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.

If it cannot be done, return -1.

Answer 316

1. Try to do rotations, so that all the values on top are equal to either tops[0] or bottoms[0]
2. If tops[i] != val && bottoms[i] != val -> return -1
3. If tops[i] != val -> topRotations++
4. If bottoms[i] != val -> bottomRotations++
5. Return min(topRotations, bottomRotations)

O(n) time
O(1) space

Question 317

Duplicate Zeros

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Answer 317

1. for (; pointer + shifts < arr.length; pointer++) -> count zeroes
2. for (pointer = pointer - 1; shifts > 0; pointer--)
3. If pointer + shifts < arr.length -> arr[pointer + shifts] = arr[pointer]
4. If arr[pointer] == 0 -> arr[pointer + --shifts] = arr[pointer]

O(n) time
O(1) space

Question 318

Number of Longest Increasing Subsequence

Given an integer array nums, return the number of longest increasing subsequences.

Answer 318

1. Use 1D-DP with two arrays: count and length
2. If length[left] < length[right] + 1 -> new longest, count[left] = count[right]; length[left] = length[right] + 1
3. If length[left] == length[right] + 1 -> one more longest, count[left] += count[right]
4. Find and sum all count[i] where length[i] == longest

O(n^2) time
O(n) space

Question 319

Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

Answer 319

1. Use minHeap to store one value from each list
2. Track currentRangeMax
3. If end - start > currentRangeMax - minHeap.poll().val -> update range
4. If current.idx < nums.get(current.row).size() -> add next and update currentRangeMax

O(nlog m) time
O(m) space

Question 320

Delete Operation for Two Strings

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Answer 320

1. Use 2D-DP to find longest common subsequence
2. Return w1.length() + w2.length() - 2 * lcs

O(m * n) time
O(m * n) space

Question 321

Flatten Binary Tree to Linked List

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.

Answer 321

1. Use iterative reversed post-order traversal
2. s.push(current.right)
3. s.push(current.left)
4. If !s.isEmpty() -> current.right = s.peek()
5. current.left = null

O(n) time
O(n) space

Question 322

Earliest Possible Day of Full Bloom

You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed takes time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each:

• plantTime[i] is the number of full days it takes you to plant the ith seed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have worked plantTime[i] days on planting it in total.
• growTime[i] is the number of full days it takes the ith seed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever.

From the beginning of day 0, you can plant the seeds in any order.

Return the earliest possible day where all seeds are blooming.

Answer 322

1. Sort seeds by growTime DESC
2. timeSpent = currentPlantTime + seed.plantTime + seed.growTime
3. bloom = Math.max(bloom, timeSpent)
4. currentPlantTime += seed.plantTime
5. Return bloom

O(nlog n) time
O(n) space

Question 323

Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Answer 323

1. AND of range is common prefix with all the rest digits as zeroes
2. while left != right -> left >>= 1; right >>= 1; shift++
3. Return left << shift

O(1) time
O(1) space

Question 324

Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Answer 324

1. Sort intervals and indexedQueries
2. Iterate queries:
3. Add intervals that start before query to minHeap
4. Pop intervals that end before query
5. Interval on top it the shortest one

O(nlon n + qlog q) time
O(n + q) space

Question 325

Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Answer 325

1. Use 1D-DP: dp[0] = 1
2. factor1 = max(dp[j], j) – factor j or use as is
3. factor2 = max(dp[i - j], j)
4. dp[i] = max(dp[i], max(factor1, factor2))
5. Return dp[n]

O(n^2) time
O(n) space

Question 326

Edit Distance

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

Answer 326

1. Use 2D-DP: dp[i][0] = i; dp[0][j] = j
2. If equal -> dp[i][j] = dp[i - 1][j - 1]
3. replace = dp[i - 1][j - 1] + 1
4. add = dp[i][j - 1] + 1
5. delete = dp[i - 1][j] + 1
6. dp[i][j] = min(replace, add, delete)

O(m * n) time
O(m * n) space

Question 327

Shuffle an Array

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Answer 327

1. Use Fisher Yates algo
2. For i = [N - 1, 0] -> j = random.nextInt(i + 1); swap(i, j)
3. Return nums

O(n) time
O(n) space

Question 328

Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

Answer 328

Use DFS with cached results (memo instead of visited)

O(m * n) time
O(m * n) space

Question 329

Random Pick with Weight

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

Answer 329

1. Use prefix sums to encode ranges
2. Use BS to find first greater than random pick

O(log n) time
O(n) space

Question 330

Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Answer 330

1. Use slopes: slope = (y1 - y2) / (x1 - x2)
2. If x1 == x2 -> slope = Double.POSITIVE_INFINITY
3. Iterate through all possible points
4. For each point fill slopesToPointsCountMap
5. Return globalMax

O(n^2) time
O(n^2) space

Question 331

First Missing Positive

Given an unsorted integer array nums, return the smallest missing positive integer.

Answer 331

1. First missing positive is in [0, N] range or equal to N + 1
2. Kill all non-positive values: nums[i] = n + 1
3. Use array as hashtable: if number exists mark its index with negative value
4. Find first negative value or return n + 1

O(n) time
O(1) space

Question 332

Insufficient Nodes in Root to Leaf Paths

Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree.

A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than limit.

Answer 332

1. Use recursive remove(root, currentSum, limit)
2. If isLeaf() -> return currentSum >= limit ? root : null
3. remove(left); remove(right)
4. Return isLeaf() ? null : root

O(n) time
O(h) space

Question 333

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Answer 333

1. Use 2D-DP and prefix sums
2. dp[row + 1][col + 1] = dp[row][col + 1] + dp[row + 1][col] + matrix[row][col] - dp[row][col]
3. regionSum = dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1]

O(1) time
O(n) space

Question 334

Maximum Performance of a Team

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Answer 334

1. Sort engineers by efficiency DESC
2. Build minHeap for speed
3. Iterate through engineers
4. topSpeedsSum += engineers[i].speed
5. topSpeedsSum -= minHeap.poll()
6. currentPerformance = topSpeedsSum * engineers[i].efficiency
7. Return maxPerformance

O(nlog n) time
O(n) space

Question 335

IPO

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

Answer 335

1. Sort projects by capital ASC
2. Build maxHeap for profits
3. For i = [0, k):
4. While current < projects.length && projects[current].capital <= maxCapital -> maxHeap.offer(current.profit)
5. If no projects available -> break
6. maxCapital += maxHeap.poll()

O(nlog n) time
O(n) space

Question 336

Count Complete Tree Nodes

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 2h nodes inclusive at the last level h.

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

Answer 336

1. Find depth by going left
2. Find the number of nodes on the last level with BS: [0; 2^depth - 1]
3. Use isExist(root, mid, depth) for BS condition
4. In isExist() run BS one more time to reconstruct the path from root to node: for i = [0; 2^depth - 1]
5. Return 2^depth - 1 + lastLevelNodesNumber

O(log n * log n) time
O(1) space

Question 337

Minimum Path Sum

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.

Answer 337

Use 2D-DP

O(m * n) time
O(m * n) space

Question 338

Perfect Squares

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Answer 338

Use 1D-DP of recursion with memo

O(n * sqrt(n)) time
O(n) space

Question 339

Alien Dictonary

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language’s dictionary, where the strings in words are
sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there is no solution, return "". If there are multiple solutions, return any of them.

Answer 339

1. Build adjList: add all chars, than add all edges
2. If word2 is prefix of word1 -> return ""
3. To find edge look for first non match in two words
4. Run topological sort via DFS
5. Return "" is there’re cycles
6. Return sortedChars.reverse().toString()

O(n) time
O(n) space

Question 340

Design In-Memory File System

Answer 340

Use Trie

Question 341

Can Make Arithmetic Progression From Sequence

A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Given an array of numbers arr, return true if the array can be rearranged to form an arithmetic progression. Otherwise, return false.

Answer 341

1. Compute min and max
2. diff = (max - min) / (N - 1)
3. Check for duplicates and if (max - num) % diff == 0

O(n) time
O(1) space

Question 342

Palindrome Pairs

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

• 0 <= i, j < words.length
• i != j
• words[i] + words[j] (the concatenation of the two strings) is a palindrome

Return an array of all the palindrome pairs of words.

Answer 342

1. For each word check 3 cases
2. map.containsKey(reversedWord)
3. isPalindrome(suffix) && map.containsKey(reversedPrefix)
4. isPalindrome(prefix) && map.containsKey(reversedSuffix)

O(n * length^2) time
O(n^2 + length^2) space

Question 343

Maximum Frequency Stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

• void push(int val) pushes an integer val onto the top of the stack
• int pop() removes and returns the most frequent element in the stack

If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.

Answer 343

valueToFreqMap, freqToStackMap, maxFreq

O(1) time
O(n) space

Question 344

Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

Answer 344

1. Use recursive isInterleave(s1, s2, s3, p1, p2, p3, seen)
2. If p1 == s1.length() -> return s2.substring(p2).equals(s3.substring(p3))
3. If p2 == s2.length() -> return s1.substring(p1).equals(s3.substring(p3))
4. If seen[p1][p2] -> return false
5. Return takeFirst || takeSecond

O(m * n) time
O(m * n) space

Question 345

Count Negative Numbers in a Sorted Matrix

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Answer 345

1. Iterate from top-left corner
2. count += N - row
3. Return count

O(m * n) time
O(1) space

Question 346

Employee Free Time

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Answer 346

1. Sort intervals
2. Use minHeap to store K intervals at any time
3. If current.start > maxEnd -> freeTime.add(maxEnd, current.start)
4. Return freeTime

O(nlog k) time
O(k) space

Question 347

Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.

Answer 347

1. Use two-pointers window
2. Expand window, than shrink it if k < 0
3. Return right - left

For stream: use Queue to track previous zeroes and update max = max(max, right - left + 1)

O(n) time
O(1) space

Question 348

Sum in a Matrix

You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:

From each row in the matrix, select the largest number and remove it. In the case of a tie, it does not matter which number is chosen.
Identify the highest number amongst all those removed in step 1. Add that number to your score.
Return the final score.

Answer 348

1. Sort each row
2. Return sum of max elements in every col

O(m * nlog n + m * n) time
O(log n) space

Question 349

Maximum Number of Moves in a Grid

You are given a 0-indexed m x n matrix grid consisting of positive integers.

You can start at any cell in the first column of the matrix, and traverse the grid in the following way:

From a cell (row, col), you can move to any of the cells: (row - 1, col + 1), (row, col + 1) and (row + 1, col + 1) such that the value of the cell you move to, should be strictly bigger than the value of the current cell.

Return the maximum number of moves that you can perform.

Answer 349

1. Use 2D-DP starting from col = M - 2
2. Find max within first col of dp[][0]

O(m * n) time
O(m * n) space

Question 350

Merge Triplets to Form Target Triplet

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

Answer 350

1. Skip triplets, that have values greater than any of the target’s
2. result = max(result, triplet)
3. Return Arrays.equals(result, target)

O(n) time
O(1) space

Question 351

Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending 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 (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Answer 351

1. Use minHeap
2. Add k pairs: offer(new Tuple(nums1[i], nums[0], 0))
3. result.add(minHeap.poll())
4. If current.index < nums2.length - 1 -> offer(new Tuple(current.first, nums2[current.index + 1], current.index + 1))
5. Return result

O(k logk) time
O(k) space

Question 352

Number of Recent Calls

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

• int ping(int t) – Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Answer 352

Use Queue to eliminate timestamp - hits.peek() > 3000

O(n) time
O(n) space

Question 353

Snapshot Array

Implement a SnapshotArray that supports the following interface:

• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Answer 353

1. Use array buckets with TreeMap inside
2. Find first less than or equal snapshot with floorEntry(snapshotId)

O(log n) for get() and O(1) for snap() and set()
O(n) space

Question 354

Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Answer 354

1. Build adjList with indexed Tickets
2. Run recursive backtrack until result.size == tickets.size() + 1

O(V ^ E) time
O(V + E) space

Question 355

Equal Row and Column Pairs

Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).

Answer 355

1. Build freqMap of rows: Arrays.toString(row)
2. Iterate columns and count pairs

OR

1. Transpose matrix
2. Compare row by row

O(n^3) time
O(n^2) space

Question 356

Online Stock Span

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock’s price for the current day.

Answer 356

1. Use mono decreasing Stack
2. while price > peek().price -> span += poll().span`
3. push(new Record(span, price))

O(n) time
O(n) space

Question 357

Total Cost to Hire K Workers

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

• You will run k sessions and hire exactly one worker in each session.
• In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
• If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
• A worker can only be chosen once.

Return the total cost to hire exactly k workers.

Answer 357

Use minHeap with two pointers

O(n logn) time
O(n) space

Question 358

Swim in Rising Water

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Answer 358

1. Use modified Dijkstra Algo
2. Use minHeap to choose minimum possible cell and update max = max(max, cell)
3. Return max

O(n logn) time
O(n) space

Question 359

Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Answer 359

1. Use recursive maxCoins(nums, left, right, int[][] memo)
2. If left > right -> return 0
3. If memo[][] > 0 -> return memo[][]
4. Burst i baloon last
5. burstLeft = maxCoins(left, i - 1); burstRight = maxCoins(i + 1, right)
6. currentBurst = nums[left - 1] + nums[i] + nums[right + 1]
7. Update max

O(n^3) time
O(n^2) space

Question 360

H-Index

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith 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.

Answer 360

Sort and iterate from behind while citations[i] > hIndex

OR

1. By definition, hIndex can be in range [0, N]
2. Use counting sort
3. Check every possible hIndex, counting the totalCitations
4. If totalCitations >= hIndex -> return

O(n) time
O(n) space

Question 361

Remove Duplicates from Sorted Array II

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.

Answer 361

1. If nums[i] == nums[i - 1] -> duplucates++
2. Else -> duplicates = 1
3. If duplicates <= 2 -> nums[pointer] = nums[i]; pointer++

O(n) time
O(1) space

Question 362

Search in Rotated Sorted Array II

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length).

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

Answer 362

1. while (left <= right)
2. Skip duplicates: left++; right--
3. Run modified BS: If nums[mid] >= nums[left]

O(log n) average, O(n) worst
O(1) space

Question 363

Construct Quad Tree

Answer 363

1. Use recursive(x, y, length)
2. If all children are leaves and have the same value -> return leaf
3. Else -> return root

O(n^2) time
O(log n) space

Question 364

Detect Squares

Answer 364

1. Use Map of points
2. Find diagonal point: abs(x1 - x2) == abs(y1 - y2)
3. Find two corner points in Map
4. Return diagonalCount * corner1Count * corner2Count

O(1) for add(), O(n) for count()
O(n) space

Question 365

Distinct Subsequences

Given two strings s and t, return the number of distinct
subsequences of s which equals t.

Answer 365

1. Use recursive count(s, t, sPointer, tPointer, int[][] memo)
2. On each step either skip or pick

O(m * n) time
O(m * n) space

Question 366

Greatest Common Divisor of Strings

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Answer 366

1. Iterate i = [min(str1.length(), s2.length()), 1]
2. Check if [0, i] substring is gcd
3. Return str1.replaceAll(candidate, "").isEmpty() && str2.replaceAll(candidate, "").isEmpty()

O(min(m, n) * (m + n)) time
O(min(m, n)) space

Question 367

Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

• '.' Matches any single character.​​​​
• '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Answer 367

1. Use recursive isMatch(s, t, sPointer, tPointer, int[][] memo)
2. Check for current match
3. If next is start – either pick or skip
4. Else -> move on

O(m * n) time
O(m * n) space

Question 368

Number of Increasing Paths in a Grid

You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.

Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell.

Answer 368

1. Use DFS with cache instead of visited
2. count = 1
3. count += dfs()
4. Return count

O(m * n) time
O(m * n) space

Question 369

Check If a Number Is Majority Element in a Sorted Array

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element, or false otherwise.

A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.

Answer 369

1. Use BS to find first occurence of target
2. Check if firstOccurentce + nums.length / 2 == target

O(log n) time
O(1) space

Question 370

Candy

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.

Answer 370

1. Go left: candies[i] = candies[i - 1] + 1
2. Go right: candies[i] = max(candies[i], candies[i + 1] + 1)
3. Count total

O(n) time
O(n) space

Question 371

Dota2 Senate

Answer 371

1. Use two Queue
2. Poll two senators: the one with the BIGGER index looses
3. Offer winner back: offer(winner + senate.length())
4. Return radiant.isEmpty() ? "Dire" : "Radiant"

O(n logn) time
O(n) space

Question 372

Closest Binary Search Tree Value

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

Answer 372

1. Use iterative inorder traversal
2. If predecessor <= target && root.val >= target
3. Return predecessor or root.val

O(n) time
O(n) space

Question 373

Determine if Two Strings Are Close

Two strings are considered close if you can attain one from the other using the following operations:

• Operation 1: Swap any two existing characters.
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Answer 373

1. Build two freqMap
2. If keySet() aren’t equal -> return false
3. Sort values()
4. If values() aren’t equal -> return false

O(n) time
O(n) space

Question 374

Integer to Roman

Given an integer, convert it to a roman numeral.

Answer 374

1. Hardcode values and symbols in DESC order
2. Append symbols[i] until values[i] <= num

O(1) time
O(1) space

Question 375

Longest Arithmetic Subsequence

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Answer 375

1. Use 1D-DP: Map<Integer, Integer>[] dp
2. diff = nums[right] - nums[left]
3. dp[right].put(diff, dp[left].getOrDefault(diff, 1) + 1)
4. Update longest
5. Return longest

O(n^2) time
O(n^2) space

Question 376

Sqrt(x)

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.

Answer 376

1. Use BS from 2 to x / 2
2. Return mid if sqrt(x) is an integer
3. Return right being the rounded down result otherwise

O(log n) time
O(1) space

Question 377

Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Answer 377

1. Try to find patterns and use 1D-DP
2. fullyCovered[n + 1]
3. partiallyCovered[n + 1]

O(n) time
O(n) space

Question 378

Maximum Sum Circular Subarray

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

Answer 378

1. Use modified Kadane Algo
2. Keep track of min, max and total sums
3. If max > 0 -> return max(max, total - min)
4. Else -> return max

O(n) time
O(1) space

Question 379

Substring with Concatenation of All Words

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

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

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

Answer 379

1. Build freqMap for words
2. For each index in s -> copy words and check isMatch()

O(s * w * wl) time
O(w + wl) space