Solution to LeetCode Problems: Unique Paths II

Unique Paths II

Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.

Thoughts:
We cannot use the combination trip anymore. Are we forced to use graph search?
Set the paths to the top-left of the grid, i.e. (0,0) as 1, if not blocked. Then any point in the grid has the number fo unique paths:

1. if blocked  
2.   0  
3. else  
4.   path_from_left + path_from_top  

So we can simply traverse the grid row by row and fill up the values. Extra memory allocation is not necessary, we can use the original grid.


Solution:

1. class Solution {  
2. public:  
3.     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {  
4.         const size_t RR = obstacleGrid.size();  
5.         const size_t CC = obstacleGrid[0].size();  
6.           
7.         // fill up the grid system  
8.         for(size_t r = 0; r < RR; ++r)  
9.             for(size_t c = 0; c < CC; ++c)  
10.             {  
11.                 if (obstacleGrid[r][c] == 1)  
12.                     // blocked...  
13.                     obstacleGrid[r][c] = 0;  
14.                 else if (r == 0 && c == 0)  
15.                     // starting point  
16.                     obstacleGrid[r][c] = 1;  
17.                 else {  
18.                     int right_ways = (c == 0 ? 0 : obstacleGrid[r][c-1]);  
19.                     int top_ways = (r == 0 ? 0 : obstacleGrid[r-1][c]);  
20.                     obstacleGrid[r][c] = right_ways + top_ways;  
21.                 }  
22.             }  
23.           
24.         return obstacleGrid[RR - 1][CC - 1];  
25.     }  
26. };  

Solution to LeetCode Problems: Unique Paths

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.


Thoughts:
Of course, this can be solved by applying either DFS or BFS on a directed graph. Any better solution?
Since the robot can only choose "right" or "down", the total number of each movement are fixed to (m+n-2). We can first pick up (m-1) "down" moves, and the other movements can be "right" direction only.
So the total number of unique paths are Combination(m+n-2, m-1).
The combination has factorial calculations, so we have to be careful avoiding overflow. Here the algorithm is taken from TAOCP.

Solution:

1. class Solution {  
2. public:  
3.     unsigned long long  
4.     choose(unsigned long long n, unsigned long long k) {  
5.         if (k > n) {  
6.             return 0;  
7.         }  
8.         unsigned long long r = 1;  
9.         for (unsigned long long d = 1; d <= k; ++d) {  
10.             r *= n--;  
11.             r /= d;  
12.         }  
13.         return r;  
14.     }  
15.   
16.     int uniquePaths(int m, int n) {  
17.         if (m == 1 || n == 1)  
18.             return 1;  
19.               
20.         if (m < n) swap(m, n);  
21.           
22.         return choose(m+n-2, n-1);         
23.     }  
24. };  

Solution to LeetCode Problems: Valid Sudoku

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character'.'.

A partially filled sudoku which is valid.

Thoughts:
Mark every used number in a row, column or block. When a re-marking occurs, return false. Note the method used to calculate the block ID using row and column indices.

Solution:

1. // ⑨ ばか
2. #define BAKA 9  
3.   
4. class Solution {  
5. public:  
6.     bool isValidSudoku(vector<vector<char> > &board) {  
7.         array<bool, BAKA> row[BAKA];  
8.         array<bool, BAKA> col[BAKA];  
9.         array<bool, BAKA> box[BAKA];  
10.   
11.         // as standard C array  
12.         // the variables are not initialized...  
13.         for(auto r = 0; r < BAKA; ++r)  
14.             for(auto c = 0; c < BAKA; ++c)  
15.                 row[r][c] = col[r][c] = box[r][c] = false;  
16.   
17.         for(auto r = 0; r < BAKA; ++r)  
18.             for(auto c = 0; c < BAKA; ++c)  
19.             {  
20.                 char ch=board[r][c];  
21.                 if (ch == '.')  
22.                     continue;   // blank, no effect  
23.                   
24.                 ch -= '1';  
25.                   
26.                 if (row[r][ch])  
27.                     return false;  
28.                 row[r][ch] = true;  
29.                   
30.                 if (col[c][ch])  
31.                     return false;  
32.                 col[c][ch] = true;  
33.                   
34.                 if (box[r / 3 * 3 + c / 3][ch])  
35.                     return false;  
36.                 box[r / 3 * 3 + c / 3][ch] = true;  
37.             }  
38.               
39.         return true;  
40.     }  
41. }; 

Solution to LeetCode Problems: Anagrams

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Thoughts:

What is the definition of anagrams?
One thing has to be thought over: do "" and "" together make a pair of anagrams?

After we defined anagrams, the algorithm straight in the mind is hash. What is a good hash algorithm? There are several possibilities. Two of them are: 1. hash by sorting the string; 2. hash by counting the number of used characters, respectively. The latter is used in the solution.

Solution:

1. class Solution {  
2. public:  
3.     struct StringHash  
4.     {  
5.         char hash[26];  
6.           
7.         StringHash(const string& str)  
8.         {  
9.             fill(hash, hash+26, 0);  
10.             for(auto& ch : str)  
11.                 ++ hash[ch - 'a'];  
12.         }  
13.           
14.         bool operator<(const StringHash& sh) const  
15.         {  
16.             for(size_t i = 0; i < 26; ++i)  
17.                 if ( this->hash[i] < sh.hash[i] )  
18.                     return true;  
19.                 else if ( this->hash[i] > sh.hash[i] )  
20.                     return false;  
21.             return false;  
22.         }  
23.     };  
24.   
25.     vector<string> anagrams(vector<string> &strs)   
26.     {  
27.         map<StringHash, vector<vector<string>::iterator>>  hash_map;  
28.   
29.         for(auto iter=begin(strs); iter != end(strs); ++iter)  
30.             hash_map[StringHash(*iter)].push_back(iter);  
31.   
32.         vector<string> ret;  
33.         for(auto hsm : hash_map)  
34.             if (hsm.second.size() >= 2)  
35.                 for(auto i : hsm.second)  
36.                     ret.push_back(*i);  
37.   
38.         return ret;  
39.     } 

Solution to LeetCode Problems: Count and Say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.
Note: The sequence of integers will be represented as a string.

Thoughts:
Scan the string while maintaining a "state" that counts the numbers. Save previous results for accelerating the next string generation.


Solution:

1. class Solution {  
2. public:  
3.     // save previous history for accelerated calculation  
4.     vector<string> history;  
5.       
6.     Solution()  
7.     {  
8.         history.emplace_back(string("1"));  
9.     }  
10.       
11.     string generate_seq(const string& in)  
12.     {  
13.         string generated;  
14.         char scratch[64];  
15.         char current = in[0];  
16.         int count = 0;  
17.           
18.         auto commit = [&]()  
19.         {  
20.             sprintf(scratch, "%d%c", count, current);  
21.             generated += scratch;  
22.         };  
23.           
24.         for(auto ch : in)  
25.             if (ch != current)  
26.             {  
27.                 // we met another character  
28.                 commit();  
29.   
30.                 count = 1;  
31.                 current = ch;  
32.             }  
33.             else  
34.                 ++count;  
35.           
36.         commit();   // commit the last continuous char accumulation  
37.         return generated;  
38.     }  
39.       
40.     string countAndSay(int n)   
41.     {  
42.         while(n-1 >= history.size())  
43.             // exploit the r-value reference  
44.             history.emplace_back(generate_seq(history.back()));  
45.               
46.         return history[n-1];  
47.     }  
48. };  

Solution to LeetCode Problems: Subsets

Subsets

Given a set of distinct integers, S, return all possible subsets.
Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Thoughts:
For a set with n elements, the number of subsets is 2^n. Every element has "chosen" or "not-chosen" state, this led direct use of bit operations.

Solution:

1. class Solution {  
2. public:  
3.     vector<vector<int> > subsets(vector<int> &S) {  
4.         sort(begin(S), end(S)); // ensure non-descending results  
5.           
6.         const size_t n = S.size();  
7.         const size_t num_sets = pow(2, n);  
8.           
9.         vector<vector<int>> ret(num_sets);  
10.       
11.         for(size_t bitwise = 0; bitwise < num_sets; ++bitwise)  
12.         {  
13.             size_t bit_chk = 1;  
14.             for(size_t bit = 0; bit < n; ++bit)  
15.                 if ((bit_chk << bit) & bitwise)  
16.                     ret[bitwise].push_back(S[bit]);  
17.         }  
18.           
19.         return ret;  
20.     }  
21. }; 

Solution to LeetCode Problems: Merge Sorted Array

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Thoughts:
A direct solution is, allocate an array with length [m+n] and merge. Then copy the merged array to the original array A. I strongly doubt if it would be the expected answer.

Let's assume only O(1) space could be used instead. Then we have to consider the exploit of excess space in array A, with length n. We can merge the two arrays there, and when the space is all used up, data at starting of A should be either useless (already merged) or at the right place (if all elements in B are smaller than A).

Then we rotate the array leftwise by m. Such coding can be implemented by three reverses: [0, m+n), [0, n), [n, m+n). This is illustrated in Programming Pearls.

Solution:

1. class Solution {  
2. public:  
3.     void merge(int A[], int m, int B[], int n) {  
4.         // Iterator used through merging  
5.         int merge_A = 0;   
6.         int merge_B = 0;  
7.           
8.         // merge is done at the end of m-th element, A[]  
9.         int merge_iter = m;  
10.           
11.         while(merge_A < m || merge_B < n)  
12.         {  
13.             // check if we reached the end of merge region, if so,   
14.             // start from beginning  
15.             if (merge_iter == m + n)  
16.                 merge_iter = 0;  
17.   
18.             if (merge_A == m)  // merge A is done  
19.                 A[merge_iter++] = B[merge_B++];  
20.             else if (merge_B == n) // merge B is done  
21.                 A[merge_iter++] = A[merge_A++];  
22.             else  
23.                 A[merge_iter++] = (A[merge_A] < B[merge_B] ? A[merge_A++] : B[merge_B++]);  
24.         }  
25.           
26.         // merge is complete, now the array looks like  
27.         // 4567 | 123  
28.         // so we need to reverse it -- ref. Programming Pearls  
29.         reverse(A, A+m);  
30.         reverse(A+m, A+m+n);  
31.         reverse(A, A+m+n);  
32.     }  
33. }; 

Solution to LeetCode Problems: Pow(x,n)

Pow(x, n)

Implement pow(x, n).

Thought:
1. Do it by loop.
2. Divide and conqueror, so the number of multiplications is reduced by half.

Solution:

1. class Solution {  
2. public:  
3.     double pow_proc(double x, int n) {  
4.         double p;  
5.         switch(n)  
6.         {  
7.             case 0:  
8.                 return 1;  
9.             case 1:  
10.                 return x;  
11.             default:  
12.                 p=pow_proc(x, n/2);  
13.                 if ((n & 1) == 0)  
14.                     return p*p;  
15.                 else  
16.                     return p*p*x;  
17.         }  
18.     }  
19.       
20.     double pow(double x, int n)  
21.     {  
22.         if (n < 0)  
23.             return 1.0/pow_proc(x, -n);  
24.         else  
25.             return pow_proc(x, n);  
26.     }  
27. };  

Solution to LeetCode Problems: Valid Parentheses

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Thoughts:
A stack should do the job. 

Solution:

1. class Solution {  
2. public:  
3.     char counterPart(const char ch)  
4.     {  
5.         switch(ch)  
6.         {  
7.             case '{':  
8.                 return '}';  
9.             case '[':  
10.                 return ']';  
11.             case '(':  
12.                 return ')';  
13.             default:  
14.                 return 0;  
15.         }  
16.     }  
17.   
18.     bool isValid(string s) {  
19.         stack<char> parenthesis;  
20.           
21.         for(auto ch: s)  
22.             if (ch == '(' || ch == '[' || ch == '{')  
23.                 parenthesis.push(ch);  
24.             else  
25.                 if (!parenthesis.empty() && ch == counterPart(parenthesis.top()))  
26.                     parenthesis.pop();  
27.                 else  
28.                     return false;  
29.           
30.         return parenthesis.empty();  
31.     }  
32. };  

Solution to LeetCode Problems: Sum Root to Leaf Numbers

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

Thoughts:
Traverse the binary tree by depth-first and record the numbers. When the leaf is met, the accumulated value is added up.


Solution:

1. /** 
2.  * Definition for binary tree 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
8.  * }; 
9.  */  
10. class Solution {  
11. public:  
12.     int Sum;  
13.       
14.     void TraverseProc(const TreeNode* node, int value)  
15.     {  
16.         const int VAL = value * 10 + node->val;  
17.           
18.         if (node->left == nullptr && node->right == nullptr)  
19.             Sum += VAL; // at a leaf  
20.         else  
21.         {  
22.             if (node->left != nullptr)  
23.                 TraverseProc(node->left, VAL);  
24.             if (node->right != nullptr)   
25.                 TraverseProc(node->right, VAL);  
26.         }  
27.     }  
28.   
29.     int sumNumbers(TreeNode *root) {  
30.         Sum = 0;  
31.         if (root != nullptr)  
32.             TraverseProc(root, 0);  
33.         return Sum;  
34.     }  
35. }; 

Solution to LeetCode Problems: Jump Game

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.


Thoughts:
Mark the last element as "reachable" since it is able to reach itself. Then traverse the array A[] backwards, and check if there is an element within the range the current element could reach marked as "reachable". If so, mark the current element as "reachable". The problem is solved when the first element is inspected.

Solution:

1. class Solution {  
2. public:  
3.     bool canJump(int A[], int n) {  
4.         // store the maximum index can be reached from the i-th index  
5.         vector<bool> reachable(n);  
6.         reachable[n-1] = true;  // it can always reach itself  
7.           
8.         auto reach_forward=[&reachable,n](const int index, const int dist) -> bool {  
9.             for(int fwd = index+1; fwd <= min(dist, n-1); ++fwd)  
10.                 if (reachable[fwd])   
11.                     return true;  
12.             return false;  
13.         };  
14.           
15.         // reverse iterate every previous element   
16.         for(int ri = n-2; ri>=0; --ri)  
17.             reachable[ri]=reach_forward(ri, A[ri]);  
18.               
19.         return reachable[0];  
20.     }  
21. };  

Thoughts:
The previous solution has the time complexity O(n^2). It works but too slow.

If we traverse the array forwardly, and mark the index of farthest element the current partition of the array as "so_far", then we can confirm the last element is reachable when "so_far" is larger than n-1 (we assume the first element has the index 0, as C/C++ defines). If we reached "so_far" but unable to update "so_far" to a value larger than n-1, then the last element cannot be reached. The array is iterated only once so the time complexity is O(n). So far so good.

Solution:

1. class Solution {  
2. public:  
3.     bool canJump(int A[], int n) {  
4.         // store the farthest element can be reached  
5.         int so_far = 0;  
6.           
7.         for(int iter=0; iter<=so_far; ++iter)  
8.             if ( (so_far = max(so_far, A[iter] + iter)) >= n-1 )  
9.                 return true;  
10.         return false;  
11.     }  
12. };  

Solution to LeetCode Problems: Balanced Binary Tree

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Thoughts:
When a tree node is considered as "balanced", the left and the right leaf nodes are both "balanced", and the difference between height of left and right leaf is at most 1. A recursive procedure can then be designed.

Also worthy to mention, there are several common used self-balanced binary tree alogorithms: AVL Tree and RB Tree.

Solution:

1. /** 
2.  * Definition for binary tree 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
8.  * }; 
9.  */  
10. class Solution {  
11. public:  
12.     pair<bool, int> TraverseProc(const TreeNode* node)  
13.     {  
14.         if (node == nullptr)  
15.             return make_pair(true, 0);  
16.               
17.         // check left branch  
18.         pair<bool, int> left_balance=TraverseProc(node->left);  
19.         if (!left_balance.first) return make_pair(false, 0);  
20.           
21.         // check right branch  
22.         pair<bool, int> right_balance=TraverseProc(node->right);  
23.         if (!right_balance.first) return make_pair(false, 0);  
24.           
25.         // check the current node  
26.         int balance_factor = left_balance.second - right_balance.second;  
27.         if (balance_factor>1 || balance_factor<-1)  
28.             return make_pair(false, 0);  
29.         else  
30.             return make_pair(true, max(left_balance.second, right_balance.second)+1);  
31.     }  
32.   
33.     bool isBalanced(TreeNode *root) {  
34.         // Note: The Solution object is instantiated only once and is reused by each test case.  
35.         return TraverseProc(root).first;  
36.     }  
37. }; 

Solution to LeetCode Problems: Merge k Sorted Lists

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity

Thoughts:
Standard merge-sort, k ways. This requires the original min(x, y) function to be extended to min(x, y, z, ...) function and a heap could be used.

Solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        using node_pair = pair<ListNode*, size_t>;
       
        // Note: By default, C++ will create a max-heap, but we need a min-heap
        auto comparison=[](const node_pair& n1, const node_pair& n2) -> bool {
            return n1.first->val > n2.first->val; 
        };
       
        // starting point of the list
        ListNode* new_start = new ListNode(0);
        ListNode* new_last = new_start;
       
        // Heap, storing the first node of each list
        vector<node_pair> v_nodes;
        v_nodes.reserve(lists.size());
       
        // initalize the heap
        size_t index=0;
        for(auto& t : lists)
        {
            if (t!=nullptr)
            {
                v_nodes.push_back(node_pair(t, index));
                t=t->next;
            }
            index++;
        }
        make_heap(begin(v_nodes), end(v_nodes),comparison);
       
        // Heap injector
        auto inject_heap=[&v_nodes,&lists,&comparison](const size_t list_id) -> void {
            if (lists[list_id]==nullptr)
                return;
            else
            {
                auto save = lists[list_id];
                lists[list_id]=save->next;
                v_nodes.push_back(node_pair(save, list_id));
                push_heap(begin(v_nodes), end(v_nodes), comparison);
            }
        }; 
       
        // Loop until the heap is empty
        while(!v_nodes.empty())
        {
            pop_heap(begin(v_nodes), end(v_nodes), comparison);

            auto t = v_nodes.back();
            v_nodes.pop_back();

            new_last->next = t.first;
            new_last = new_last->next;
           
            inject_heap(t.second);
        }
       
        // drop the head
        new_last=new_start;
        new_start=new_start->next;
        delete new_last;
       
        return new_start;
    }
};

Solution to LeetCode Problems: Length of Last Word

Length of Last Word
Given a string s consists of upper/lower-case alphabets and empty space characters' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.
Thoughts:
The straightforward thought is that we can iterate the string to the end and reverse-iterate the string until we get the last word. The time complexity is O(2n).

To reduce the time complexity to O(n), we can iterate it only once and record the word length we are meeting. When we found a space, the word length is then backuped and we can start a new recording. However, if two or more continuous spaces are found, special care is required.
Solution:

1. class Solution {  
2. public:  
3.     int lengthOfLastWord(const char *s) {  
4.         int last_word_length=0;  
5.         int this_word_length=0;  
6.         const char* p=s;  
7.         while(*p!=0)  
8.         {  
9.             if (*p++ == 32 )  
10.             {  
11.                 if (this_word_length != 0)  
12.                     last_word_length = this_word_length;  
13.                 this_word_length = 0;  
14.             }  
15.             else  
16.                 ++this_word_length;  
17.         }  
18.         if (this_word_length == 0)  
19.             return last_word_length;  
20.         else  
21.             return this_word_length;  
22.     }  
23. };  

Solution to LeetCode Problems: Two Sum

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Thoughts:

 

If the array is not sorted, then the brutal way time complexity is O(n^2) = n(n-1).

When treating search problem, sorting is usually helpful. After sort, we can use two pointers pointing at the beginning and the end of the array. If the sum of numbers at two pointers larger than target, left-move the pointer at right; otherwise right-move the pointer at last until the solution is found, which the problem ensured.

The algorithm has time complexity O(nlogn) + O(n) = O(nlogn). The first term is for sorting, and the second term is for searching. Before we sort, we need to record the original indices for each elements, this will require an extra O(2n) space complexity.

Solution：

1. class Solution {  
2. public:  
3.     typedef pair<int, size_t> valoffset_pair_t;  
4.       
5.   
6.     vector<int> twoSum(vector<int> &numbers, int target) {  
7.   
8.         vector<valoffset_pair_t> new_array;  
9.         // Preallocate the memory for faster push_back  
10.         new_array.reserve(numbers.size());  
11.           
12.         // generate the new array  
13.         int index=0;  
14.         for(auto i : numbers)  
15.             new_array.push_back(valoffset_pair_t(i, ++index));  
16.             // Note: here the index is already increased, so   
17.             // the new indices are not zero based  
18.           
19.         // sort it!  
20.         sort(begin(new_array), end(new_array),   
21.             [&](const valoffset_pair_t& v1, const valoffset_pair_t& v2) -> bool  
22.             {  
23.                 return v1.first < v2.first;  
24.             }  
25.         );  
26.           
27.         // now find the right pair using two pointers  
28.         auto p_left=begin(new_array);  
29.         auto p_right=end(new_array);   
30.         p_right--;  // make it locate at the last position  
31.         int sum = p_left->first + p_right->first;  
32.           
33.         // it is guaranteed to have one exact solution  
34.         while(sum!=target)  
35.         {  
36.             sum = p_left->first + p_right->first;  
37.             if (sum > target)  
38.                 p_right--;  
39.             else if (sum < target)  
40.                 p_left++;  
41.             else  
42.                 break;  
43.         }  
44.         return vector<int>(  
45.             {min(p_left->second, p_right->second),  
46.              max(p_left->second, p_right->second)});  
47.     }  
48. };