Two Pointers (Part 2)

532	K-diff Pairs in an Array

Two pointers, O(NlgN) time and O(1) space

(a) sort the array

(b) Use the first pointer (the rear pointer) to iterate each element in the array. Set the second pointer (the front pointer) to first pointer plus one.

(c) while the second pointer is still valid (index within range) and the diff between two pointer is less than k. increase the front pointer.

(d) check whether the diff is exactly equal to k, if so increase the counter.

(e) while next of rear pointer is still valid and the pointee value is equal to the next pointee, increase rear pointer

(f) return the counter in the end.

826	Most Profit Assigning Work

(a) zip difficulty and profit as jobs.
(b) sort jobs and sort 'worker'.
(c) 2 pointers idea, for each worker, find his maximum profit he can make under his ability.
Because we have sorted jobs and worker, we will go through two lists only once. It will be only O(M+N).
Time Complexity O(NlogN + MlogM), as we sort list. Space complexity O(N) space as we created jobs.

763	Partition Labels

The idea here is to find the max ending index for all the letters encountered so far. And push that length into the result. And continue check next group.
(1) For brute force solution.   We iterate each letter in the string and calculate the max Ending (find_last_index(S[i]) so far, if the current index value is equal to the max ending index, that means we could split at max ending index without leaving same letters to later group.  Since we repeatedly call find_last_of() in the for loop. This is O(N^2) time and O(1) space.

(2) A clever solution is using hash table to save the last_index for each letter and use that value instead of calling find_last_of() lib function. In that case we only calculate once. It is O(N) time and O(1) space (just need to save 26 last indices value)

86	Partition List

Use two pointers leftTail and rightTail. Initialize them to two head nodes (to save its head, say leftHead, rightHead which are set to head initially). While the list is not NULL loop each node in the list, if head->val < x, add to left list and move left pointer to its next, otherwise add to right list, move right pointer to its next. For both cases move head to its next. Finally set leftTail->next = rightHead->next. rightTail->next = NULL, and return leftHead->next.

Here

142	Linked List Cycle II

Suppose there are m nodes before the cycle (including the first one in the cycle)
and the cycle has n nodes, and fast and slow pointer meets at the (m + k) th node
in the cycle. The idea here is that at the meeting point, slow pointer has walked
(m + k) steps, since the faster walks twice as the slower pointer, it has walked
2 * (m + k) steps. Suppose fast pointer traveled N more time cycles before finally
encounter the slower pointer. Then we have 2 * (m + k) - N * n = m + k
i.e.: m + k = N * n. (N = 1, 2, ...). We transform this equation to the following
then it will be more clear. m = N * n - k. Which means if we pull the slow pointer
back to the beginning and leave fast pointer where it meets slow pointer.  And let
both pointer move forward by 1 node each time. When slow arrives at the m-th node.
faster will arrive at (m + k) + (N * n - k) = m +  N * n. i.e: faster walks another
N times of the cycle and arrives at node m, which is the first node in the cycle.

Sliding Window

713	Subarray Product Less Than K

Our loop invariant is that left is the smallest value so that the product in the window prod = nums[left] * nums[left + 1] * ... * nums[right] is less than k.

For every right, we update left and prod to maintain this invariant. Then, the number of intervals with subarray product less than k and with right-most coordinate right, is right - left + 1. We'll count all of these for each value of right.

16	3Sum Closest

Improved on 1, instead of brute force emuerate every pair for j, k we could first sort the array in ascending order. And let j = i + 1, and k = n - 1. and check each pair of i,j,k has closer sum. If so update the result. When we find a sum that is less than target we move j forward by 1. When we find a sum that is larger or equal to target we move k backward by 1 until j < k no longer holds, we still could get the same result as in the brute force solution. But now the time complexity is only O(N^2) and space is O(1)

15

3Sum

Similar to 16, except we could have duplicates.

for i from 0 to n - 2

    Set target = -nums[i]

    triples = {nums[i], nums[j], nums[k]}

    while (j < k)

           sum = nums[j] + nums[k]

            if (sum < target)

                 j++;

            else if (sum > target)

                 k--;

            else

                while (j < n - 1 && triples[1] == nums[j]) j++; // go to next non triples[1] value

                while (k >= 0 && triples[2] == nums[k]) k--;  // go to next non triples[2] value

                result.insert(triples);

     while (i < n -2 && nums[i] == nums[i+1]) i++;  // go to next non duplicate nums[i]

O(N^2) time and O(N^2) space, O(1) extra space.

18

4Sum

   Similar to 15  3Sum. Only difference is one more level loop. And you can do some early exit checks to make it faster. Like if first 4 elements already > target early exit. If first 1 and last three elements sum < target, continue next loop.  

O(N^3) time and O(N^3) space, O(1) extra space.

567	Permutation in String

(1) Use two hash map  mp1, mp2 (either unordered_map or vector to mimic map) to count the char frequency of the first N1 chars in both s1 and s2.
(2) Check whether mp1 is equal to mp2. if so, meaning permutation of s1 is a substring of s2. return true.
(3) Otherwise, starting from N1 position of s2, add one new char to the sliding window end and delete one char from the window begin and increase/decrease the corresponding char frequency accordingly. Check whether mp1 is equal to mp2, if so, meaning permutation of s1 is a substring of s2. return true.
(4) If after the loop,  no early exit, meaning permutation of s1 is not a substring of s2.

287	Find the Duplicate Number

Similar to 142 Linked List Cycle II,  expect we know there is doomed to be a cycle. So we don't have to check the case that doesn't have a cycle. So in short, use fast and slow pointer. Let fast move 2 steps at a time and slow move 1 step at a time until they meet. And then pull fast to the beginning of the list again. Let the two pointers move   at the same pace until they meet. Then the meeting point is the duplicate number.

524	Longest Word in Dictionary through Deleting

 Wihtout sorting: O((L + S) * D) = O(D(L + S)), O(L) space
Since sorting the dictionary could lead to a huge amount of extra effort, we can skip the sorting and directly look for the strings x in the unsorted dictionary $d$D such that $x$is a subsequence in $s$ If such a string s $x$is found, we compare it with the other matching strings found till now based on the required length and lexicographic criteria. Thus, after considering every string in D we can obtain the required result.

80	Remove Duplicates from Sorted Array II

tail = 0;

for (int i = 0;  i < nums.size(); i++)

          if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet

                nums[tail++] = nums[i];

return tail

Please note, we are comparing nums[i] with nums[tail - 2] not nums[i - 2]

DNF (Dutch National Flag) problem, 3 pointers

75	Sort Colors

It’s actually Dutch national flag problem (DNF).

[, i): 0
[i, j]: 1
(k, ...]: 2
Once j goes over k, the sorting is complete

Before that, check the value of nums[j]:
(a) If nums[j] == 0, swap with nums[i] and increase both i,j
(b) If nums[j] == 1, no swap needed, just increase j
(c) If nums[j] == 2, swap with nums[k], only decrease k.

j <= k, not j < k. We need equal, otherwise 2, 0, 1 won't work. Because when j == k, it is possible
that the number is 0, we still need to swap it with 1.