Algo Advance

1674. Minimum Moves to Make Array Complementary You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive. The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5. Return the minimum number of moves required to make nums complementary. Constraints: n == nums.length 2 <= n <= 10^5 1 <= nums[i] <= limit <= 10^5 n is even. Analysis: The brute force method works, for example, the pair sum range is [2, limit*2], so we can check the number of replacements needed for each sum, then pick up the smallest one. But the time complexity is O(N*limit), which could be as high as 10^10! So we need to find a faster method to pass the OJ. A faster algorithm is NOT easy to find, if do not have a good underst...

1109. Corporate Flight Bookings There are n flights that are labeled from 1 to n. You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range. Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i. Constraints: 1 <= n <= 2 * 10^4 1 <= bookings.length <= 2 * 10^4 bookings[i].length == 3 1 <= firsti <= lasti <= n 1 <= seatsi <= 10^4 Analysis: The naïve method is to fill in every fight with the number of seats booked. The overall time complexity is O(N^2), which cannot pass the online OJ. We do not have to do this. Instead, we can just label the starting and ending flights (since all the flights between them are the same). Or in the terminology of Sweep line, we can treat the flights range as an interval: the start flight is the start of the interval, and end...

2105. Watering Plants II Alice and Bob want to water n plants in their garden. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the ith plant is located at x = i. Each plant needs a specific amount of water. Alice and Bob have a watering can each, initially full. They water the plants in the following way: Alice waters the plants in order from left to right, starting from the 0th plant. Bob waters the plants in order from right to left, starting from the (n - 1)th plant. They begin watering the plants simultaneously. It takes the same amount of time to water each plant regardless of how much water it needs. Alice/Bob must water the plant if they have enough in their can to fully water it. Otherwise, they first refill their can (instantaneously) then water the plant. In case both Alice and Bob reach the same plant, the one with more water currently in his/her watering can should water this plant. If they have the same amount of water, then Alice ...

Brute Force - Question List Question 1:  Recover the Original Array Question 2: Watering Plants II More Questions Upper Layer

Recover the Original Array Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner: lower[i] = arr[i] - k, for every index i where 0 <= i < n higher[i] = arr[i] + k, for every index i where 0 <= i < n Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array. Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array. Note: The test cases are generated such that there exists at least one valid array arr. Constraints: 2 * n == nums.length 1 <= n <= 1000 1 <= nums[i] <= 10^9 The test cases are generated such that the...

The brute force is not a specific algorithm but a common concept. The basic idea is straightforward: when there is no faster way to solve the problem, we will incrementally try all the possible solutions. Some algorithms in the previous sections can be considered as brute force methods as well, for example, bfs, dfs, and backtracking. Or in general, if there is no clue to solve a problem, maybe we should start with the brute force way first: to solve the problem first, and then try to optimize it. Question List Upper Layer

973 K Closest Points to Origin Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2). You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in). Constraints: 1 <= k <= points.length <= 10^4 -10^4 < xi, yi < 10^4 Analysis: It is quite straightforward to find the K points that have the closest distances to the original point. Since we need to find the smallest values, the root of the priority_queue (pq) is the largest one for all the elements inside the pq. Once the size of pq is larger than K, we need to pop out one. See the code below: class Solution { public: typedef pair<int, int> pp; vector<vector<int>> kClosest(vector<vector<int>>& points, int k) { vector...

Graph - Question List Example     Question 1:  Clone Graph Easy Level Medium Level     Question 1:  Count Nodes With the Highest Score     Question 2:    2192. All Ancestors of a Node in a Directed Acyclic Graph Hard Level     Question 1:  2246. Longest Path With Different Adjacent Characters     Question 2:  2392. Build a Matrix With Conditions  Interview Questions More Questions Upper Layer 

Depth First Search - Question List Example     Question 1:  Number of Islands Easy Lvel     Question 1:  Maximum Depth of Binary Tree Medium Level     Question 1:  Path Sum II     Question 2:  2115. Find All Possible Recipes from Given Supplies Hard Level Interview Questions More Questions Upper Layer 

Bit Manipulation - Question List Example Easy Level Medium Level Hard Level Interview Questions More Questions Upper Layer

Breadth First Search - Question List  Example     Question 1:  Number of Islands  Easy Level     Question 1:  Binary Tree Level Order Traversal Medium Level     Question 1:  As Far from Land as Possible Hard Level     Question 1: Bus Routes Interview Questions More Questions Upper Layer

Dynamic Programming - Question List Example     Question 1:  Climbing Stairs Easy Level     Question 1:  Get Maximum in Generated Array     Question 2:  Unique Paths Medium Level     Question 1:  Decode ways     Question 2:  Dungeon Game Hard Level      Question 1.  Maximum Number of Points with Cost      Question 2.  Painting a Grid with Three Different Colors      Question 3.  Count Number of Special Subsequences      Question 4. Minimum Window Subsequence Interview Questions More Questions Upper Layer

Binary Search - Question List Example     Question 1:  Search Insert Position Easy Level     Question 1:  First Bad Version Medium Level     Question 1:  Search in Rotated Sorted Array Hard Level      Question 1:  Split Array Largest Sum      Question 2:  Minimum Window Subsequence      Question 3:  Nth Magical Number Interview Questions     Question 1:  Minimum steps to find a baseball More Questions Upper Layer

Recursion - Question List Example     Question 1:  Power of Two Easy Level     Question 1:  Base 7     Question 2:  Fibonacci Number Middle Level     Question 1:  Pow(x, n)     Question 2:  Count Good Numbers Hard Level     Question 1:  Special Binary String Interview Questions     Question 1:  Please describe the recursion concept to a 5 years old?     Question 2:  Please reverse a singly linked list using a recursion method More Questions Upper Layer

Sweep Line - Question List: Question 1: Minimum Meeting Room Needed Question 2:  Corporate Flight Bookings Question 3.  Minimum Moves to Make Array Complementary More questions Upper Layer

Question 1: The minimum meeting room needed Say we have had a list of meetings with start_time and end_time. For each meeting room, only one meeting can be hold once the meeting starts, and it cannot hold the next meeting until the first one ends. For example, if the first meeting start at 1 and end at 10, then the meeting room can only hold a second meeting starting at or later than 10. The question is to find the minimum number of meeting rooms needed to hold all the meetings. Example 1: meetings = [[2, 5], [4, 6], [5, 9]] Ans: 2 the first meeting room can hold: [2, 5], [5, 9]; the second meeting room can hold: [4, 6]. Example 2: meetings = [[1, 10], [2, 3], [3, 7], [4, 6], [5, 8], [6, 9], [7, 11], [10, 12]] Ans: 4 the first meeting room can hold: [1, 10], [10, 12]; the second meeting room can hold: [2, 3], [3, 7], [7, 11]; the third meeting room can hold: [4, 6], [6, 9]; the fourth meeting room can hold: [5, 8]. Analysis: As indicated by the second example, we can sort the meeting t...

300. Longest Increasing Subsequence Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]. Constraints: 1 <= nums.length <= 2500 -10^4 <= nums[i] <= 10^4 Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity? Analysis: This questions can be solved by dynamic programming (dp) with a time complexity of O(N^2), where N is the length of the array. The key point is to define dp[i] as the longest length of the increasing sequence ending with element arr[i]. The pseudo code is: for(int i=0; i<n; ++i) { for(int j=0; j<i; ++j) { if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1); } res = max(res, dp[i]); } The time complexity is O(N^2), which is not the optimal solution....

Binary Search - Hard Level - Question 3 878. Nth Magical Number A positive integer is magical if it is divisible by either a or b. Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 10^9 + 7. Analysis: Let us consider some examples first. Example 1, a = 4, b = 2. If b is dividable by a, then all the numbers which is dividable by a should be dividable by b as well. So the nth magical number should be n*b; Example 2, a = 3, b = 2. The multiples of 2 are: 2, 4, 6, 8, 10, 12, ... The multiple of 3 are: 3, 6, 9, 12, ... So the overlap is related to the minimum common multiple between a and b, and we need to remove the overlap which is double-counted. So now, we make some conclusions: 1. the upper bound of the nth magical number should be n*b, where a is the smaller one (or b <= a); 2. there are n*b/a magical numbers smaller than n*b; 3. there are n*b/(minimum common multiple) overlaps. Thus, the overall count is: n + ...

Union-Find - Question List Question 1: GCD Sort of an Array More Questions Upper Layer

Union-Find (UF) becomes one of the popular algorithms in the tech interview nowadays. As indicated by its name, UF contains two parts: union and find. The step of find is to find the root of the group; and the step of union is to unite two groups with different roots. A common implementation of the find function uses a recursive searching process. The end condition is when the root is that same as the key, or roots[key] == key; if roots[X] == X, roots[Y] == Y, and we need to connect them, then we just need to set roots[X] = Y. After this operation, all the elements with X as the root previously now points to Y as the root. So the group with root as X and group with root Y are united. (We can set roots[Y] = X as well, but now the connected group root is X). The roots could becomes very flat in the searching process, so the find process is of almost O(1) time complexity; the union is also of O(1), so the overall speed of UF is quite fast. One of the conditions for whether use UF is that:...

1998. GCD Sort of an Array You are given an integer array nums, and you can perform the following operation any number of times on nums: Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j]. Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise. Constraints: 1 <= nums.length <= 3 * 10^4 2 <= nums[i] <= 10^5 Analysis: One of the key information is that we can do the swap as many as needed, so the crux is to how to find the pair or group that can be swapped. Let say we have three elements: A, B and C. If A and B can swap, and B and C can swap, then A, B, and C can swap in any order. So it is easy to propagate this property to groups with more than 3 elements. Or more general: say we have a group of elements that can swap with each other. Now, we have a new element X. If X can swap with one element in t...