# [Leetcode C++] Roman to Integer

## Problem

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

## Analysis

We traverse the string and add up each char by its value.
We need to handle a special case such as: IV, in which we have V-I = 4
In this case, we need to have I+V – 2*I = 4

## Solution

```class Solution {
public:
int romanToInt(string s) {
if(s.empty()) return 0;
unordered_map<char, int> map({{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},  {'C', 100}, {'D', 500}, {'M', 1000}});
int val = 0;
for(int i=0; i<s.size(); i++){
val += map[s[i]];

//Handle case like: IV = 4, as in the traverse we have added I(1) and V(5), we need to substract twice of I
if(i>0 && map[s[i]] > map[s[i-1]])
val -= 2*map[s[i-1]];
}
return val;
}
};
```

# [Leetcode C++] Integer to Roman

## Problem

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

## Analysis

Time complexity: O(13*3) = O(1)

## Solution

```// I: 1
// IV: 4
// V: 5
// IX: 9
// X: 10
// XL: 40
// L: 50
// XC: 90
// C: 100
// CD: 400
// D: 500
// CM: 900
// M: 1000

class Solution {
public:
string intToRoman(int num) {
// build the dictionary to value maps
string dict = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int val = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string ret;
int remain = num;

// build the roman results from interger
for(int i=0; i<13; i++){ if(remain >= val[i]){
int count = remain/val[i];
remain = remain%val[i];

for(int j=0; j<count; j++){
ret.append(dict[i]);
}
}

if(remain == 0) break;
}

return ret;
}
};
```

# [Leetcode C++] Permutations II

## Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
`[1,1,2]` have the following unique permutations:

```[
[1,1,2],
[1,2,1],
[2,1,1]
]
```

## Analysis

This problem is similar to http://mytechroad.com/leetcode-c-permutations/
The only difference is that the number may be repeated, thus we need to deal with the special case when
– nums[i-1] is used, and nums[i]==num[i-1]

Time complexity: O(n!), the same analysis with previous problem

## Solution

```class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> allPer;
if(nums.size()==0) return allPer;
vector<int> currPer;
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
findAllPer(nums, allPer, currPer, used);
return allPer;

}

void findAllPer(vector<int>& nums, vector<vector<int>>& allPer, vector<int>& currPer, vector<bool>& used){
if(currPer.size() == nums.size()){
allPer.push_back(currPer);
return;
}

for(int i=0; i<nums.size(); i++){
//Case 1: if current number is used, skip
if(used[i]) continue;
//Case 2: if current number is not used, but previous number is equal to current number, skip
if(i>0 && nums[i]==nums[i-1] && used[i-1]) continue;

//Otherwise: DFS to find all permutation
used[i] = true;
currPer.push_back(nums[i]);
findAllPer(nums, allPer, currPer, used);
currPer.pop_back();
used[i] = false;
}
}
};
```

# [Leetcode C++] Next Permutation

## Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
`1,2,3` → `1,3,2`
`3,2,1` → `1,2,3`
`1,1,5` → `1,5,1`

## Analysis

Check http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html
In specific, we have the following steps
Step 1: scan from right to left, find the first index that violates the non-decreasing property, denote as vioIdx
Step 2: scan from right to left, find the first index of number that is smaller than vioIdx, and swap the values
Step 3: reverse the array on the right side of the value

## Solution

```class Solution {
public:
void nextPermutation(vector<int>& nums) {
//Step 1: from right to left, find the first one that violates the non-decreasing trend
int vioIdx = nums.size()-1;
while(vioIdx > 0 && nums[vioIdx] <= nums[vioIdx-1]){
vioIdx--;
}

if(vioIdx > 0){
vioIdx--;
//Step 2: from right to left, find the first one that is larger than nums[vioIdx]
int rightIdx = nums.size()-1;
while(rightIdx > 0 && nums[rightIdx] <= nums[vioIdx]){
rightIdx--;
}

int swap = nums[vioIdx];
nums[vioIdx] = nums[rightIdx];
nums[rightIdx] = swap;

//Step 3: preparation, reverse the array from the righthand side of vioidx
vioIdx++;
}

//Step 3: reverse
int end = nums.size()-1;
while(end>vioIdx){
int swap = nums[vioIdx];
nums[vioIdx] = nums[end];
nums[end] = swap;
vioIdx++;
end--;
}
}
};
```

# [Leetcode C++] Permutations

## Problem

Given a collection of distinct numbers, return all possible permutations.

For example,
`[1,2,3]` have the following permutations:

```[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
```

## Analysis

We can use DFS approach, we maintain a temporary vector for current permutation
– then we traverse the array to add unused nums to the vector
– that means we need a vector to keep track which num has been used

Time complexity:
– T(n) = n*T(n-1) + 1, thus it is O(n!)
– reference: https://stackoverflow.com/questions/41627749/time-complexity-of-permutation-function

## Solution

```class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> allPer;
vector<int> currPer;
//keep track of whether nums[i] has been used
vector<bool> used(nums.size(), false);
getAllPermute(nums, allPer, currPer, used);
return allPer;
}

//recursively find all permutation
void getAllPermute(vector<int>& nums, vector<vector<int>>& allPer, vector<int>& currPer, vector<bool>& used){
if(currPer.size()==nums.size()){
allPer.push_back(currPer);
return;
}

for(int i=0; i<nums.size(); i++){
//if nums[i] has already been used, skip
if(used[i]) continue;

//otherwise, add to the permutation, and recursively build the array
currPer.push_back(nums[i]);
used[i] = true;
getAllPermute(nums, allPer, currPer, used);
currPer.pop_back();
used[i] = false;
}
}
};
```

# [Leetcode C++] Merge k Sorted Lists

## Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

## Analysis

We can recursively merge two lists into one list

Let k denote the number of lists
Let n denote the average length of each list
Time complexity: T(k) = 2T(k/2) + O(nk), thus we have O(nk*log k)
Space complexity:

## Solution

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return NULL;
if(lists.size() == 1) return lists;

//merge each two lists into one
vector<ListNode*> newLists;
int n = lists.size();
for(int i=0; i<n/2; i++){
ListNode* currList = helper(lists[i], lists[n-1-i]);
newLists.push_back(currList);
}
if(n%2 != 0){
newLists.push_back(lists[n/2]);
}

//recursively merge all the lists
return mergeKLists(newLists);
}

//merge two lists
ListNode* helper(ListNode* l1, ListNode* l2){
while(l1 && l2){
if(l1->val <= l2->val){
l->next = l1;
l1 = l1->next;
}else{
l->next = l2;
l2 = l2->next;
}
l = l->next;
}
l->next = l1? l1 : l2;
}
};
```

# [Leetcode C++] Combination Sum

## Problem

Given a set of candidate numbers (C(without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set `[2, 3, 6, 7]` and target `7`,
A solution set is:

```[
,
[2, 2, 3]
]```

## Analysis

We can use DFS to recursive build the solution, i.e.,
let sol denote current solution,
let allSol denote all solutions,
let remain denote current remaining value to reach target in sol,
let start denote current traversing index in vector candidates
– we need to define terminate condition of DFS (i.e., when remain == 0)
– decide how/when to recursive build sol

Time complexity: O(2^n)
Space complexity: O(d) where d is the depth

## Solution

```class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> allSol;
if(candidates.empty()) return allSol;

vector<int> sol;
int remain = target;
int start = 0;
sort(candidates.begin(), candidates.end());
findComb(allSol, sol, start, remain, candidates);
return allSol;
}

//DFS
void findComb(vector<vector<int>>& allSol, vector<int>& sol, int start, int remain, vector<int>& candidates){
//check terminate state
if(remain == 0){
allSol.push_back(sol);
return;
}

//recursive construct solution
for(int i=start; i<candidates.size(); i++){
if(i>start && candidates[i-1] == candidates[i]) continue;
if(candidates[i] <= remain){
//push back
sol.push_back(candidates[i]);
findComb(allSol, sol, i, remain - candidates[i], candidates);
//pop back
sol.pop_back();
}else{
break;
}
}
}
};
```

# [Leetcode C++] Pow(x, n)

## Problem

Implement pow(x, n).

## Analysis

Divide and conquer, first compute pow(x, n/2), then use it to compute pow(x,n). Need to consider
– n is odd or even
– if n is odd, need to consider n is positive or negative

## Solution

```class Solution {
public:
double myPow(double x, int n) {
if(x==0) return 0;
if(n==0) return 1;

//divide and conquer
int half = n/2;
double val = myPow(x, half);
//check if n is odd or even
if(n%2 == 0)
return val*val;
else{
//check if n is positive or negative
if(n>0) return val*val*x;
else return val*val/x;
}

}
};
```

# [Leetcode C++] Remove Duplicates from Sorted Array

## Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

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

For example,
Given input array nums = `[1,1,2]`,

Your function should return length = `2`, with the first two elements of nums being `1` and `2` respectively. It doesn’t matter what you leave beyond the new length.

## Analysis

We can use an integer (validIdx) to keep track of current valid length, then we traverse the array
– when nums[i] has been repeated, continue
– otherwise, write it to the array, and advance validIdx

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

## Solution

```class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0) return 0;
int validIdx = 0;
int curr = nums;
for(int i=0; i<nums.size(); i++){
//if repeat continue
if(nums[i] == curr){
continue;
}
//otherwise write the array, and move index
else{
nums[validIdx] = curr;
curr = nums[i];
validIdx=validIdx+1;
}
}
nums[validIdx] = curr;
return (validIdx+1);
}
};
```

# [Leetcode C++] Container With Most Water

## Problem

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

## Analysis

We can use double pointers to solve this problem, let left and right denote the index of left and right pointer respectively, then we have
– height[left] < height[right], left++
– height[left] >= height[right], right–

## Solution

```class Solution {
public:
int maxArea(vector<int>& height) {
if(height.size()<=1) return 0;
int left = 0;
int right = height.size()-1;
int max = 0;

//two pointer
while(left < right){
//compute size
int curr = min(height[left], height[right]) * (right - left);
if(max < curr) max = curr;

if(height[left] < height[right]){
left++;
}else{
right--;
}
}
return max;
}
};
```