[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";
        
        //interatively read n times
        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[0];
        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

 

/**
 * Definition for singly-linked list.
 * 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[0].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[0][i])
                    return commPrefix;
            }
            commPrefix.push_back(strs[0][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)