Algo Advance

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

Question List Question 1:  167. Two Sum II - Input Array Is Sorted Question 2:  2337. Move Pieces to Obtain a String Upper Layer

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

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