Two pointers (Part 1)

344	Reverse String

Use two pointers i, j. keep switching elements at position i, j while i < j.

    string reverseString(string s) {

       for (int i = 0, j = s.size() - 1; i < j; i++, j--)

           swap(s[i], s[j]);

        

        return s;

    }

345	Reverse Vowels of a String

Similar with 344 Reverse String,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not.

283	Move Zeroes

Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero.

349	Intersection of Two Arrays

// O(NlgN + MlgN) time and O(N) space two pointers 

(a) Sort both array in O(NlgN) and O(MlgM) time

(b) Use two pointers i,j to iterate both arrays.

(c) if nums1[i] == nums2[j] put the either nums1[i] or nums2[j] into the result array. and increase both i, j. Also use a while loop to get rid od dup with nums1[i] and nums2[j]. i.e:  while (nums1[i] == nums1[i - 1])  i++;  while (nums2[j] == nums2[j - 1]) j++;

(d) else if (nums1[i] > nums2[j])  j++

(e) else  i++

350	Intersection of Two Arrays II

Similar with 349. But delete the two while loop lines that get rid of duplications.

Sliding Window (SW)

3	Longest Substring Without Repeating Characters

Sliding window O(N) time, O(K) space where K is the size of set Define a hash set and loop over each char in the string from left to right while the right side of the window is still within the range of string size check whether the current char is already in the set, if not: insert it into the set and move the right side right by 1, update maxCount if the current window size is greater that maxCount. If yes, erase the current element indicated by the left side of the window from the set and move the left side of window right by one. After the right side of the window exceeds string size. maxCount will be the  longest substring without repeating characters.

209	Minimum Size Subarray Sum

// O(N) time and O(1) space two pointers sliding window solution.
For the right pointer, keep moving forward and update the total sum in the for loop. In a inner loop,  we check whether the total sum is greater or equal than the target sum s, if so update the minLen and keep subtracting the left pointer from the total sum move the left pointer forward, after every subtraction check again whether the total sum is still greater or equal than s. Keep doing this until total sum  less than s and also update the minLen when necessary.  Then go to the outer loop to move the right pointer forward. After the loop, minLen will have the minimum Len that has total sum greater or equal than s.

167	Two Sum II - Input array is sorted

(1) Use hash map to save the elements encountered so far. And check whether target - current_num_val is already in the hash map, if so push both of their indices into the result array and return them.

(2) Two pointers, left pointer and right pointer. Let sum = numbers[left] + numbers[right], if sum == target, return {left + 1, right + 1}. Else if sum > target, right--, Else left++. If not early return  after the loop, return {0, 0} meaning not exist. O(N) time and (1) space.

(3) lg(N) time and O(1) space improved on (2). Instead of moving 1 by 1 from left or right. We could do binary search when sum is not equal target. If sum < target, we could left left = findNextGreaterOrEqual(numbers, left, right, target - numbers[right]); Else if sum > target, we could let right = findNextSmallOrEqual(numbers, left, right, target - numbers[left]); For findNextGreaterOrEqual and findNextSmallOrEqual,  it is just ordinary 3-part left <= right binary search.  Only difference is the former return left, and the later return right.

27	Remove Element

Using two pointers. Keep increase the right pointer by exactly one each time in the loop. While once copy and increase the right pointer pointed element to the left pointer pointed element when it is not the given value and increase the left pointer when copy happens.
O(N) time and O(1) space

26 Remove Duplicates from Sorted Array

O(N) time when the array is sorted, since if the last tail element is not equal nums[i] then all the other before it couldn't be equal to it. Just need to check whether the current element is equal to tail element or not ( The cleverpart here is use  nums[++tail] = nums[i] (not nums[tail++] = nums[i]) to not overwrite the first element in the duplication group). If so skip current element, otherwise, increase tail and copy the current to tail position. If the array is not sorted, we have to check all the element from 0 to tail and check whether any of them is equal to current element, if so skip it, otherwise copy it to tail element. In which case, the time complexity will be O(N^2)

11	Container With Most Water

O(N) time and O(1) space, since better candidadates must use the taller line of l and r

therefore we can use two pointer keep moving towards each other until they meet. Always

abandon the shorter line while moving.

88	Merge Sorted Array

The key is you should merge the two sorted array backwards to avoid insert and move elements. Since we know the last element index will be m + n - 1, which saves  the largest value of the two sorted array. And similarly, m + n -2 will save the second largest value ...


Linked List

141	Linked List Cycle

Idea: Using a fast pointer and a slow pointer. If there is a cycle, They will meet with each other. Otherwise, there is not cycle.

234	Palindrome Linked List

 First use fast and slow pointer to find the middle of the linkedList. And
 then reverse the second half of the linkedList. Finally compare the first
 half and the second half to determine whether it is a palindrome.

 Please note that you cannot write ListNode* slow = head, fast = head;

Since that means ListNode* slow = head; ListNode fast = head;
Please always only define a variable in one line to avoid such kind of issues

61	Rotate List

O(N) time and O(1) space.
(1) caculate the length of the LinkedList
(2) If head is NULL or head->next is NULL or k % len is 0 return head
(3) Use two pointers front and rear to find the ne head after rotation.
    specifically, let both pointers point to the head initially. Let front
.    pointer move k steps first. Move both pointer forward by 1 each time
    until front->next is NULL.
 (4) let  front->next = head; (connect), head = rear->next (reset), rear->next = NULL (break)

19	Remove Nth Node From End of List

(step 1) Let q walk n step first.
(step 2) Then both p and q walk forward at the same speed (one node each step) when q is NULL, p is the Nth element from the end

String

125	Valid Palindrome

Use two pointers i,j to compare char to char at the beginning and at the end. If encounter non letters and non numerical number (i.e !isalnum(c)) skip it, otherwise convert both char to upper case, if they are not equal, then this is not a valid palindrome, otherwise increase i and decrease j to continue compare next pair of chars. If after the loop, it is still not invalid. That means it is a valid palindrome.

28  Implement strStr()

http://blog.csdn.net/v_july_v/article/details/7041827
KMP algorithm is using the known info from previous comparison to improve the naive string match algorithm.

// KMP  O(N + M) time and O(1) space
class Solution {
public:

  int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
 
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (-1 == j || haystack[i] == needle[j]) { // match
                // ① 如果j == -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
                i++;
                j++;
            } else {
            // ② 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
            //next[j]即为j所对应的next值
                j = next[j];
            }
        }
 
        if (j == m)
            return i - j;
 
        return -1;
    }

void calculateNext(string str,vector<int>& next) {
        if (next.empty())
            return;
   
        int M = next.size();
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < M - 1) {
            // str[j]: post-fix, str[k] prefix
            if (-1 == k || str[k] == str[j]) {
                k++;
                j++;
                next[j] = k;

            } else
                k = next[k];
        }