# [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)

# [Hackerrank] Grid Challenge

## Problem

Given a squared sized grid G of size N in which each cell has a lowercase letter. Denote the character in the ith row and in the jth column as G[i][j].
You can perform one operation as many times as you like: Swap two column adjacent characters in the same row G[i][j] and G[i][j+1] for all valid i,j.
Is it possible to rearrange the grid such that the following condition is true?
G[i]G[i]G[i][N] for 1iN and
G[j]G[j]G[N][j] for 1jN
In other words, is it possible to rearrange the grid such that every row and every column is lexicographically sorted?
Notec1c2, if letter c1 is equal to c2 or is before c2 in the alphabet.
Input Format
The first line begins with T, the number of testcases. In each testcase you will be given N. The following N lines contain N lowercase english alphabet each, describing the grid.
Output Format
Print T lines. On the ith line print YES if it is possible to rearrange the grid in the ith testcase or NO otherwise.
Constraints
1T100
1N100
Gij will be a lower case letter
Sample Input
15ebacdfghijolmkntrpqsxywuv
Sample Output
YES

## Analysis

• Sort each row
• Then check each column to check whether numbers are in increasing order or not