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> 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>` 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)` 2. Use `i = skip(String s, int i)` to skip characters 3. If `charAt(i) != charAt(j)` -> return `false` 4. If `(i >= 0 && j < 0) || (j >= 0 && i < 0)` -> return `false` 5. 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 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 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 subset, List> 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 children, boolean isTerminal)` 2. Insert each `word` character as a `Node` 3. While searching if `next == null` -> return `false` 4. Else return `current.isTerminal`for `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 tmp, List> 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 tmp, int start, List> 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 tmp, int remains, List 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 wordDict, Set 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 currentPath, int remains, List> 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 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[] 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()` 4. 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 `frequencyMap`s, 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 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 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 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 nodeToParent` to be able to treat the tree as a graph 2. Use BFS for level traversal (don't forget `Set 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)` 6. 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]))` 5. 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])` 3. `totalAmount += width * (boundaryHeight - heights[i])` 4. `start = prev.start` 5. `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 seen` 3. For `[N - 1; 0]`-> `tmpSet = new HashSet<>()` 4. `newSum = nums[i] + prev` 5. If `newSum == target` -> return `true` 6. `seen.addAll(tmpSet)` 7. 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^(n*n)) time** **O(9^(n*n)) 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 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 `0`s (land) and `1`s (water). An island is a maximal 4-directionally connected group of `0`s and a closed island is an island totally (all left, top, right, bottom) surrounded by `1`s. 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++` 4. 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 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 in`RED` 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 `Ticket`s 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[] 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**