Leetcode: Remove Nth Node From End of List in C++

Given a linked list, remove the n^th node from the end of list and return its head.
Solution:
ListNode *removeNthFromEnd(ListNode *head, int n) {
        if(!head)
        return NULL;
        ListNode* fast = head;
        for(int i=0;i<n;i++)
           fast = fast->next;
        ListNode* slow = head;
        ListNode* pre = slow;
        if(!fast)
        {
            head = head->next;
            delete slow;
            return head;
        }
        while(fast)
        {
            fast = fast->next;
            pre = slow;
            slow = slow->next;
        }
            pre->next = slow->next;
            delete slow;
            return head;
    }

Leetcode: Swap Nodes in Pairs in C++

Given a linked list, swap every two adjacent nodes and return its head.

For example,

Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Solution:

ListNode *swapPairs(ListNode *head) {
        if(!head)
        return NULL;
        ListNode* result;
        if(head->next)
        result = head->next;
        else
        return head;
        ListNode* cur = NULL;
        ListNode* pre = NULL;
        while(head&&head->next)
        {
            cur = head->next->next;
            head->next->next = head;
            if(pre)
            pre->next = head->next;
            head->next = NULL;
            pre = head;
            head = cur;
        }
        if(head&&pre)
        pre->next = head;
        return result;
    }

Code Practice: Reverse Linked List in C++

Node* ReverseLinkedList(Node* root)
{
     if(!root)
      return NULL;
      Node* pre = root;
      Node* next = root->next;
      root->next = NULL;
      while(root->next)
     {
           root = next
           next = root->next;
           root->next = pre;
           pre = root;
     }
      return root;
}

Leetcode: Substring with Concatenation of All Words in Java

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Solution:
public ArrayList<Integer> findSubstring(String S, String[] L) {
        HashMap<String, Integer> Lmap = new HashMap<String, Integer>();
        HashMap<String, Integer> Smap = new HashMap<String, Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        int total = L.length;
        if(total==0)
        return result;
        for(int i=0;i<total;i++)
        {
            if(!Lmap.containsKey(L[i]))
            Lmap.put(L[i], 1);
            else
            {
                int k = Lmap.get(L[i]);
                Lmap.put(L[i], k+1);
            }
        }
        int len = L[0].length();
        for(int i=0;i<=S.length()-len*total;i++)
        {
            Smap.clear();
            int j = 0;
            for(;j<total;j++)
            {
                String s = S.substring(i+j*len, i+(j+1)*len);
                if(!Lmap.containsKey(s))
                    break;
                if(!Smap.containsKey(s))
                Smap.put(s, 1);
                else
                {
                    int k = Smap.get(s);
                    Smap.put(s, k+1);
                }
                if(Smap.get(s)>Lmap.get(s))
                    break;
            }
            if(j==total)
            {
                result.add(i);
            }
        }
        return result;
    }

Leetcode: Anagrams in Java

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Solution:
public ArrayList<String> anagrams(String[] strs) {
        int len = strs.length;
        HashMap<String, Integer> mymap = new HashMap<String, Integer>();
        ArrayList<String> result = new ArrayList<String>();
        for(int i=0;i<len;i++)
        {
            char[] cur = strs[i].toCharArray();
            Arrays.sort(cur);
            String sorted = new String(cur);
            if(mymap.containsKey(sorted))
            {
                if(mymap.get(sorted)!=-1)
                {
                    result.add(strs[mymap.get(sorted)]);
                    mymap.put(sorted,-1);
                }
                result.add(strs[i]);
            }
            else
            {
                mymap.put(sorted, i);
            }
        }
        return result;
    }

Leetcode: Maximum Subarray in C++

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution:
int maxSubArray(int A[], int n) {
        int cur = 0;
        int max = INT_MIN;
        for(int i=0;i<n;i++)
        {
            if(cur>=0)
            {
                cur+=A[i];
            }
            else
                cur = A[i];
            if(cur>max)
            max = cur;
        }
        return max;
    }

Leetcode: Insert Interval in C++

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Solution:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> result;
        int len = intervals.size();
        int cur = 0;
        while(cur<len&&intervals[cur].end<newInterval.start)
        {
            result.push_back(intervals[cur]);
            cur++;
        }
        while(cur<len&&intervals[cur].start<=newInterval.end)
        {
            newInterval.start = min(intervals[cur].start, newInterval.start);
            newInterval.end = max(intervals[cur].end, newInterval.end);
            cur++;
        }
        result.push_back(newInterval);
        while(cur<len)
        {
            result.push_back(intervals[cur]);
            cur++;
        }
        return result;
    }

Leetcode: Trapping Rain Water in C++

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Solution:
int trap(int A[], int n) {
       vector<int> left(n, 0);
       int max = 0;
       for(int i=0;i<n;i++)
       {
           if(A[i]>max)
           {
               max = A[i];
           }
           left[i] = max;
       }
       max = 0;
       int right = 0;
       int result = 0;
       for(int i=n-1;i>=0;i--)
       {
           if(A[i]>max)
           {
               max = A[i];
           }
           right = left[i]>max?max:left[i];
           result +=right - A[i];
       }
       return result;
    }

Leetcode: Set Matrix Zeroes in C++

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Did you use extra space?

Solution: 

void setZeroes(vector<vector<int> > &matrix) {
        bool rowflag = false;
        bool columnflag = false;
        if(matrix.size()==0)
        return;
        for(int i=0;i<matrix.size();i++)
        {
            if(matrix[i][0]==0)
            {
                columnflag = true;
            }
        }
        for(int j=0;j<matrix[0].size();j++)
        {
            if(matrix[0][j]==0)
            {
                rowflag = true;
            }
        }
        for(int i=1;i<matrix.size();i++)
        {
            for(int j=1;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i=1;i<matrix.size();i++)
        {
            for(int j=1;j<matrix[0].size();j++)
            {
                if(matrix[0][j]==0||matrix[i][0]==0)
                {
                    matrix[i][j] = 0;
                }
            }
        }
        if(columnflag)
        {
            for(int i=0;i<matrix.size();i++)
            {
                matrix[i][0]=0;
            }
        }
        if(rowflag)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                matrix[0][j]=0;
            }
        }
    }

Leetcode: Remove Duplicates from Sorted Array in C++

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 A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Solution:
int removeDuplicates(int A[], int n) {
        if(n<2)
        return n;
        int pre = A[0];
        int newlen = 1;
        for(int i=1;i<n;i++)
        {
            if(A[i]==pre)
            {
                continue;
            }
            else
            {
                A[newlen] = A[i];
                newlen++;
                pre = A[i];
            }
        }
        return newlen;
    }

Rotate List in C++

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.


Solution:
ListNode *rotateRight(ListNode *head, int k) {
        if(!head)
        return NULL;
        ListNode* quick = head;
        int len = 1;
        while(head->next)
        {
            head = head->next;
            len++;
        }
        head->next = quick;
        k = k%len;
        k = len - k;
        int cur = 1;
        while(cur < k)
        {
            quick = quick->next;
            cur++;
        }
        ListNode* newhead = quick->next;
        quick->next = NULL;
        return newhead;
    }

Leetcode: Search in Rotated Sorted Array II in C++

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

bool search(int A[], int n, int target) {
        int start = 0;
        int end = n-1;
        while(start<=end)
        {
            int mid = start+(end-start)/2;
            if(A[mid]==target)
             return true;
            if(A[mid]>A[start])
            {
                if(target>=A[start]&&target<A[mid])
                end = mid-1;
                else 
                start = mid+1;
            }
            else if(A[mid]<A[start])
            {
                if(target>A[mid]&&target<=A[end])
                start = mid + 1;
                else
                end = mid -1;
            }
            else
                start++;
        }
        return false;
    }

Leetcode: Partition List in C++

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal tox.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Solution:
ListNode *partition(ListNode *head, int x) {
        ListNode* left = new ListNode(0);
        ListNode* right = new ListNode(0);
        ListNode* headL = left;
        ListNode* headR = right;
        while(head)
        {
            if(head->val<x)
            {
                left->next = head;
                head = head->next;
                left = left->next;
                left->next = NULL;
            }
            else
            {
                right->next = head;
                head = head->next;
                right = right->next;
                right->next = NULL;
            }
        }
        left->next = headR->next;
        headR->next = NULL;
        delete headR;
        ListNode* result = headL->next;
        delete headL;
        return result;
    }

Leetcode: First Missing Positive in C++

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution:
int firstMissingPositive(int A[], int n) {
        if(n==0)
        return 1;
        int pos = 0;
        while(pos<n)
        {
            if(A[pos]>=0&&A[pos]<n&&A[pos]!=A[A[pos]])
            {
                swap(A[A[pos]],A[pos]);
            }
            else
            pos++;
        }
        for(int i=1;i<n;i++)
        {
            if(A[i]!=i)
            return i;
        }
        return A[0]==n?n+1:n;
    }

Leetcode: Merge Two Sorted Lists in C++

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:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode* head = new ListNode(0);  
        ListNode* cur = head;  
        while (l1&& l2) {  
     if (l1->val <= l2->val) {  
       cur->next = l1;  
       l1 = l1->next;  
     } else {  
       cur->next = l2;  
       l2 = l2->next;  
     }  
     cur = cur->next;  
   }  
   if (l1) {  
     cur->next = l1;  
   } else {  
     cur->next = l2;  
   }  
   return head->next;  
    }

Leetcode: 3Sum in Java

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:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
• 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: O(n2)
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(num.length<3)
        return res;
        Arrays.sort(num);
        for(int i=0;i<num.length-2;i++)
        {
            if(i>0&&num[i]==num[i-1])
            continue;
            int start = i+1;
            int end = num.length-1;
            while(start<end)
            {
                
                if(num[start]+num[end] == -num[i])
                {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(num[i]);
                    tmp.add(num[start]);
                    tmp.add(num[end]);
                    res.add(tmp);
                    start++;
                    end--;
                    while(num[start]==num[start-1]&&start<end)
                    start++;
                    while(num[end]==num[end+1]&&start<end)
                    end--;
                }
                else if(num[start]+num[end]>-num[i])
                end--;
                else
                start++;
            }
        }
        return res;
    }

Leetcode: Jump Game in C++

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution:
range is current max position we can reach.
bool canJump(int A[], int n) {
        int range = 0;
        int cur = 0;
        while(cur<=range)
        {
            if(cur+A[cur]>range)
            {
                range = cur+A[cur];
            }
            if(range>=n-1)
            break;
            cur++;
        }
        return range>=n-1;
    }

Leetcode: Remove Duplicates from Sorted Array II in C++

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Solution:

int removeDuplicates(int A[], int n) {
        if(n<=2)
        return n;
        int pre = A[0];
        int count = 1;
        int pos = 1;
        for(int i=1;i<n;i++)
        {
            if(A[i]==pre)
            {
                count++;
                if(count<=2)
                {
                    A[pos] = A[i];
                    pos++;
                }
            }
            else
            {
                pre = A[i];
                count = 0;
                A[pos] = A[i];
                pos++;
                count++;
            }
        }
        return pos;
    }

Leetcode: Remove Duplicates from Sorted List II in Java

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
Solution:  
public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
        return head;
        ListNode root = new ListNode(0);
        ListNode cur = head;
        ListNode pre = root;
       
        while(cur!=null)
        {
            boolean isDup = false;
            while(cur.next!=null&&cur.val==cur.next.val)
            {
                isDup = true;
                cur = cur.next;
            }
            if(isDup)
            {
                cur = cur.next;
            }
            else
            {
                pre.next = cur;
                pre = cur;
                cur = cur.next;
                pre.next = null;
               
            }
        }
        return root.next;

Leetcode: Merge Sorted Array in C++

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
Solution:
void merge(int A[], int m, int B[], int n) {
        int pos = m+n-1;
        m = m-1;
        n = n-1;
        while(n>=0&&m>=0)
        {
            if(A[m]>B[n])
            {
                A[pos] = A[m];
                m--;
            }
            else
            {
                A[pos] = B[n];
                n--;
            }
            pos--;
        }
        if(n>=0)
        {
            while(n>=0)
            {
                A[pos] = B[n];
                pos--;
                n--;
            }
        }
    }