Array Part1

DP

62	Unique Paths

 (1) memo[i][j] = memo[i - 1][j] + memo[i][j - 1];

 (2) Math formula: C(m + n - 2, m - 1)

64	Minimum Path Sum

Create a (m + 1) * (n + 1) memo array, and initialize the first row and column to INT_MAX, except initialize memo[0][1] to 0.
memo[i][j] = grid[i - 1][j - 1] + min(memo[i - 1][j], memo[i][j - 1]);

Two Pointers

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

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.

228	Summary Ranges

O(N) time and O(1) space two pointers solution.
Use two pointer begin and end in the for loop for i from 0 to n - 1.
begin = nums[i];
while (i != (n - 1) && nums[i] == nums[i + 1] - 1) i++
end = nums[i];
res.push_back(to_string(begin());
if (begin != end) res.back() += "->" + to_string(end);

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)

Prefix Sum 

724	Find Pivot Index

O(N) time and O(1) space. Calculate the total sum first. And then check each element  in the array to see whether prefix sum of the left part elements plus the current element value is equal total sum minus left prefix sum. If so return the index. If no early return after loop. meaning no such pivot element.

DFS + Backtracking

For loop each cell in the matrix to try them as the starting position of the word string to do DFS backtracking. 

Base case:

 if (row < 0 || row >= board.size() || col < 0 ||

             col >= board[0].size() || board[row][col] != word[start])

            return false;

  if (start == word.size() - 1)

         return true;

DFS backtracking

   char curChar = board[row][col];

   board[row][col] = '#'; // avoid multiple use for the same cell

   bool res = backtracking(board, word, row + 1, col, start + 1) ||

             backtracking(board, word, row - 1, col, start + 1)  ||

             backtracking(board, word, row, col + 1, start + 1) ||

             backtracking(board, word, row, col - 1, start + 1);

   board[row][col] = curChar; // backtracking

// O(4^(M*N)) time, O(M*N) space

Binary Search

74	Search a 2D Matrix

left = 0, right = m * n -1, while left <= right, if matrix[i][j] == target return true, else if target >  matrix[i][j]    right = mid - 1, else left = mid + 1 (where i = mid / n, j = mid % n). Return false in the end. O(lg(M*N)) time and O(1) space

You can also do saddle search from top right, i.e: row = 0, col = n - 1, if matrix[row][col] == target return true, if target > matrix[row][col] col--, else if target < matrix[row][col] row++, return false in the end. But O(M + N) time and O(1) space.

35	Search Insert Position

O(lgN) binary search, while left <= right, if nums[mid] == target return mid, else if target > nums[mid],   right = mid - 1, else left = mid + 1. Return left in the end.

Math

66

Plus One

Initialize carry to 1, and loop from the last element and add the carry value to it and get the sum. Update the digit with sum % 10, and update carry with sum / 10. After the loop, if carry is not equal to zero, then insert the carry value to the beginning of the result array.
O(N) time and O(1) space.

268	Missing Number

       (1) Calculate the total sum of the given array (either for loop or use STL accumulate interface)

       (2) the missing number = N * (N + 1) / 2 - sum. ( Where N is the size of input array)

118	Pascal's Triangle

First and last element of each row is always 1

For others: pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];

O(N^2) time and O(N^2) space.

119	Pascal's Triangle II

Similar to 118, but we don't have to allocate O(N*K) space. Allocate O(K) space on the fly is enough. Use last and current to keep the last row and the current row while generating.

628	Maximum Product of Three Numbers

The max product is always either the product of the right most three elements or the two left most elements multiply the right most element.

 

Sliding Window

674	Longest Continuous Increasing Subsequence

Keep move the right side of the window to the right by one each time in the loop, and when encounter reversing order element ( nums[i]  >= nums[i + 1]) update the left side of window.  Get the maximum of all the (right - left + 1) which will be the longest continuous increasing subsequence length.

Hash Map

1

Two Sum

Use hash map to save the mapping between the element and its index.  If see target - num[i] exist in the hash map, put both target - num[i] and num[i] indices into the result and return. If after loop no early return. That means no such pair exist.  

O(N) time and O(N) space.

169	Majority Element

Use hash map to save each element and its frequency, once we encounter one element has frequency 

more than n/2, return it. Otherwise, there is no such number.

167	Two Sum II - Input array is sorted

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.

217	Contains Duplicate

Use hash set to save the elements encountered so far. And check whether the current_num_val is already in the hash set, if so  return true. If in the end after loop not returned, then return false.

697	Degree of an Array

Use a hash Map to save every element and its frequency, remove those that have non max-frequency elements later. And for each remaining element, get the minimum length between their last  occurrence and first occurrence

532	K-diff Pairs in an Array

Define a hash map and a hash set to save the frequency of each element and the starters for these element pair (m, m + k). Loop over each element x in the array, if x - k is in the frequency map already, put x - k in the set. Similarly, if x + k is in the frequency map already, put x in the set.
Also increase the element x frequency by 1. In the end, the starter set size will have the number of k diff Paris we wanted.

TREE

105	Construct Binary Tree from Preorder and Inorder Traversal

     (a) Find index of root in the inorder list.

        TreeNode* root = new TreeNode(preorder[preBegin]);

        (b) root->left = constructTree(preorder, preBegin + 1,  preBegin + 1 + (index - 1 - inBegin),

                                   inorder, inBegin, index - 1);

             root->right = constructTree(preorder, preEnd - (inEnd - index - 1),  preEnd,

                                   inorder, index + 1, inEnd);

106	Construct Binary Tree from Inorder and Postorder Traversal

    (a) Find index of root in the inorder list.

       TreeNode* root = new TreeNode(inorder[index]);

        (b) root->left = constructTree(inorder, inBegin, index - 1,

                                   postorder, postBegin, postBegin + (index - 1 - inBegin));

        root->right = constructTree(inorder, index + 1, inEnd,

                                   postorder, postEnd - 1 - (inEnd - index - 1), postEnd - 1);

Other

561	Array Partition I

Idea:
In short, the sum of all number is fixed, to maximize the sum of smaller group, you want to minimize the diff of the sum of 2 groups. And the best way to do that is to pair the numbers that are next to each other in sorted order.
Implementation:
Sort the array in increasing order and sum up every two pairs from small to large.
O(NlgN) time and O(1) space

566	Reshape the Matrix

The indices mapping is from (i, j) to ((i * col + j) / c, (i * col + j) % c)
Time O(r*c) and Space O(r*c)

485	Max Consecutive Ones

Loop over each element if the current number is 1 increase the counter, otherwise reset the counter to zero. Get the maximum of all the counter size calculated.

695	Max Area of Island

We want to know the area of each connected shape in the grid, then take the maximum of these.  If we are on a land square and explore every square connected to it 4-directionally (and recursively squares connected to those squares, and so on), then the total number of squares explored will be the area of that connected shape.

To ensure we don't count squares in a shape more than once, We could use seen flag to keep track of squares we haven't visited before if the original grid cannot be changed. But if it can be changed, we could simple do this by setting visited grid[r][c] = 0 instead. It will also prevent us from counting the same shape more than once.

  Base Cases:

   if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0)
            return 0;

   Recursion Formula:
   grid[r][c] = 0;
    return dfs(grid, r - 1, c) + dfs(grid, r +  1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1) + 1;

283	Move Zeroes

move non zero elements forward and keep storeIndex increased. After that fill the remaining with zero.

717	1-bit and 2-bit Characters

For every element in the array, check from beginning, if the current element is 0, goto check the next one, else go to check the one after next. If eventually, we arrive at element array length minus 1, return true if that element is 0, return false if that element is 1. If we didn't arrive at element array length minus 1, return false.

122	Best Time to Buy and Sell Stock II

Greedy.

For loop each price and calculate the diff with its previous price, if positive, add it to the total revenue.

661	Image Smoother

Define a vector<pair<int,int>> to save the 9 offset relative to the current position in the matrix.

Double for loop each element inside the matrix, and in the third level nested for loop, check whether current indices plus offset is inside  the board, if so increase the counter and total sum. When exit the most inside level loop, the smoothed value for current position will be total sum / counter.

747	Largest Number At Least Twice of Others

Just loop once is enough, keep record of the largest value (update whenever encounter one value larger than current largest value) and the second largest value (update whenever encounter one value larger than current second largest value, i.e: greater than current second largest and smaller than current largest). When exit check whether second * 2 <= first (note: don't check  first / second >= 2, since second could be zero, the rule is if you could use multiply don't use division,  which is slower)

605	Can Place Flowers

The solution is very simple. We can find out the extra maximum number of flowers, $count$, that can be planted for the given $flowerbed$ arrangement. To do so, we can traverse over all the elements of the $flowerbed$ and find out those elements which are 0(implying an empty position). For every such element, we check if its both adjacent positions are also empty. If so, we can plant a flower at the current position without violating the no-adjacent-flowers-rule. For the first and last elements, we need not check the previous and the next adjacent positions respectively.

If the $count$ obtained is greater than or equal to $n$, the required number of flowers to be planted, we can plant $n$ flowers in the empty spaces, otherwise not.

581	Shortest Unsorted Continuous Subarray

Sort the array and compare the sorted array with the original array. Find the first and last different element indices. Their difference plus one with be the shortest unsorted continuous subarray. If no such indices exist, return 0.

189	Rotate Array

Solution 1: Remove the last element from the array end and insert that value to the beginning of the array. Repeat this operation k times.

Solution 2: (a) Reverse the whole n elements (b) reverse first k elements (c) reverse the last n - k elements.

287	Find the Duplicate Number

(a) Sort the array and check whether there is consecutive numbers that are equal, if so return it.

(b) Use hash map, when see number already in the map, return it.

729	My Calendar I

Use vector<pair<int,int> > booked to keep record of these events have been booked. If we want to book a new event, we have to iterate each event in the booked list to see whether they overlap, only book the new event if it doesn't overlap with any existing one (note we can sort the booked list and try to do binary search to reduce time complexity, or use customized set with comparator)
O(N^2) time and O(N) space.

775	Global and Local Inversions

All local inversions are global inversions.
If the number of global inversions is equal to the number of local inversions,
it means that all global inversions in permutations are local inversions.
It also means that we can not find A[i] > A[j] with i+2<=j.
In other words, max(A[i]) < A[i+2]

153	Find Minimum in Rotated Sorted Array

Binary Search, but  compare nums[mid] with nums[high]

while (low < high)

if nums[mid] > nums[high]

      low = mid + 1;

else

high = mid;

return nums[low]

905	Sort Array By Parity

(1) One easy way is using the sort function provided by any languages. In C++, customize the key to be x % 2, i.e: a % 2 < b % 2. Takes O(NlgN) time and O(1) space.

(2) Can use the simplified version DNF algorithm
 Algorithm:
 let odd = 0
 let even = N - 1
while odd < even
   while num[odd] is odd
        odd++
  while num[even] is even
       even--
  swap nums[odd++] with nums[even++]