# [Leetcode C++] Search Insert Position

## Problem

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
`[1,3,5,6]`, 5 → 2
`[1,3,5,6]`, 2 → 1
`[1,3,5,6]`, 7 → 4
`[1,3,5,6]`, 0 → 0

## Analysis

We can use naive search with time O(n), or binary search with time O(log n)

## Solution

Naive solution O(n)

```class Solution {
public:
int searchInsert(vector<int>& nums, int target) {

for(int i =0; i<nums.size(); i++){
if(nums[i] >= target)
return i;
}

return nums.size();
}
};
```

Binary search O(log n)

```class Solution {
public:
int searchInsert(vector<int>& nums, int target) {

int low = 0;
int high = nums.size()-1;

//binary search
while(low <= high){
int mid = (low+high)/2;
if(nums[mid] < target) low = mid+1;
else if(nums[mid] > target)
high = mid-1;
else return mid;
}

return low;

}
};
```

# [Leetcode C++] Implement strStr

## Problem

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

## Analysis

Brute force. Assume haystack has length n, and the needle has length m. We have
Time complexity: O(m*n)

## Solution

```class Solution {
public:
int strStr(string haystack, string needle) {

if(needle.size() == 0) return 0;

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

if(haystack.size()-i < needle.size()) return -1;
int j =0;
for(; j<needle.size(); j++){
if(haystack[i+j]!=needle[j]){
break;
}
}

//found
if(j==needle.size()){
return i;
}
}

return -1;
}
};
```

# [Leetcode C++] Count and Say

## Problem

The count-and-say sequence is the sequence of integers with the first five terms as following:

```1.     1
2.     11
3.     21
4.     1211
5.     111221
```

`1` is read off as `"one 1"` or `11`.
`11` is read off as `"two 1s"` or `21`.
`21` is read off as `"one 2`, then `one 1"` or `1211`.

Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

```Input: 1
Output: "1"
```

Example 2:

```Input: 4
Output: "1211"
```

## Analysis

This problem is about string operation

## Solution

```class Solution {
public:
string countAndSay(int n) {
string num = "1";

for(int i=1; i<n; i++){
num = helper(num);
}

return num;
}

//helper function for reading a number
string helper(string num){

stringstream nextStr;
char last = num;
int count = 1;
for(int i=1; i<num.size(); i++){
if(num[i] == last){
count++;
}else{
nextStr<<count<<last;
last = num[i];
count = 1;
}
}
nextStr<<count<<last;
return nextStr.str();
}
};
```

# [Leetcode c++] Remove Element

## Problem

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

### Example: Given input array nums = `[3,2,2,3]`, val = `3`

Your function should return length = 2, with the first two elements of nums being 2.

## Solution

```class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int l = 0;
int r = nums.size()-1;
int count = 0;

while(l <= r){
//replace the left repeated value with rightest value
if(nums[l] == val){
nums[l] = nums[r];
r--;
}else{
l++;
count++;
}
}

return count;
}
};
```

## Analysis

We scan the array from leftside, and replace every target value with the value from the rightside. In specific
– for nums[left] == val, we have nums[left] = nums[right], right–
– for nums[left] != val, we have left++

Time complexity: O(n), where n in the length of the array

# [Leetcode c++] Merge Two Sorted Lists

## Problem

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

## Solution

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *l3 = new ListNode(-1);
ListNode *t3 = l3;

while(l1 && l2){
if(l1->val <= l2->val){
t3->next = l1;
l1 = l1->next;
}else{
t3->next = l2;
l2 = l2->next;
}
t3 = t3->next;
}

t3->next = l1? l1 : l2;
//ListNode *tmp = l3;
l3 = l3->next;
//delete tmp;
return l3;
}
};
```

## Analysis

Time complexity: O(n) where n is the length of the linked lists
Space complexity: O(n)

# [Leetcode c++] Valid Parentheses

## Problem:

Given a string containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.

The brackets must close in the correct order, `"()"` and `"()[]{}"` are all valid but `"(]"` and `"([)]"` are not.

## Solution:

```class Solution {
public:
bool isValid(string s) {
stack&lt;char&gt; stk;
for(int i=0; i&lt;s.size(); i++){
if(isLeft(s[i]))
stk.push(s[i]);
else{
if(stk.empty() || !isClose(stk.top(), s[i])){
return false;
}
stk.pop();
}
}
return stk.empty();
}

bool isLeft(char c){
if(c=='(' || c=='{' || c=='[')
return true;
return false;
}

bool isClose(char l, char r){
if(l=='(' &amp;&amp; r ==')') return true;
else if(l=='{' &amp;&amp; r=='}') return true;
else if(l=='[' &amp;&amp; r==']') return true;
return false;
}
};
```

## Analysis:

Time complexity: O(n)
Space complexity: O(n)

# [Leetcode C++] 3Sum Closest

## Problem

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

```    For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).```

## Solution

```class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int minDiff = INT_MAX;
if(nums.size()<3) return minDiff;
sort(nums.begin(), nums.end());
for(int i=0; i<nums.size()-2; i++){
int left = i+1;
int right = nums.size()-1;
while(left < right){
int currDiff = nums[i] + nums[left] + nums[right] - target;

//update diff
if(abs(minDiff) > abs(currDiff))
minDiff = currDiff;

//special case
if(currDiff == 0) break;
else if (currDiff < 0) left++;
else right--;
}
}
return target + minDiff;
}
};
```

## Analysis

This problem is similar to 3Sum problem http://mytechroad.com/leetcode-c-3sum/

Time complexity: O(n^2)

# [Leetcode C++] 3Sum

## Problem

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

```For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
```

## Solution

```class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
return findThreeSum(nums, 0);
}

vector<vector<int>> findThreeSum(vector<int>& nums, int target){
vector<vector<int>> result;
if(nums.size()<3) return result;

sort(nums.begin(), nums.end());
for(int i=0; i<nums.size()-2; i++){
//skip duplicate
if(i!=0 && nums[i-1] == nums[i]) continue;

int left = i+1;
int right = nums.size()-1;
while(left < right){
int remain = target - nums[i];
int sum = nums[left] + nums[right];
if(sum < remain) left++; else if(sum > remain) right--;
else {
vector<int> curr;
curr.push_back(nums[i]);
curr.push_back(nums[left]);
curr.push_back(nums[right]);
result.push_back(curr);
left++;
right--;
//skip duplicate
while(nums[left] == nums[left-1]) left++;
while(nums[right] == nums[right+1]) right--;
}
}
}
return result;
}
};
```

## Analysis

Time complexity: O(n^2) where n is the size of the array

# [Leetcode C++] Longest Common Prefix

## Problem:

Write a function to find the longest common prefix string amongst an array of strings.

## Solution:

```class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string commPrefix;
//Case 1: strs is null
if(strs.empty()) return commPrefix;

for(int i =0; i<strs.size(); i++){
for(int j=1; j<strs.size(); j++){
//Case 2/3: length issue, or not equal
if(strs[j].size()<i+1 || strs[j][i]!=strs[i])
return commPrefix;
}
commPrefix.push_back(strs[i]);
}
return commPrefix;
}
};

```

## Analysis:

Assume:
m: the number of strings
n: the average length of each string

Then the time complexity is: O(m*n)
The extra space complexity is: O(n)