## 06/20/2017

Research:

• about use of glFinish(), re-test the times
• revise PPT

LeetCode:

• 35. Search Insert Position
• 33 & 81. Search in Rotated Sorted Array I & II

Parallel Computing Study:

• Lesson3
• Exclusive scan & Inclusive scan
• Hillis Steele Scan & Blelloch Scan:
• HSS (Inclusive) step efficiency
• step: log(n)
• work: nlog(n)
• BS (Exclusive) work efficiency
• step: 2 * logn
• work O(n)
• How to choose?
• If have more work than processors: Blelloch Scan
• If have more processors than work: Hillis Steele Scan
• If serial: step: O(n), work: O(n)
• Histogram
• bins
• atomic operation for memory

Guitar:

• practice

## 35. Search Insert Position

Description:

https://leetcode.com/problems/search-insert-position/#/description

Algorithm:

The searching for middle is the classic method.

Searching for the insert index will be the left.

Code:

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (nums.empty()) return 0;
int n = nums.size();
int left = 0, right = n – 1;
int middle;

while (left <= right)
{
middle = (left + right) / 2;
if (nums[middle] == target)
return middle;
else if (nums[middle] < target)
left = middle + 1;
else
right = middle – 1;
}
return left;
}
};

Timing:

O(logn)

## 33 & 81. Search in Rotated Sorted Array I & II

Description:

Algorithm:

|B ————————————— C | A —————————— (B – 1) |

C is the largest number, A is the minimum number.

Squeeze from left and right.

while (left <= right){

1. if ( middle == target ), return
2. else if ( middle in [B,C] region)
1. if target in [B, middle) region => right = middle – 1;
2. else (target in (middle, B]) => left = middle + 1
3. else ( middle in [A, (B-1)] region)
1. if (target in (middle , (B-1)] region) =>left = middle + 1;
2. else (target in [B, middle) region) => right = middle – 1;

}

if left > right => return -1 (cannot find target)

Code:

class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
// nums.erase(unique(nums.begin(), nums.end()), nums.end()); // if II, use this function
int i = 0;
int n = nums.size();
int mid;
int high = n – 1;
while (i <= high) {
mid = (high + i) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[high]) {
if (target > nums[mid] && nums[high] >= target) {
i = mid + 1;
}
else {
high = mid – 1;
}
}
else {
if (target >= nums[i] && nums[mid]>target) {
high = mid – 1;
}
else {
i = mid + 1;
}
}

}
return -1;
}
};

Time Complexity:

O(logn)

## 27. Remove Element

Description:

https://leetcode.com/problems/remove-element/#/description

Boundary:

• nums.size() = 0  return 0
• val > maximum  return nums.size()
• if cannot find return nums.size()

Algorithm:

1. sort
2. go through array and find the beginning index and end index of the val
3. nums.erase()

Code:

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if (nums.size() == 0) return 0;
sort(nums.begin(), nums.end());
if (val > nums[nums.size() – 1]) return nums.size();

int beginner = -1, ender = -1;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == val)
{
beginner = i;
ender = i;
while (i + 1 < nums.size() && nums[i] == nums[i + 1])
{
i++;
ender++;
}
break;
}
}
if (ender > -1)
nums.erase(nums.begin() + beginner, nums.begin() + ender + 1);
return nums.size();
}
};

Timing:

O(n)

## 17. Letter Combinations of a Phone Number

Description:

https://leetcode.com/problems/letter-combinations-of-a-phone-number/#/description

Boundary:

No

Algorithm:

Nothing special.

Code:

class Solution {
public:
vector<string> letterCombinations(string digits) {
string mapping[10] = { ” “,””,”abc”,”def”,”ghi”,”jkl”,”mno”,”pqrs”,”tuv”,”wxyz” };
vector<string> result1, result2;

for (int i = 0; i < digits.size();i++)
{
int idx = (int)(digits[i]) – 48;
if (idx == 1) continue;
for (int j = 0; j < mapping[idx].size(); j++)
{
if (result1.size() > 0)
for (int k = 0; k < result1.size(); k++)
{
string tmp = “”;
tmp += result1[k] + mapping[idx].substr(j, 1);
result2.push_back(tmp);
}
else
result2.push_back(mapping[idx].substr(j, 1));
}

result1 = result2;
result2.clear();
}
return result1;
}
};

## 19. Remove Nth Node From End of List

Description:

https://leetcode.com/problems/remove-nth-node-from-end-of-list/#/description

Boundary:

n > length: delete nothing

Algorithm:

My method:

Count to find length of the list -> get index of the node in front of the deleted node -> delete (beats 66%)

The optimized method:

Two pointers: pre and pos

Code:

My Code:

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int length = 0;
while (node != NULL)
{
length++;
node = node->next;
};
if (n > length)
return NULL;
if (n == length) return head->next;

int idx = length – n;
for (int i = 0; i < idx – 1; i++)
node = node->next;

// ListNode* tmp = node->next;
node->next = node->next->next;
// delete tmp;
}
};

Optimized Code:

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {

while (pre != NULL)
{
if(n < 0)
{
pos = pos -> next;
}
pre = pre -> next;
n–;
};
if (n == 0) return head-> next;
if (n > 0) return NULL;

pos -> next = pos -> next -> next;
}
};

Timing:

O(n)

## 42. Trapping Rain Water

Description:

https://leetcode.com/problems/trapping-rain-water/#/description

Algorithm:

Initially I thought about scan from left to right. and find the containers one by one. However, this doesn’t succeed because It may be trapped in local maximization rather than global maximization.

The correct way is to;

1. scan from left to right and find the left highest for each bar;
2. scan from right to left and find the right highest for each bar;
3. get the water area and add up.

Code:

class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n < 2) return 0;
vector<int> left = vector<int>(n, -1);
vector<int> right = vector<int>(n, -1);
vector<int> thisHeight = vector<int>(n, -1);
left[0] = 0;
right[n – 1] = 0;

int left_rec = 0;
int right_rec = 0;
int total = 0;

for (int i = 1; i < n;i++)
{
if (height[i – 1] >= left_rec)
left_rec = height[i – 1];
left[i] = left_rec;
}
for (int i = n – 2; i >= 0;i–)
{
if (height[i + 1] >= right_rec)
right_rec = height[i + 1];
right[i] = right_rec;
}
for (int i = 0; i < n; i++)
{
int tmp = min(left[i], right[i]) – height[i];
thisHeight[i] = tmp > 0 ? tmp : 0;
total += thisHeight[i];
}
}
};

Timing:

Scan from left to right: O(n)

Scan from right to left: O(n)

Total: 3 * O(n) = O(n)

## 11. Container With Most Water

Description:

https://leetcode.com/problems/container-with-most-water/#/description

Algorithm:

squeeze from left and right. and get the maximun height of left and right.

Code:

class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() – 1;
int result = 0;

while(left < right)
{
int vol = min(height[left], height[right]) * (right – left);
result = vol > result ? vol:result;
if (height[left] < height[right])
left++;
else
right–;
}
return result;
}
};

Timing:

Scan once, O(n)

## 06/15/2017

Research:

LeetCode:

Parallel Computing Study:

• Finish watching video of Lesson3: Fundamental GPU Algorithms
• Reduce
• Reduction Operator a) binary (two arguments)     b) associative
• Scan
• Input:
• input array
• binary associative operator
• identity element [I op a = a]

Guitar:

• practice

Others:

• O(1) independent of size of inputs

Presentation next Monday:

• Prepare the PPT