Skip to main content

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

Comments

Post a Comment

Popular posts from this blog

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

Priority_queue - Question 4

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...
Post a Comment
Read more