Skip to main content

Posts

Graph Question - Hard Level - Question 2

2392. Build a Matrix With Conditions You are given a positive integer k. You are also given: a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti]. The two arrays contain integers from 1 to k. You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0. The matrix should also satisfy the following conditions: The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1. The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1. Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix. Constraints: 2 <= k <= 400 1 <= rowConditions.length, colConditions.length <= 10^4 rowConditions[i].length == c...
Post a Comment
Read more
Recent posts

Double Pointers - Question 2

2337. Move Pieces to Obtain a String You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where: The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right. The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces. Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false. Constraints: n == start.length == target.length 1 <= n <= 10^5 start and target consist of the characters 'L', 'R', and '_'. Analysis: The n could be pretty large, so we need to find an algorithm either O(N) or O(Nlog(N)). Some key observations: 1. th...
Post a Comment
Read more

Double Pointers - Question 1

167. Two Sum II - Input Array Is Sorted Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space. Constraints: 2 <= numbers.length <= 3 * 104 -1000 <= numbers[i] <= 1000 numbers is sorted in non-decreasing order. -1000 <= target <= 1000 The tests are generated such that there is exactly one solution. Analysis: The array is sorted, so we may want to consider binary search, but actually we can use a two-pointer method to quickly solve this problem, which is faster than the binary searc...
Post a Comment
Read more

Double Pointers

Double Pointers is one of the common tricks used in algorithm interviews. For some circumstances, for example, one or two sorted arrays, we can use two pointers to track the loop process. The final answer can be updated during the looping, and obtained when the loop is done. The logic behind the double pointers is that for every step, we just need to move one of the two pointers, or two of them. The optimal or final answer can be converged by doing this. Thus the time complexity is linear, and the space complexity is constant. One of the key step is that we have to make sure (or proof) by moving the two pointers, we will not miss the possible local optimal solutions, which then guarantees that we will obtain the global optimal solutions after finishing the looping. Question List Upper Layer
Post a Comment
Read more

Priority_queue - Question 5

692. 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. Constraints: 1 <= words.length <= 500 1 <= words[i] <= 10 words[i] consists of lowercase English letters. k is in the range [1, The number of unique words[i]] Analysis: This question is quite straightforward. We can use a priority_queue to keep the top K valid elements. One difficulty may be about the comparator of the priority_queue.  In C++, the default order of the priority_queue is with the largest one on the top. But in this question, we need choose the top K with the largest count, so we need a reversed priority_queue. And more, for the same count, we need to choose the one with the lexicographical order. So we need to take care of this in the comparator. See the code below: class Solution { public: typedef pair<...
Post a Comment
Read more

Graph Question - Hard Level - Question 1

2246. Longest Path With Different Adjacent Characters You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i. Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them. Constraints: n == parent.length == s.length 1 <= n <= 10^5 0 <= parent[i] <= n - 1 for all i >= 1 parent[0] == -1 parent represents a valid tree. s consists of only lowercase English letters. Analysis For this question, we need to construct a graph, or more specifically, a n-nary tree. How to construct the graph/tree? What we only know is the parent array. So we need to go through the parent array and constr...
Post a Comment
Read more