Array Part2

Two pointers

977
We can use two pointers to read the positive and negative parts of the array - one pointer j in the positive direction, and another i in the negative direction.
Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique.
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.

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]

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.


229
// 摩尔投票法 Moore Voting
(1) First pass, find the two candidate majority number.
(2) Second pass, recounter that voting times
(3) Check both voting times if greater than n / 3, put in the result array

2*N time and O(1) space.




Greedy


55
Jump Game    
Calculate the left most reachable index from right to left. Initially, the left most reachable index is n - 1, if find another index that plus its value is greater or equal than the current left most reachable index, update it.  In the end, check whether the left most reachable index is 0.
   
 int leftMostReachableIdx = n - 1;
        for (int i = n - 2; i >= 0; i--)
            if (i + nums[i] >= leftMostReachableIdx)
                leftMostReachableIdx = i;

        return leftMostReachableIdx == 0;


Prefix Sum / product


238
 O(N) time and no extra space
 Initialize the result array to all 1's
Use fromBegin and fromEnd to save the prefix/postfix product until element i
Update each res[i] with res[i] * prefixProduct and res[n - 1 -i] with res[n - 1 - i] * postfixProduct in one loop.


            visited[i] = true;


560
Use prefixSum to save the total sum until current element. And define a unordered_map to save all the prefixSum and its frequency. Remember to initialize map[0] = 1 (to calculate these sub-array starting from index 0). Add map[prefixSum - k] to the total count while iterating all the element on the fly. And update the map by map[prefixSum]++.


DNF (Dutch National Flag) problem

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], and increase j and 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.

75
Sort Colors    
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
922
In side a loop, use two pointers i = 0, j = N - 1, 
while i < N and j >= 0 repeat the following stetps
   find the first even number that is on a odd position, let i point to it
   find the first odd number that is on a even position, let j point to it
   swap these two numbers,


Priority Queue

621
The idea is to create a priority queue. First use hash map  to count each chars frequency and put the frequency inside the priority queue so that the most frequent number is in front of the queue. Since each
cycle we could schedule at most n + 1 task. We always try round robin between the most popular tasks at any time.  Get a task from each category task and put it in a temp array. Then iterate the array, decrease the frequency by 1, if still >= 0, then push it back to the priority queue. If after iteration, the queue is not empty, that means the full cycle is filled or we have to insert some idle slot. if the queue is empty, then we add count to the total time.


Backtracking

39
(1) Sort the array
(2) For every element from begin (starting from 0 to array.size() - 1, try backtracking, get combination with the current element, decrease target by current element, recursively call the backtracking helper function still with the current position to allow duplicated value. After coming back from the recursion, try without the current element. 

40

(1) Sort the array
(2) For every element from begin (starting from 0 to array.size() - 1, try backtracking, get combination with the current element, decrease target by current element, recursively call the backtracking helper function still with the current position plus one to avoid duplicated value. After coming back from the recursion, try without the current element. 

DP:


120
Triangle    
Base case: minVal[j] = triangle[row - 1][j] for j = 0,1, ... row - 1
Transition formula: minVal[j] = triangle[i][j] + min(minVal[j], minVal[j + 1])
the min path value will be  minVal[0] finally
O(N) space and O(N^2) time

152
// DP O(N), greedy O(N) time and O(1) space. Base on the fact that maxProduct[i] could only be max({nums[i], maxProduct[i - 1] * nums[i], minProduct[i - 1] * nums[i]})

  vector<vector<int> > dp(sizeA + 1, vector<int>(sizeB + 1, 0));
 if  A[i] == B[j]
     dp[i][j] = dp[i + 1][j + 1] + 1;
     res = max(res, dp[i][j]);

O(N) time and O(N) space DP, use an array to save the minimum price encountered so far in the second loop, calculate the max diff between prices array and the minimum price array.

A further improved version, would be do this in one loop. Use a variable to save the minPrice encountered so far and get the maximum diff between each price and the the minPrice. O(N) time and O(1) space.


714
       int cash = 0, hold = -price[0]
       for (int i = 0; i < prices.size(); i++)
             cash = max(cash, hold + prices[i] - fee); // Max possible profit without stock at day i end
             hold = max(hold, hold - prices[i]); // Max possible profit with stock at day i end

     return cash


55
Jump Game    
 BOTTOM-UP DP O(N^2) time and O(N) space
Can save these trial errors, do not make the same mistake again.
Must calcuate this backward from right to left.
Top-down to bottom-up conversion is done by eliminating recursion. In practice, this achieves better performance as we no longer have the method stack overhead and might even benefit from some caching. More importantly, this step opens up possibilities for future optimization. The recursion is usually eliminated by trying to reverse the order of the steps from the top-down approach.

Base case:
memo[n - 1] = GOOD;

Transition Formula:
         for  pos : [startPos + 1  farthestPos]
                if (memo[pos] == GOOD)
                    memo[startPos] = GOOD;

return memo[0] == GOOD


53
O(N) time and space DP.
Base case: dp[0] = numes[0], maxSlice = nums[0];
Transition Formula:
dp[i+1] = max(dp[i - 1] + nums[i], nums[i]);
maxSlice = max(dp[i], maxSlice);       i = 1, 2, ... n - 1


769
Use m to keep maximum value encountered so far. If m is equal to the current index increase the result by 1. O(N) time and O(1) space.

Binary Search

162
  while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
     
        return l;

Sort the array
For every pair (i,j) i=0,1, ... n - 2, j = i+1. Binary Search value x = nums[i] + nums[j] to find the first index that is greater or equal to x. all The elements  between j + 1 and k - 1 i.e: (k-1) - (j+1) + 1= k -j - 1 can construct triangle.

792
Indexing + Binary Search, O(S) + O(W * L * log(S)), space O(S)
Map S to  {char : [indices]}
"acbca" ==> pos = {
'a' : [0, 4]
'b' : [2]
'c' : [1, 3]
prev = -1
index = lower_bound(pos[c], prev)
if (index == len(pos[c])) return false
prev = pos[c][index];

34
Use equal_range(nums.begin(), nums.end(), target) to find the the upper and lower bounds.
If upper bound and lower bound are both NULL, then return {-1, -1}. Otherwise, return
{bounds.first - nums.begin(), bounds.second - nums.begin() - 1}

You can also implement your own version of equal_range using lower_bound and upper_bound.

33
Solution 1:
O(lgN) time and O(1) space, two passes
Use helper function findPivot() to binary search and find the minimum value index, which is the pivot index. ( i.e: 153 Find Minimum in Rotated Sorted Array). And then  do rotated binary search (i.e. realMid = (mid + pivot) % n).

 NOTE in step 2 binary search exit condition less than or equal, but in step 1,  finding a pivot index, strict less than is sufficient.


Solution 2:
O(lgN) time and O(1) space, One pass

A[mid] =  target, return mid，otherwise
(1) A[mid] < A[end]: A[mid+1 : end] sorted
A[mid] < target <= A[end]  right half，otherwise left half

(2) A[mid] > A[end] : A[start : mid-1] sorted
A[start] <= target < A[mid]  left half, otherwise right half

81
 Same two 33 Search in Rotated Sorted Array, solution 2. But add two more lines two skip duplicate elements. O(lgN) average time and O(1) space, worst case O(N) time (all duplicate numbers)

      while (l < r && nums[l] == nums[l + 1])   l++; // skip duplicates from the left
       while (r > l && nums[r] == nums[r - 1]) r--; // skip duplicates from the right


Backtracking

216
DFS + backtracking.  O(2^n)
Use a DFS helper function to pass over the result array and the candidate array and the current number with starting value 1, the total target and the total split parts k. 
Exit condition:
when (0 == k && 0 == target) push the candidate into the result.
when (k <= 0 || n <= 0 || cur > 9) early exit
Otherwise:
DFS try to split the target with/without current value:
without current value:
DFS(res, candidate, n, k, cur +  1);
backtracking with current value
DFS(res, candidate, n - cur, k - 1, cur +1)

In the end, return res.


Sliding window

Calculate the total  sum of the first window (size k from left side to right side). And initialize the largest average value with first sum / k. Then move the window right by 1 each time and add the new value entered the window and subtract the element leaving the window. Keep doing this until the last window. Get the maximum sum / k among them.

219
Same idea with 643 Maximum Average Subarray I . Except we need to use hash set to save all the elements in the first window. While move the window forward, erase the first element from the old window, and check whether the current element exist in the remaining window  elements. If there is duplicate, return true. Otherwise, insert the new element into the window. If in the end no early exit, there is not duplicate.

713
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.

Hash Map/Set

414
For loop each element in the array and put it in a set (ordered_set). If the size of the result set is greater than 3, remove the first element from it ( the res.begin(), i.e: the smallest). When exit, if the
result set size is greater or equal than 3, return the first element ( the third largest number), otherwise return the last element (rbegin()), the largest element.


380
Data Structure
     unordered_map<int, int> mp
+
     vector<int> nums


insert:
     emplace_back(val)
     mp[val] = nums.size() - 1


Delete:

        idea: copy the last to overwrite the one to be deleted and update the map accordingly.
 
        int last = nums.back();
        mp[last] = mp[val];
        nums[mp[val]] = last;
        nums.pop_back();
        mp.erase(val);

getRandom():
        return nums[rand() % nums.size()];


next_permutation

 Find the first decreasing number backward
 Find the first number that is slightly larger than nums[i] 
 Swap nums[i] and nums[j]     
 reverse nums[i + 1] to end


Matrix Layer traversal

48
 Array layer traversal O(M*N) time and O(1) extra space
for   layer = 0,1,2 ... n /2
         int first = layer;
         int last = layer + n - 1;
         for     i = first, first + 1, ... last
                int offset = i - first;
                int top = matrix[first][i];
                matrix[first][i] = matrix[last - offset][first]; // left, bottom --> left, top
                matrix[last - offset][first] =  matrix[last][last - offset]; // right, bottom --> left, bottom
                matrix[last][last - offset] = matrix[i][last];  // right, top --> right, bottom
                matrix[i][last] = top; // left, top --> right, top

Here

59
Initialize rowStart and colStart with 0, and rowEnd, colEnd with n - 1. While rowStart <= rowEnd and colStart <= colEnd, for each layer, generate the top row increase rowStart, generate right column decrease colEnd, generate bottom row decrease rowEnd, and then generate left column increase rowStart.


54
The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer layer, and so on. Similar to 59 Spiral Matrix II. Except we need to check whether the last col is equal to the first col and last row is equal to the first row when adding it. O(M*N) time and O(1) space.

Others

766
Skip the first column and the first row.  And for the remaining elements check whether matrix[i][j] == matrix[i-1][j-1], if not return false. Otherwise if all elements satisfy matrix[i][j] == matrix[i-1][j-1] return true.

448
O(N) time and no extra space. Change all the positive sign of every number at the position (index)
of abs(number) - 1 to negative and collect the index + 1 which has value nums[index] > 0 in the end


442
Similar to 448. O(N) time and no extra space. Change all the positive sign of every number at the position (index) of abs(number) - 1 to negative and collect the index + 1 which has value nums[index] < 0 on the fly.


88
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 ...


665
(1) Naive O(N^2) time and O(N) space brute force, copy the original array and try to remove from every position and check whether the remaining is in non-decreasing order. If so return true, otherwise return false.

(2) Better O(N) time and O(1) space. Loop each element and find the first reverse point. i.e: nums[j] > nums[j + 1].   Try remove nums[j] and nums[j+1] from the array (pseudo remove, save the nums[j] to a temp and overwrite nums[j] with nums[j+1] first. and then later overwrite both with temp). If after remove either of them the remaining is_sorted, return true, otherwise return false.


495
For each time Series element in the array, if its poison  duration doesn't overlap with previous one. Add the whole duration to the total poison time. If it overlaps with the previous one, add the non-overlap time duration to the total time, which is duration - overlap time = duration -  (end time of last poison duration - current duration start time)

667
if you have n number, the maximum k can be n - 1;
if n is 9, max k is 8.
This can be done by picking numbers interleavingly from head and tail,
// start from i = 1, j = n;
// i++, j--, i++, j--, i++, j--

1   2   3   4   5
  9   8   7   6
out: 1 9 2 8 3 7 6 4 5
dif:  8 7 6 5 4 3 2 1
Above is a case where k is exactly n - 1
When k is less than that, simply lay out the rest (i, j) in incremental
order(all diff is 1). Say if k is 5:
     i++ j-- i++ j--  i++ i++ i++ ...
out: 1   9   2   8    3   4   5   6   7
dif:   8   7   6   5    1   1   1   1


78
Iteratively generate the super set in a double loop. O(2^N)
like for [1,2,3]
step 1: [], [1]
step 2: [], [1], [2], [1,2]
step 3:  [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]

565
Brute force, O(N^2), O(1) space. For loop each element, keep calculating nums[nums[i]] and increase the count. Get the maximum of all the count value.
O(N) time and O(N) space improved on brute force. Use visited flag array to record these numbers that have visited, to avoid repeated calculation.


63
Similar to 62 Unique Paths. Except we need to guard the transition formula with condition:
   if (!obstacleGrid[i][j])
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1];

Also for base cases, the first row and column is not necessarily always 1. It is zero if there is obstacle (and all the elements following zero is also zero  in the first row and column)



795
 There are 3 buckets which numbers in can be placed into:
less than L
less than or equal to R
greater than R
Bucket 1 is a subset of Bucket 2. Return the ongoing count of bucket 2 numbers minus the ongoing count of bucket 1 numbers. Completely ignore bucket 3. The ongoing count of bucket 1 and 2 is reset back to 0 when a number no longer meets the ongoing count criteria ( “less than L” for bucket 1 and “less than or equal to R” for bucket 2 ).




731
Keep a vector<pair<int,int>> for all calendar events, and vector<pair<int,int>> for double booked overlapping part events with start = max(start, cal.first), end = min(end, cal.second).
For checking overlapping. if s1 >= e2 || s2 >= e1 there is no overlapping, so there is conflicts when
(!(s1 >= e2 || s2 >= e1)), i.e: (s1 < e2 && s2 < e1)


289
Game of Life    
The key here is how to do this in-place. You can add 2 to the current status if you know the next status is going to be live, you could still use board[i][j] & 1 to get the current status while counting. After scanning the array and updating the status. We just need one extra shift right 1 bit all elements, then we have all the latest cell status.


56
Sort the arry first. Then in the loop, keep a  maxEnd for starting from the current group, if the next interval start is less or equal to maxEnd then it is mergeable with the current group.  After find all the mergeable interval for current group, the merged interval will be Interval(intervals[first].start, maxEnd).


The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer layer, and so on.
832
Simple, just loop twice the array one time reverse each row (i.e flip each row) and then loop the array again to invert each element.
If you want to do this in one pass. You can easily combine the two loops as well.

1089
Loop every element in the array from i = 0 to len(arr) - 1
if arr[i] == 0, insert 0 at the index i, increase i by 1
increase 1 always unconditionally

1051
(1) Sort the array and save the result to a new array called sortedHeight
(2) For loop each element from begin to end and check if the sorted array and the original array value match, if match skip, if not add 1 to the total result
(3) return the result after loop.

Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

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      ...
Read more